Colocando campamentos de altura
Juanito quiere subir al Everest y está planeando la ascensión desde el campo base. Para llegar a la cumbre tendrá que instalar varios campamentos de altura en los que hacer noche.
Los campamentos sólo se pueden instalar en determinados puntos de la montaña, y la instalación de cada uno de ellos lleva un coste asociado que depende de su ubicación, el espacio disponible, la exposición al viento, etc. Juanito quiere minimizar los costes de la expedición, sabiendo que en cada jornada no puede superar más de un máximo conocido de desnivel desde el campamento de partida de ese día hasta el de llegada.
¿Puedes ayudarle a calcular el coste mínimo de la expedición?
Entrada
La entrada está formada por distintos casos de prueba, cada uno de ellos compuesto de 4 líneas.
La primera línea contiene un único número entero N (5 ≤ N ≤ 1.000), que representa el número de posibles ubicaciones para los campamentos de altura. La segunda línea contiene N números enteros, correspondientes a la altura de cada una de las ubicaciones, medida desde el campo base. Las ubicaciones están ordenadas por altura desde el campo base, y la última ubicación corresponde a la cima de la montaña. La tercera línea contiene N números enteros entre 10 y 100, correspondientes a los costes asociados a la instalación de un campamento en cada una de las ubicaciones. El último de estos números siempre será 0, pues la última ubicación es la cumbre y en la cumbre no se instala ningún campamento. La cuarta línea contiene un único número entero M (100 ≤ M ≤ 1.000), que representa el máximo desnivel permitido entre dos campamentos consecutivos (incluyendo el campo base), o entre el último campamento y la cumbre de la montaña.
Se garantiza que el problema siempre tiene solución.
Salida
Para cada caso de prueba, se escribirá una línea con el coste mínimo de la expedición.
Entrada de ejemplo
5 100 200 300 400 500 10 10 10 10 0 100 11 300 600 1000 1500 1700 2000 2150 2400 2700 2950 3300 10 20 30 40 50 60 70 80 90 100 0 650
Salida de ejemplo
40 250