Ir al contenido (saltar navegación)

Devorando el turrón

Tiempo máximo: 1,000-3,000 sMemoria máxima: 32768 KiB
Bandeja con dos filas de trozos de turrón

Parecía que no iba a llegar nunca pero por fin te encuentras en la sobremesa de la cena de nochevieja. Y es que hacer de anfitrión y que venga todo el mundo a cenar a casa es agotador. Te pasas el día preparando entrantes, primer plato, plato principal, postre y uvas. Tienes que encargarte de que las bebidas estén frías, la mesa en perfecto estado y la casa ordenada. Y todo eso, además, teniendo en cuenta que la mañana la has pasado ocupada liado en el ordenador.

Y lo peor de todo es que ni siquiera has cenado bien. No has hecho más que ir y venir de la cocina al salón, preocupándote de que no le faltara nada a tus comensales y ahora te das cuenta de que ellos ya están atiborrados mientras a ti los turrones que cuidadosamente colocaste ayer en la bandeja (sabías que hoy no te daría tiempo) te están llamando a gritos.

En la bandeja hay dos hileras con pedazos de turrón de distintos tipos. Por la posición que ocupas llegas a coger turrones de ambas hileras así que comerás de ambas, aunque por educación irás cogiendo solo de los dos extremos más cercanos, haciendo que las hileras vayan siendo cada vez más cortas.

Si tienes una estimación del tiempo que tardas en comer cada pedazo, ¿cuántos trozos de turrón podrás comerte como mucho en el tiempo que queda de fiesta?

Entrada

La entrada está compuesta por distintos casos de prueba, cada uno en tres líneas.

La primera línea de cada caso de prueba comienza con dos números, n y m, representando el número de trozos de turrón que hay en cada hilera (entre 0 y 200.000) seguidos del tiempo que tienes para comer turrón (entre 0 y 109).

Las dos líneas siguientes contienen nm números respectivamente con el tiempo que se tarda en comer cada pedazo de turrón (entre 1 y 2000). Los pedazos que tienes más cerca (que son por los que empiezas comiendo) corresponden a los últimos números de cada línea.

Salida

Por cada caso de prueba se escribirá una única línea con el número de pedazos de turrón que, como mucho, podrás comer en el tiempo disponible.

Entrada de ejemplo

3 2 2
2 2 1
2 1
3 5 5
1 3 3
2 1 1 1 1

Salida de ejemplo

2
4