De cabalgata a cabalgata
A los habitantes de Ledesmás les encantan las luces navideñas. A principio de diciembre el Ayuntamiento inunda el pueblo de adornos multicolores que retira convenientemente unas semanas después.
A la cabalgata de Reyes le presta especial atención. No solo se ponen luces navideñas, sino que se ilumina el recorrido con enormes focos equidistantes que dan la sensación de que se ha hecho de día. Como son meros postes con focos sin ninguna relación con las fiestas navideñas, tras la cabalgata se apagan y se dejan montados para el año siguiente.
Para reducir el gasto en electricidad, utilizan focos LED, de tal forma que cada foco está en realidad compuesto de una miríada de pequeñas "bombillas" led de bajo consumo que, sumadas, generan una potencia lumínica considerable a muy bajo coste.
El recorrido está dividido en varias secciones de la misma longitud y en cada una hay colocado uno de estos focos LED. Un foco ilumina la sección donde se encuentra y también L secciones más a cada lado, de tal manera que cada sección recibe luz de varios focos.
El problema es que al estar todo el año a la intemperie, los focos se deterioran y algunos de los leds que los forman se dañan y no lucen. Esto afecta tanto a la sección donde está el foco como a las L a cada lado a las que bañó con su luz la temporada pasada. El resultado es un recorrido iluminado de manera irregular dependiendo de cuántos leds se hayan fundido en cada sección.
La solución es obvia pero cara: reemplazar los leds estropeados. El Ayuntamiento de Ledesmás solo tiene presupuesto para reemplazar K leds de los fundidos o luego no tendrá dinero para encenderlos. Pero debe hacerlo aprovechando correctamente el dinero público, y para ello quiere que, tras sustituir tantos leds como permita el presupuesto, la sección menos iluminada tenga la mayor cantidad posible de luz. Eso sí, puede sustituir leds pero no puede quitar leds que funcionen para llevarlos a otro foco.
Entrada
La entrada está compuesta por distintos casos de prueba, cada uno ocupando dos líneas.
La primera línea de cada caso de prueba tiene tres números. El primero es el número N de focos (o secciones) por las que pasa la cabalgata (hasta 500.000); a continuación viene el número de secciones L a la izquierda y a la derecha a las que afecta cada foco (entre 0 y N−1), además de a aquella en la que está colocado. Por último aparece el número K de leds que podremos sustituir (hasta 1015).
La segunda línea contiene N números, uno por foco, con la cantidad de leds funcionales que aún conserva cada uno. Cada foco tiene como mucho 109 leds que funcionan, aunque tienen espacio para 1016.
Se garantiza que los focos de todos los casos no superarán los 2.000.000 y el presupuesto total los 1018.
Salida
Por cada caso de prueba se escribirá de cuántos leds recibirá luz la sección de acera menos iluminada tras las reparaciones, teniendo en cuenta que el objetivo es conseguir maximizar ese número.
Entrada de ejemplo
5 0 0 3 1 5 6 7 5 0 2 3 1 5 6 7 5 1 0 3 1 5 6 7 5 1 2 3 1 5 6 7
Salida de ejemplo
1 3 4 6
Notas
En el primer caso de prueba del ejemplo no hay presupuesto para arreglar nada, por lo que la situación se queda igual; como los focos solo afectan a la sección en la que están (L=0), la menos iluminada es la segunda con un único led. En el segundo caso se puede arreglar la segunda sección para que todas tengan al menos tres leds iluminándolas (L=0). El tercer caso no tiene presupuesto por lo que no hay arreglos y la sección menos iluminada será la primera, con cuatro leds gracias a que se ve afectada también por el segundo foco (L=1). El último caso es similar al anterior pero arreglando dos leds del segundo foco.