Problema número 716

Enchufando las luces de navidad

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
Casa con luces de navidad bordeando la fachada (generada por IA)

Los vecinos de enfrente se han venido arriba este año con la decoración de Navidad y han llenado toda la fachada de su casa de luces. En condiciones normales las miraría con indiferencia y algo de fastidio, porque tener luces parpadeantes entrando por la ventana durante toda la noche es francamente molesto.

Pero este año es distinto. Por distintos motivos, ha sido un año especialmente significativo para la familia, y no queremos tener que importar la alegría lumínica de los vecinos, de modo que estamos dispuestos a contraatacar. El problema es que en el porche solo tenemos un enchufe, de modo que hemos acabado comprando un montón de regletas, esos cables que se enchufan y tienen a la vez varias tomas adicionales donde enchufar más cosas. Permiten así conectar al mismo enchufe varias cosas, al mismo tiempo que aumentan la distancia de conexión.

Enchufando unas regletas a otras podemos conseguir un montón de tomas de enchufes sacadas todas del único que tenemos en el porche. Pero como tenemos tantas luces por poner, no tenemos claro que vayan a ser suficientes.

Entrada

Cada caso de prueba comienza con un número 1 ≤ N ≤ 1.000 que indica el número de regletas que hemos comprado. A continuación aparecen N números, entre 1 y 10, con la cantidad de tomas de enchufe que tiene cada una de las regletas. Las "regletas" con una sola toma son en realidad alargaderas, útiles para llevar electricidad a las zonas más alejadas de la fachada.

La entrada termina con un 0 que no debe procesarse.

Salida

Por cada caso de prueba se escribirá el máximo número de tomas de enchufes que podemos conseguir para conectar luces con las que adornar la fachada.

Entrada de ejemplo

1
5
2
5 5
0

Salida de ejemplo

5
9