Ir al contenido (saltar navegación)

La fiesta del verano

Tiempo máximo: 1,000-3,000 sMemoria máxima: 4096 KiB
Playa

El segundo domingo de agosto se celebra la fiesta de mi pueblo. El ayuntamiento coloca grandes carpas en la playa y pone mesas para que comamos todos los vecinos. Las mesas se organizan por edades para evitar que los chavales se aburran con la conversación de sus padres y estos a su vez no tengan que aguantar el jaleo de los más pequeños. Las mesas son todas del mismo tamaño colocándose varias para un mismo tramo de edad si es necesario.

Cada año el ayuntamiento dedica un gran esfuerzo a calcular el número de mesas necesarias, de forma que sean lo más grandes posible, no sobre ningún hueco, y al mismo tiempo sean todas ellas del mismo tamaño. Este año han decidido informatizar el proceso. ¿Puedes ayudarles?

Entrada

La entrada está formada por varios casos de prueba. Cada caso consiste en una lista de valores con el número de personas en cada tramo de edad, acabada con el valor cero. La última lista tendrá solamente el valor cero, y no debe ser procesada. Cada tramo estará formado por al menos una persona y el número total de personas nunca será mayor que 1018.

Salida

Para cada caso de prueba se indicará el número de mesas a utilizar. Recuerda que se desea que las mesas tengan el mayor tamaño posible sin que sobre ningún hueco.

Entrada de ejemplo

10 25 30 0
60 45 0
7 0
0 

Salida de ejemplo

13
7
1