Atascos con público
La M-30 es una vía de circunvalación de unos 30 kilómetros de longitud que rodea el centro de Madrid. Se comenzó a construir en 1970 y desde entonces da servicio a miles (e incluso cientos de miles) de vehículos diarios. Tanto es así que sus atascos son famosos y nunca falta en la información del tráfico que todas las mañanas dan en las horas punta las radios y televisiones.
En 2006 se comenzó una inmensa obra para soterrar un buen número de kilómetros de la vía liberando miles de metros cuadrados de superficie que pasaron a ser en su mayor parte zonas verdes. En ese tramo soterrado se tuvo que dejar, eso sí, una pequeña parte que seguía siendo de superficie pues discurría por debajo de las gradas de un estadio de fútbol (Vicente Calderón) y era imposible soterrar esa zona teniendo una construcción tan grande encima.
Eso cambió cuando el club de fútbol propietario del estadio se mudó a otro en las afueras. En 2019 comenzaron los trabajos de demolición y el trazado de la M-30 se vio alterado durante las obras. Curiosamente durante una de las fases, las gradas del estadio seguían en pie y la M-30 pasaba justo delante, dando la sensación de que se habían colocado unas majestuosas gradas para que los famosos atascos pudieran tener espectadores.
El alcalde de una ciudad al sur de Madrid llamada Le-ganéh vio fotos de la M-30 con las gradas y, haciendo honor al nombre de la ciudad, quiso superar al alcalde de Madrid poniendo gradas en su carretera principal y cobrar entrada a todo aquel que quisiera ver sus atascos. Dividió la carretera en tramos e hizo una estimación de las ganancias esperadas en cada uno para decidir en cuáles las colocaría. Eso sí, teniendo en cuenta que entre grada y grada debía de haber al menos k tramos sin público para no despistar mucho a los conductores.
Afortunadamente un asesor le dijo a tiempo que lo de la grada de la M-30 era temporal y el proyecto en Le-ganéh se canceló. Aun así queremos ver si la planificación de dónde poner las gradas estaba bien hecha o no.
Entrada
La entrada comienza con el número de casos de prueba que vendrán a continuación.
Cada caso de prueba tiene dos líneas. En la primera aparecen dos números con el número de tramos (hasta 100.000) y el número de tramos vacíos que hay que dejar como mínimo entre dos gradas. La segunda línea contiene tantos números como tramos con las ganancias que podrían obtenerse en cada uno de ellos en caso de colocarse ahí una grada (hasta 109).
Salida
Por cada caso de prueba se escribirá el beneficio máximo que se puede conseguir teniendo en cuenta que se pueden colocar gradas en todos los tramos que se quiera siempre y cuando entre dos tramos con gradas se respete el mínimo número de tramos sin ellas.
Entrada de ejemplo
3 3 1 600 1000 600 3 1 600 2000 600 6 1 1000000000 60 10 1000000000 10 1000000000
Salida de ejemplo
1200 2000 3000000000