Problem
Kazuma는 Aqua, Megumin 및 Darkness의 세 동료와 함께 여행합니다. 하지만 여행비는 지급되지 않기 때문에 우리 분대는 모험가 조합에서 할당한 임무를 완수해야 합니다.
Kazuma는 이미 완료할 n개의 작업을 선택했습니다. 그러나 전력을 다한 분대가 어떤 일을 맡을 때마다 예상치 못한 황당한 일이 발생한다. 그렇기 때문에 Kazuma는 각 작업에 대해
정확히 두 동료를 데려가기로 결정했습니다.
Kazuma에 대한 각 동료의 비율은 정수가 특징입니다. 처음에 그들 각각의 태도는 중립적이며 0과 같습니다. 작업을 완료하는 과정에서 그가 작업을 수행 한 소녀들의 태도는 긍정적 또는 부정적 방향으로 변경됩니다 (또는 전혀 변경되지 않을 수 있음). .
각 작업에 대해 Kazuma는 각 소녀가 작업을 완료한 후 그에 대한 태도가 어떻게 변할지 알고 있습니다. 그는 모든 과제를 완료 한 후 그에 대한 모든 소녀의 태도가 동등하도록 동료를 과제에 데려 가고 싶어합니다. 이것이 다른 방법으로 달성될 수 있다면 물론 관계가 가능한 한 좋은 것이 필요합니다.
카즈마가 모든 소녀들에게 받을 수 있는 가장 동등한 대우가 무엇인지 알아내도록 도와주세요.
입력:
첫 번째 줄은 양의 정수 n(1 ≤ n ≤ 25)을 포함합니다. 완료할 작업 수.
다음 n행에는 — i 번째 줄에는 a
i, m
i, d
i — 아쿠아, 메구밍, 다크니스가 i번째 과제를 완수하기 위해 아쿠아, 메구밍, 다크니스의 카즈마에 대한 태도가 각각 변하는 정도.
입력의 모든 숫자는 정수이며 절대값이 10
7을 초과하지 않습니다.
출력:
해결책이 없으면 첫 줄에 "Impossible"을 인쇄하십시오.
그렇지 않으면 모든 소녀가 Kazuma에 대해 가질 관계를 인쇄하고 동시에 가능한 최대를 인쇄하십시오.
예:
<몸>
| 입력 |
출력 |
3
100
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
100
1 1 0
| 불가능 |