Bakejoon Online Judge는 특이한 조건을 만족하는 빵을 구워서 제출하는 온라인 저지이다.
Bakejoon Online Judge의 유저인 당신은 다음 조건을 만족하는 $N$개의 신선한 빵을 한 번에 제출해야 한다.
빵은 한 번에 최대 한 개만 구울 수 있으며, 굽기 시작한 빵을 중단할 수는 없다.
각 빵은 준비 시간 $P_i$, 굽는 시간 $T_i$, 신선도 $F_i$라는 특성을 가진다.
- 빵을 굽기 전의 준비 시간이 필요하므로 $i$번째 빵은 시각 $P_i$부터 구울 수 있다.
- $i$번째 빵을 굽는 데에는 $T_i$ 시간이 걸린다.
- $i$번째 빵은 완전히 구워진 시각부터 $F_i$ 시간 동안 신선함이 유지된다.
엄밀히는, 시각 $t \ge P_i$에 $i$번째 빵을 굽기 시작하면 시각 $t+T_i$에 빵이 완전히 구워지고, 시각 $t+T_i$부터 시각 $t+T_i+F_i$까지 신선함이 유지된다. 시각이 정확히 $t+T_i$ 또는 $t+T_i+F_i$일 때도 빵은 신선하다.
$N$개의 빵의 특성이 주어질 때 모든 빵을 신선한 상태로 제출할 수 있는지와 가능하다면 빵을 제출할 수 있는 가장 이른 시각을 구해보자.
입력
첫째 줄에 빵의 개수 $N$이 주어진다.
$$1 \le N \le 200\,000$$
둘째 줄부터 $N$개의 줄에 걸쳐 각 빵의 준비 시간 $P_i$, 굽는 시간 $T_i$, 신선도 $F_i$가 공백을 사이에 두고 주어진다.
$$0 \le P_i,T_i,F_i \le 10^9$$
출력
$N$개의 빵을 모두 신선한 상태로 제출할 수 있는 가장 이른 시각을 출력한다. 만약 $N$개의 빵을 모두 신선한 상태로 제출할 수 없다면 -1을 대신 출력한다.
입출력 예시
예제 1
입력
4
2 0 4
4 1 2
1 2 0
0 3 7출력
7예제 2
입력
3
0 1 1
1 1 1
2 1 1출력
-1노트
첫 번째 예제의 경우 다음 방식대로 빵을 구우면 시각 $7$에 모든 빵을 신선한 상태로 제출할 수 있다.
| 빵 | 굽는 시간 구간 | 신선한 시간 구간 |
|---|---|---|
| 1 | 시각 $5$에 즉시 | $[5,9]$ |
| 2 | $[4,5]$ | $[5,7]$ |
| 3 | $[5,7]$ | 시각 $7$에만 |
| 4 | $[0,3]$ | $[3,10]$ |
즉, 4번 빵을 시각 $0$부터 시각 $3$까지, 2번 빵을 시각 $4$부터 시각 $5$까지 굽고, 시각 $5$에 1번 빵을 즉시 구운 뒤, 3번 빵을 시각 $5$부터 시각 $7$까지 구우면 시각 $7$에 네 빵이 모두 신선하다.
원문의 그림에서 회색 X는 아직 빵을 구울 준비가 되지 않았음을, 초록색 P는 준비가 완료되었음을, 빨간색 T는 오븐에서 빵을 굽고 있음을, 파란색 F는 빵이 신선한 상태임을, 노란색 R은 빵이 더 이상 신선하지 않음을 나타낸다.
두 번째 예제의 경우 어떻게 빵을 굽더라도 $3$개의 빵을 모두 신선한 상태로 만들 수 없다.