숙제 부담

이미지 출처: publicdomainpictures.net

몇 년 전 Menntaskólinn á Akureyri의 교장은 연설에서 학생들의 반응이 그다지 좋지 않았던 몇 가지 말을 했다. 그는 학생들이 평일마다 방과 후에 단 한 시간만 남아 있으면 이후 집에서 할 숙제가 전혀 없을 것이며, 숙제에 대한 불평은 과장된 것이라고 주장했다.

Menntaskólinn á Akureyri에 다녔거나 현재 다니고 있는 학생들은 (사실 다른 아이슬란드 고등학교의 학생들도 마찬가지로) 이것이 완전히 터무니없는 소리라는 사실을 잘 알고 있다. Menntaskólinn á Akureyri에서 Íslandsáfangar를 견뎌 내야 했던 사람이라면 특히 잘 안다. 이 주장이 얼마나 현실과 동떨어져 있는지 보여 주기 위해 과제와 마감일에 관한 일부 데이터를 수집했다. 이제 여기서는 모든 것을 끝내기 위해 하루에 방과 후 얼마나 공부해야 하는지를 살펴본다.

아이슬란드 사가, 원자 시인, 폭포와 고래 종의 이름 외우기, 게다가 보너스 문제를 맞히려면 선생님이 가장 좋아하는 수영장의 이름도 기억하는 게 좋을 것이다! 완전히 미친 짓이다. 하루 종일이라도 계속 말할 수 있다! 이 모든 것은 즉시 폐지되어야 하고 전부-

뭐라고? 아니, 아직 문제 설명을 다 쓰지 않았어. 이봐! 안 돼- 아직 안 끝났어! 키보드에서 손 떼-

방금 일은 미안하다.

각 과제는 특정한 날에 부여되며 특정한 날까지는 늦어도 완료해야 한다. 또한 각 문제를 완료하는 데에는 일정한 수의 시간 단위가 걸린다. (이미 모든 숙제를 끝낸 경우가 아니라면) 매일 항상 $x$ 시간 단위만큼 공부하려고 한다면, 모든 과제를 기한 내에 끝낼 수 있도록 하려면 $x$의 최솟값은 얼마여야 하는가?

채점

그룹 | 점수 | 제약 조건

1 | 15 | $n = 1$.

2 | 20 | 모든 $i$에 대해 $n \leq 100$이고 $t_i \leq 100$이다.

3 | 25 | 모든 $i$에 대해 $a_i = b_i$이다.

4 | 40 | 추가 제약 조건이 없다.

입력의 첫째 줄에는 과제의 수를 나타내는 하나의 정수 $n$이 주어진다. 항상 $0 \leq n \leq 100\,000$을 만족한다. 이어서 $n$개의 줄이 주어지며, 그중 $i$번째 줄에는 $i$번째 과제의 세부 정보가 주어진다.

각 줄에는 세 정수 $a_i, b_i, t_i$이 주어진다. 여기서 $a_i$은 과제가 부여되는 날이고, $b_i$은 과제의 마감일이며(그날이 끝날 때 과제를 제출해도 된다), $t_i$은 과제를 완료하는 데 걸리는 시간 단위의 수이다. 항상 $0 \leq a_i, b_i, t_i \leq 10^9$ 및 $a_i \leq b_i$을 만족한다.

입력의 값은 크며 계산 결과가 $32$비트에 들어가지 않을 수도 있음에 유의한다.

모든 과제를 기한 내에 끝내기 위해 하루에 공부해야 하는 최소 시간 단위 수를 출력한다.