Problem
Kazuma viaja con tres compañeros: Aqua, Megumin y Darkness. Pero los viajes no se pagan, por lo que nuestro escuadrón debe completar las tareas asignadas por el Gremio de Aventureros.
Kazuma ya ha elegido n tareas para completar. Sin embargo, cada vez que un escuadrón en pleno se enfrenta a algo, suceden imprevistos y cosas absurdas. Por eso Kazuma decidió que para cada una de las tareas llevaría
exactamente dos acompañantes.
La proporción de cada uno de los compañeros a Kazuma se caracteriza por un número entero. Inicialmente, la actitud de cada uno de ellos es neutral e igual a 0. En el proceso de completar la tarea, la actitud de las chicas que asumió la tarea hacia él cambia en una dirección positiva o negativa (o puede no cambiar en absoluto) .
Para cada una de las tareas, Kazuma sabe cómo cambiará la actitud de cada niña hacia él después de completar la tarea. Quiere llevar compañeros a las tareas para que, después de completarlas todas, las actitudes de todas las chicas hacia él sean iguales. Si esto se puede lograr de diferentes maneras, entonces, por supuesto, es necesario que la relación sea lo mejor posible.
Ayuda a Kazuma a descubrir cuál es el trato más equitativo que puede recibir para todas las chicas.
Entrada:
La primera línea contiene un entero positivo n (1 ≤ n ≤ 25) — el número de tareas a completar.
Las siguientes n líneas contienen descripciones de — i-ésima línea contiene tres números a
i, m
i, d
i — la cantidad en la que cambiarán las actitudes de Aqua, Megumin o Darkness hacia Kazuma, respectivamente, si el héroe los lleva con él para completar la i-ésima tarea.
Todos los números en la entrada son enteros y no exceden 10
7 en valor absoluto.
Salida:
Si no hay solución, escriba "Imposible" en la primera línea.
De lo contrario, imprima la relación que todas las chicas tendrán con Kazuma y, al mismo tiempo, imprima la máxima posible.
Ejemplos:
| Entrada |
Salida |
3
1 0 0
0 1 0
0 0 1
| 1 |
7
0 8 9
5 9 -2
6-8-7
9 4 5
-4 -9 9
-4 5 2
-6 8 -7
| 5 |
2
1 0 0
1 1 0
| Imposible |