Carrera de sacos en downtown P25067

La calle mayor de tu pueblo tiene mucha pendiente, lo que hace que sea un lugar propicio para celebrar... ¡carreras de sacos! En una ya antigua y respetada tradición, la gente se reúne cerca de la calle mayor para disfrutar de la carrera (y con el botiquín de emergencia a punto para atender a los posibles heridos).

La carrera siempre empieza en la calle mayor (no necesariamente al principio de la misma) y trascurre en su totalidad por dicha calle. La calle mayor se divide en N trozos (manzanas). La carrera no puede empezar ni acabar en la mitad de un trozo. La Federación de Carreras de Sacos Pendiente Abajo no permite que la carrera dure más de L metros.

Conociendo la longitud y el número de público asistente a cada uno de los N trozos, encuentra dónde debería empezar y acabar la carrera, de modo que se maximice la cantidad de público sin exceder la longitud máxima L. En caso de empate en número de público, devuelve la carrera más larga (sin exceder nunca L). Si hubiera más de una, devuelve la que empiece lo antes posible.

Entrada

Cada entrada contiene un número arbitrario de casos. Para cada caso, la primera línea contiene los números N≥ 1 y L≥ 1. La segunda línea contiene las longitudes (en metros) de los N trozos de la calle mayor, en el sentido de la carrera (pendiente abajo). La tercera línea contiene el número de público asistente a cada uno de los N trozos, todos ellos números entre 0 y 1000.

Salida

Escribe, en una línea y separados por espacios, el punto inicial y el punto final de la carrera (ambos números expresados en metros desde el inicio de la calle mayor) y la cantidad de público que asistirá.

Si no es posible organizar ninguna carrera porque todos los trozos son mayores que L, escribe 0 0 0.

Puntuación

• TestA:  ‍25 Puntos ‍

  Resolver casos con 1≤ N≤ 100, 1≤ L≤ 1000 y donde todas las distancias son 10.

• TestB:  ‍25 Puntos ‍

  Resolver casos con 1≤ N≤ 100, 1≤ L≤ 10⁹ y donde todas las distancias están entre 10 y 10⁷.

• TestC:  ‍25 Puntos ‍

  Resolver casos con 1≤ N≤ 50000, 1≤ L≤ 500000 y donde todas las distancias son 10.

• TestD:  ‍25 Puntos ‍

  Resolver casos con 1≤ N≤ 50000, 1≤ L≤ 10⁹ y donde todas las distancias están entre 10 y 10⁷.