Megaautopista de Oriente
La megaautopista de Oriente está terminada y a punto de estrenarse. A lo largo de sus miles de kilómetros hay áreas de descanso ya habilitadas. Las autoridades han abierto un concurso para la explotación de dichas áreas, y en particular para la construcción de restaurantes que sirvan de esparcimiento gastronómico a los usuarios de la autopista. Para evitar el monopolio han puesto una condición: una misma empresa no podrá tener dos restaurantes a menos de K kilómetros de separación.
En la compañía de restaurantes Le Nouvelle Kebab están muy interesados en esta oportunidad de expansión y van a apostar fuerte por conseguir un buen negocio. Han hecho un estudio y valorando cada área de descanso según su posición, las poblaciones cercanas, la cantidad de tráfico previsto, las vistas, etc., han estimado cuál sería el beneficio medio diario en cada área de descanso.
Ahora quieren saber dónde deberían construir sus restaurantes para maximizar el beneficio obtenido, sabiendo que tienen que respetar la restricción sobre separación entre restaurantes.
Entrada
La entrada está formada por diversos casos de prueba. Cada caso se describe en tres líneas: en la primera aparece el número N de áreas de descanso de la megaautopista (1 ≤ N ≤ 300.000) y los kilómetros K de separación mínima entre restaurantes de la misma empresa (1 ≤ K ≤ 1.000.000); en la segunda línea aparecen los N puntos kilométricos donde están localizadas esas áreas de descanso, en orden y medidos todos desde el comienzo de la megaautopista (esta nunca tendrá más de 10.000.000 de kilómetros); y en la tercera aparecen los N beneficios estimados, uno por área, en el mismo orden (los beneficios por área nunca son mayores que 1.000).
Salida
Por cada caso de prueba se escribirá una línea con el máximo beneficio que puede obtener la compañía de restaurantes según su estimación y respetando la restricción de separación entre restaurantes.
Entrada de ejemplo
3 15 10 20 30 20 40 10 3 10 10 20 30 20 40 10
Salida de ejemplo
40 70