견습생의 학습 계획

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

요약

n명의 장인마다 작업 시간대 [a_i, b_i]와 검 제작 시간 t_i가 주어질 때, 각 장인의 시간대 안에서 길이 t_i인 구간을 겹치지 않게 최대한 많이 고르는 문제입니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 구간, 그리디
정답자: 아직 제출이 없습니다

문제

아비게일은 대장장이가 되기 위해 수련하는 견습생이다. 그녀는 유명한 전문가가 되는 길에서 가능한 한 많은 검을 만들고 싶어 하며, 이를 위해 학습 계획을 세우려 한다.

$n$ 명의 대장이 아비게일을 견습생으로 받아 줄 의향이 있다. $i$ 번째 대장은 $a_i$ 분에 일을 시작하여 $b_i$ 분에 일을 마친다. 따라서 이 대장이 일하는 총 시간은 $b_i - a_i$ 분이다. 아비게일은 이 구간 동안 그 대장의 대장간에서 일할 수 있다. 대장간에 여러 번 들어가고 나올 수 있으며, 올 때마다 검을 한 자루 또는 여러 자루 만들 수 있다. 다만 $i$ 번째 대장의 감독 아래 검 한 자루를 만들려면 그 대장간에서 $t_i$ 분 동안 쉬지 않고 일해야 한다. 검을 미완성 상태로 두었다가 다음 방문 때 이어서 만들 수는 없다.

아비게일이 최적의 계획을 세울 수 있도록 도와서, $n$ 명의 대장 감독 아래에서 만들 수 있는 검의 최대 개수를 구하라.

입력

첫 번째 줄에 대장의 수 $n$ ( $1 \le n \le 200\,000$ )이 주어진다.

이어지는 $n$ 개의 줄에는 각각 세 정수 $a_i$ , $b_i$ , $t_i$ ( $1 \le a_i < a_i + t_i \le b_i \le 10^{18}$ )가 주어진다. 이는 $i$ 번째 대장의 일 시작 시각, 일 종료 시각, 그리고 그 대장의 대장간에서 검 한 자루를 만드는 데 걸리는 시간이다.

출력

아비게일이 최적의 학습 계획으로 만들 수 있는 검의 최대 개수를 출력한다.

예제3

예제 1
입력
```
2
5 7 1
1 9 2
```
예상 출력
```
5
```
예제 2
입력
```
3
1 10 4
6 12 3
9 13 2
```
예상 출력
```
4
```
예제 3
입력
```
3
1 13 4
6 11 2
9 13 3
```
예상 출력
```
4
```