비자

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

요약

허용 구간이 있는 비자 신청 가운데 일부를 골라 날짜가 겹치지 않게 배정하고 총 지불액을 최대화합니다.

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

문제

누구나 초부유국 SBP로 떠나고 싶어 하지만, 입국하려면 비자가 필요하고 비자는 유료입니다. 가격은 정해져 있지 않습니다. 신청할 때 각 사람이 얼마를 낼 수 있는지 스스로 적어 냅니다. 또한 각 신청서에는 비자를 받아도 되는 날짜 구간, 즉 날짜 구간 $[p, k]$ 를 적습니다. 날짜가 너무 이른 비자는 여행 전에 유효기간이 끝나고, 너무 늦은 비자는 쓸모가 없기 때문입니다.

가격을 높게 유지하기 위해 이민국은 하루에 비자를 최대 한 장만 발급합니다. 모든 신청서는 같은 날 한꺼번에 접수되고, 그중에서 발급 대상이 정해집니다. 신청 자체는 무료이므로 거절되어도 비용이 들지 않습니다.

어떤 신청을 승인한다는 것은 그 신청의 구간 $[p, k]$ 안에서 정확히 하루를 골라 배정하는 것입니다. 하루에 한 장만 발급되므로, 승인된 두 신청서에 같은 날을 배정할 수 없습니다. 승인된 신청서는 적어 낸 금액만큼의 수입을 냅니다.

구간에는 특별한 성질이 있습니다. 임의의 두 신청서에 대해, 한 구간의 시작일이 다른 구간의 시작일보다 엄격히 이르면, 그 구간의 끝일도 다른 구간의 끝일보다 늦지 않습니다. 수식으로 쓰면, $p_i < p_j$ 이면 $k_i \le k_j$ 입니다.

어떤 신청을 승인하고 각각을 며칠에 배정할지 정하여, 걷을 수 있는 총 금액을 최대로 만드세요. 그 최댓값을 출력하면 됩니다.

입력

첫 줄에는 신청서의 수를 나타내는 정수 $n$ ( $1 \le n \le 10000$ )이 주어집니다. 이어지는 $n$ 개의 줄에는 각각 세 정수 $p$ , $k$ , $c$ ( $1 \le p \le k \le 10^9$ , $1 \le c \le 400000$ )가 주어집니다. 이는 해당 신청자가 $p$ 일부터 $k$ 일까지 중 어느 하루에 비자를 받으면 되고, 그 대가로 $c$ 를 낼 수 있다는 뜻입니다. 임의의 두 신청서 $(p_i, k_i)$ 와 $(p_j, k_j)$ 에 대해, $p_i < p_j$ 이면 $k_i \le k_j$ 임이 보장됩니다.

출력

발급된 비자로 걷을 수 있는 최대 총 금액을 한 줄에 출력합니다.

예제5

예제 1
입력
```
4
1 2 10
2 3 11
2 3 5
3 3 13
```
예상 출력
```
34
```
예제 2
입력
```
1
5 5 100
```
예상 출력
```
100
```
예제 3
입력
```
2
1 1 5
2 2 6
```
예상 출력
```
11
```
예제 4
입력
```
3
1 2 10
2 3 8
2 2 3
```
예상 출력
```
21
```
예제 5
입력
```
3
1 2 10
1 2 7
1 2 7
```
예상 출력
```
17
```