문제
가수 케이윌은 위가 좋지 않아서 병원에 가서 진단을 받아 보려고 하지만 병원이 예약제라서 N번째 날(지금이 1번째 날이다)까지는 임시로 다른 방법을 사용하기로 했다. 그 방법은, 위에 좋다는 윌을 마시는 것이다. 윌의 효과는 단순히 그날 케이윌이 마신 윌의 양에 비례한다.
케이윌의 팬들 중 K명의 팬들은 케이윌이 위가 좋지 않다는 것을 알고 케이윌에게 윌을 선물한다. 각 팬마다 Sx번째 날부터 Ex번째 날까지 양이 Wx인 윌을 선물한다. 케이윌은 자신의 팬클럽에서 이를 모두 알아버리고 윌의 효과가 가장 적은 날을 알아보고 싶어 한다. 즉, 윌을 가장 적게 마시는 날을 알아보고 싶어 한다. 그러나 케이윌은 인기 있는 만큼 바쁜 몸이므로 그런 것을 계산할 시간이 없다. 코딩을 할 줄 아는 당신이 이를 해결해 주어라.
입력
첫 번째 줄에는 날의 수 N과 윌을 주는 팬의 수 K가 주어진다. (1 ≤ N ≤ 1,000,000,000, 1 ≤ K ≤ 100,000) 두 번째 줄부터 K개의 줄에는 Sx, Ex, Wx 가 주어진다. (1 ≤ Sx ≤ Ex ≤ N, 1 ≤ Wx ≤ 20,000)
출력
케이윌이 윌을 가장 적게 마시는 날의 번호의 최솟값과, 그 때 케이윌이 마시는 윌의 양을 출력하여라. 케이윌이 하루에 마시는 윌의 양은 항상 2,000,000,000 이하이다.
<제약조건> 전체 데이터의 40%는 2 ≤ N ≤ 100,000, 1 ≤ K ≤ 100이다
예제
20 4
1 10 5
1 8 3
10 14 6
15 20 5
9 5
출처
functionx
로그인해야 코드를 작성할 수 있어요.