Problem
Kazuma voyage avec trois compagnons : Aqua, Megumin et Darkness. Mais le voyage n'est pas payé, donc notre équipe doit accomplir les tâches assignées par la guilde des aventuriers.
Kazuma a déjà choisi n tâches à accomplir. Cependant, chaque fois qu'une équipe en pleine force prend quelque chose, des choses imprévues et absurdes se produisent. C'est pourquoi Kazuma a décidé que pour chacune des tâches, il prendrait
exactement deux compagnons.
Le rapport de chacun des compagnons à Kazuma est caractérisé par un nombre entier. Initialement, l'attitude de chacune d'elles est neutre et égale à 0. Au cours de la réalisation de la tâche, l'attitude des filles qu'il a prises en charge à son égard change dans un sens positif ou négatif (ou peut ne pas changer du tout) .
Pour chacune des tâches, Kazuma sait comment l'attitude de chaque fille envers lui changera après avoir terminé la tâche. Il veut prendre des compagnons pour des missions afin qu'après les avoir toutes accomplies, les attitudes de toutes les filles à son égard soient égales. Si cela peut être réalisé de différentes manières, alors, bien sûr, il est nécessaire que la relation soit aussi bonne que possible.
Aidez Kazuma à déterminer quel est le traitement le plus équitable qu'il puisse obtenir pour toutes les filles.
Saisie :
La première ligne contient un entier positif n (1 ≤ n ≤ 25) — le nombre de tâches à accomplir.
Les n lignes suivantes contiennent des descriptions de — la ième ligne contient trois nombres a
i, m
i, d
i — le montant par lequel les attitudes d'Aqua, Megumin ou Darkness envers Kazuma changeront, respectivement, si le héros les emmène avec lui pour accomplir la ième tâche.
Tous les nombres dans l'entrée sont des nombres entiers et ne dépassent pas 10
7 en valeur absolue.
Sortie :
S'il n'y a pas de solution, écrivez "Impossible" sur la première ligne.
Sinon, imprimez la relation que toutes les filles auront envers Kazuma, et en même temps, imprimez le maximum possible.
Exemples :
| Entrée |
Sortie |
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
| Impossible |