Powerless Mage

시간 제한2초메모리 제한512 MB

요약

n개의 주문 마나 비용 벡터가 주어질 때, 어떤 주문도 시전할 수 없는 최대 총 마나 Q+W+E를 구하거나 무한히 큰 경우를 판정한다.

난이도: 보통10점 중 7점
유형: 수학, 기하, 구현
정답자: 아직 제출이 없습니다

문제

A mage knows $n$ spells, the $i$ -th of which requires $q\_i$ blue mana, $w\_i$ purple mana and $e\_i$ orange mana ( $q\_i + w\_i + e\_i > 0$ ). Let's say the mage has $Q$ blue mana, $W$ purple mana and $E$ orange mana, and denote the total amount of mana $Q + W + E$ as $R$ . Knowing that the mage is unable to cast any spell, what can be the maximal value of $R$ ?

입력

The first line contains an integer $n$ ( $1 \le n \le 200000$ ) --- the number of spells.

Each of the next $n$ lines contains three integers $q\_i$ , $w\_i$ , $e\_i$ ( $0 \le q\_i, w\_i, e\_i \le 10^{9}, q\_i + w\_i + e\_i > 0$ ) --- the manacosts of the $i$ -th spell.

출력

Output the maximal total amount of mana $R$ such that the mage is unable to cast any spell.

If this number is infinitely large (for any total amount of mana $R$ , there could be a situation so that the mage is unable to cast any spell), output "Infinity".

예제3

예제 1
입력
```
4
0 0 100
0 100 0
100 0 0
61 71 81
```
예상 출력
```
278
```

예제 2

입력

예상 출력

예제 3
입력
```
3
3 1 1
1 3 1
1 1 3
```
예상 출력
```
Infinity
```