문제1986--컵케잌

1986: 컵케잌

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 32  통과: 14
[제출] [채점기록] [묻고답하기]

문제 설명

 

'요둘'족은 컵케잌을 매우 좋아한다. '요둘잡이 덫' 으로 사용하는 미끼에 컵케잌을 놓을 정도로 ‘요둘’족은 컵케잌을 좋아한다. '요둘'족의 '띠모'는 정찰대 소속의 매우 활발한 '요둘'이다. 그에게 내려진 이번 임무는 최근 잘나가는 빵집 'AdbyMe' 에 침투하여 컵케잌 레시피를 탈취해 오는 것이다. 그 동안 '요둘'들이 'AdbyMe'에 대한 침투가 없었던 것은 아니다. 하지만 'AdbyMe' 역시 컵케잌을 이용한 덫을 설치해놨고, '요둘'에게 컵케잌은 덫이라는걸 알아도 벗어날 수 없는 유혹이라, 많은 정찰대원들이 희생되었을 뿐이다.
그러나 '띠모'는 다르다. 그는 정찰대 에이스로서 그 누구보다 강력한 자제력과 전투력, 침투력을 보유한 '요둘'이기 때문이다. 하지만 역시 '요둘'이었다. '띠모'는 최상의 침투루트는 이미 그의 머릿속에 없었다. 얼마나 많은 미끼용 컵케잌들을 자신이 챙겨 나올 수 있을까가 그가 스스로에게 내린 작은 임무였다. '띠모'가 최대한 챙길 수 있는 컵케잌 수를 구해보자.
'띠모'는 직선좌표계 0에서부터 d까지 움직여 'AdbyMe'에 도착하게 된다. 0에서 e까지는 통로가 여러 개 설치되어 있고, 각 통로에는 컵케잌이 들어있는 '요둘잡이 덫' 들이 놓여져 있다. '띠모'는 0에서 출발하여 e까지 덫이 설치된 통로들을 통과하며 최대한 많은 컵케잌을 회수한다. i번째 통로가 입구가 si이고 출구가ei 라면, '띠모'는 이 통로를 통과한 이상, 입구가 ei보다 작은 값을 가지는 통로는 통과할 수 없다. 또한 입구가 ei보다 큰 값을 가진 통로라고 하여 꼭 통과할 필요는 없다. 두 개의 통로를 한번에 통과할 수 없다. 돌아오는 과정은 고려하지 않는다.

입력 설명

 

테스트 케이스 n이 입력된다. (1 ≤ n ≤ 100)
그리고 각 테스트 케이스 마다 도착점 d, 통로 개수 c가 입력된다.
(1 ≤ d ≤1000, 1 ≤ c ≤ 1000000 d, c는 모두 정수)
다음 줄부터 c개 줄에 각 통로의 정보가 입력된다..
n
d c
s1 e1 f1
s2 e2 f2
...
sc ec fc
(si, ei, fi 는 각각 i번째 통로의 입구 좌표, 출구 좌표, 해당 통로의 컵케잌 개수이다.)
(1 ≤ si < ei ≤ d, 1 ≤ fi ≤ 100 모두 정수)

출력 설명

한 줄에 한 개씩 각각의 테스트 케이스에 대한 결과 출력하여라.

입력 예시 Copy

2
10 7
8 10 5
6 8 3
3 10 15
8 9 3
1 5 7
6 7 7
2 5 6
25 13
16 24 14
7 16 10
16 25 11
9 25 19
1 15 10
2 6 6
17 22 10
15 22 7
6 15 13
2 9 12
10 16 7
2 9 10
16 21 2

출력 예시 Copy

19
33

도움

 

ex1) 0 -> (1,5)7 -> (6,7)7 -> (8,10)5
7 + 7 + 5 = 19
ex2) 0 -> (2,6)6 -> (6,15)13 -> (16,24)14
6 + 13 + 14 = 33

출처/분류