Florencia
La ciudad de Florencia es muy conocida por la imponente cúpula de su catedral (Duomo de Santa Maria del Fiore), por sus puentes (como el Ponte Vecchio), y por sus plazas y fuentes.
Aunque en mucha menor medida, también es conocida por la belleza de sus paraguas y parasoles, que se han convertido en un objeto perseguido por los turistas y visitantes ocasionales.
No obstante, los paraguas y parasoles no son un invento florentino. Se han encontrado pruebas del uso de paraguas en civilizaciones antiguas, como Egipto, Grecia y Roma. En aquel entonces, se utilizaban como parasoles (de hecho, la palabra inglesa umbrella, tiene una raiz etimológica romana, umbra, sombra), y eran habitualmente un objeto de uso femenino. En China y otras civilizaciones más remotas, también hay pruebas del uso de parasoles hace más de dos mil años. Su uso como protector contra la lluvia tardó mucho más en llegar, debido a la necesidad de impermeabilizar la lona.
No fue hasta principios del siglo XX cuando surgieron los primeros paraguas plegables. Éstos tienen la ventaja de ocupar poco espacio, por lo que pueden ser metidos en cualquier sitio, para luego ser abiertos, cubriendo una gran superficie, lo que hace las delicias de algunos de sus usuarios.
Un paraguas abierto tiene forma de polígono regular. El número de lados suele ser de al menos 8, lo que le confiere una forma circular. Para soportar el peso de la lona abierta, se utilizan varillas (normalmente metálicas) que parten del centro y que crean la estructura interna, recordando a los nervios de la cúpula de Brunelleschi.
Los paraguas plegables, al contrario que los de bastón, suben y bajan las varillas internas, de manera que la lona queda rodeando al palo interior cuando está plegada. La longitud de un paraguas cerrado debe ser como mínimo el radio de la lona una vez abierta. Para disminuir esa longitud, algunos fabricantes dividen las varillas internas en varios segmentos, de modo que la lona se pliega sobre sí misma, lo que consigue paraguas cerrados de un tamaño mucho más reducido, sin perder superficie una vez abiertos.
La característica que distingue a los paraguas florentinos es su doble lona, una exterior, que protege de la lluvia, y una interior, que oculta las varillas y todo el mecanismo de plegado, haciéndolos mucho más estéticos.
Un fabricante compra varillas largas, que luego trocea según va creando cada paraguas. No es demasiado cuidadoso con los retales, de modo que si la porción de varilla restante que le queda es más corta de lo que necesita, la desprecia sin preocuparse de si podrá utilizarla en el futuro, y empieza una varilla nueva.
Para una longitud de la varilla inicial, y un grupo de paraguas a fabricar, ¿eres capaz de decirnos cuantas varillas se necesitan?
Entrada
La entrada estará compuesta por múltiples casos de prueba, cada uno formado por dos líneas. La primera contendrá la longitud (en centímetros) de las varillas largas de partida, que serán troceadas durante la fabricación de los paraguas. La segunda contiene una lista con descripciones de los paraguas a fabricar.
Cada paraguas se define con tres números mayores que 0. El primero indica el número de "nervios" del paraguas, el segundo el número de segmentos en los que se ha troceado cada uno (para hacer aún más reducido el paraguas cerrado), y el tercero la longitud de cada uno de esos segmentos. La lista de paraguas termina cuando el número de lados del siguiente paraguas es -1.
Por su parte, la entrada termina cuando la longitud de las varillas de partida es -1.
Salida
Para cada caso de prueba se escribirán dos números separados por un espacio. El primero indicará cuantas varillas tendrá que comprar el fabricante para poder crear todos los paraguas, recordando que descarta los retales de cada varilla sin preocuparse de aprovecharlos más adelante. El segundo número indicará la suma de la longitud de esos retales.
Si con la longitud de las varillas es imposible construir los paraguas, se escribirá IMPOSIBLE.
Entrada de ejemplo
200 8 1 60 8 3 20 -1 100 8 1 60 8 3 20 -1 50 8 1 60 8 3 20 -1 -1
Salida de ejemplo
5 40 13 340 IMPOSIBLE