TV 전쟁

면접 대비

시간 제한1초메모리 제한256 MB

요약

겹치지 않게 주간 TV 프로그램을 골라 선호도 합이 가장 커지는 값을 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 정렬, 이분 탐색, 구간
정답자: 아직 제출이 없습니다

문제

집에 티비가 한 대뿐이라 가족이 어떤 프로그램을 볼지 늘 다툰다. 이 다툼을 자동으로 정리해 주는 기계를 만들려고 한다.

한 해 동안 가족이 보려는 프로그램은 이미 정해져 있다. 각 프로그램은 매주 같은 시각에 시작해서 같은 시각에 끝나므로, 한 주 분량의 시청 계획만 세워 두면 1년 내내 그대로 쓰면 된다. 프로그램마다 가족이 매긴 선호도 점수가 있고, 점수가 높을수록 가족이 더 보고 싶어 하는 프로그램이다. 티비가 한 대뿐이라 시간이 겹치는 두 프로그램을 함께 볼 수는 없다.

시청 시간이 서로 겹치지 않게 프로그램을 고를 때, 선호도의 총합이 최대가 되도록 하려고 한다. 그 최댓값을 구하라.

입력

첫 줄에 테스트 케이스의 개수 $t$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 프로그램의 개수 $n$ $(1 \le n \le 100000)$ 이 주어진다. 이어지는 $n$ 개의 줄에는 공백으로 구분된 정수 $s$ , $d$ , $p$ 가 주어진다. $s$ 는 프로그램이 시작하는 시각, $d$ 는 프로그램이 이어지는 시간, $p$ 는 그 프로그램의 선호도이다. $(0 \le s < s+d \le 10080,\ 1 \le p \le 2000)$

$s+d$ 를 $k$ 라고 하면 이 프로그램은 정확히 $k$ 시각에 끝나고, 다른 프로그램을 정확히 $k$ 시각부터 볼 수 있다.

출력

각 테스트 케이스마다 선호도 총합의 최댓값을 한 줄에 출력한다.

힌트

첫 번째 예제에서 시각 $1$ 에 시작해 $4$ 만큼 이어지는 프로그램과 시각 $6$ 에 시작해 $4$ 만큼 이어지는 프로그램을 고르면 선호도의 합이 $6+5=11$ 이고, 이것이 가족이 얻을 수 있는 최댓값이다.

예제5

예제 1
입력
```
1
3
3 8 10
1 4 6
6 4 5
```
예상 출력
```
11
```
예제 2
입력
```
1
1
0 10080 2000
```
예상 출력
```
2000
```
예제 3
입력
```
1
4
0 5 3
1 2 7
2 2 5
0 4 6
```
예상 출력
```
7
```
예제 4
입력
```
1
4
0 2 5
2 2 5
4 2 5
0 6 14
```
예상 출력
```
15
```

예제 5

입력

예상 출력

57
108
62