Задача
Казума путешествует с тремя спутницами: Аквой, Мегумин и Даркнесс. Но за путешествия не платят, поэтому нашему отряду необходимо выполнять задания, порученные гильдией авантюристов.
Казума уже выбрал n заданий, которые необходимо выполнить. Однако всегда, когда отряд в полном сборе берется за что-то, то происходят непредвиденные и абсурдные вещи. Именно поэтому Казума решил, что на каждое из заданий он возьмет
ровно двух спутниц.
Отношение каждой из спутниц к Казуме характеризуется целым числом. Изначально отношение каждой из них нейтрально и равно 0. В процессе выполнения задания отношение девушек, которых он взял на задание, к нему меняется в положительную или отрицательную сторону (а может и не меняться вовсе).
Для каждого из заданий Казума знает, как изменится отношение каждой девушки к нему после выполнения поручения. Он хочет брать спутниц на задания так, чтобы после выполнения всех, отношения всех девушек к нему были равны. Если этого можно добиться разными способами, то, конечно, необходимо, чтобы отношение было как можно лучше.
Помогите Казуме определить, какое наибольшее, равное для всех девушек, отношение к нему он может получить.
Входные данные:
В первой строке содержится целое положительное число n (1 ≤ n ≤ 25) — количество заданий, обязательных для выполнения.
Следующие n строк содержат описание заданий — i-я строка содержит три числа a
i, m
i, d
i — величины, на которые изменятся отношения к Казуме Аквы, Мегумин или Даркнесс соответственно, в случае, если герой возьмет их с собой на выполнение i-го задания.
Все числа во входных данных целые и не превышают по абсолютному значению 10
7.
Выходные данные:
В случае, если решения не существует, в первой строке выведите "Impossible".
В противном случае выведите отношение, которое будет у всех девушек по отношению к Казуме и при этом максимально возможное.
Примеры:
| Входные данные |
Выходные данные |
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 |