#1986 컵케잌

12  1 s   128 MB  

Description

 

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

Input

 

테스트 케이스 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 모두 정수)

Output

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

Sample Input

Sample Output

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
19
33

HINT

 

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

Source

2012 Ajou Programming Contest, Division 1