문제
가수 케이윌은 위가 좋지 않아서 병원에 가서 진단을 받아 보려고 하지만 병원이 예약제라서 N번째 날(지금이 1번째 날이다)까지는 임시로 다른 방법을 사용하기로 했다. 그 방법은, 위에 좋다는 윌을 마시는 것이다. 윌의 효과는 단순히 그날 케이윌이 마신 윌의 양에 비례한다.
케이윌의 팬들 중 K명의 팬들은 케이윌이 위가 좋지 않다는 것을 알고 케이윌에게 윌을 선물한다. 각 팬마다 Sx번째 날부터 Ex번째 날까지 양이 Wx인 윌을 선물한다. 정인이도 케이윌을 좋아하기 때문에 윌을 선물할 것이다. 그녀는 D일 동안 양이 W인 윌을 선물할 것이다. 정인이는 다른 팬들이 윌을 줄 계획을 모두 알고 있기 때문에, 정인이는 케이윌이 윌을 가장 적게 마시는 날에 마시는 윌의 양이 최대가 되게 윌을 선물할 것이다. 정인이를 도와 언제 윌을 선물해야 하는지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 날의 수 N과 윌을 주는 다른 팬의 수 K가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K ≤ 100,000)
두 번째 줄부터 K개의 줄에는 Sx, Ex, Wx가 주어진다. (1 ≤ Sx ≤ Ex ≤ N, 1 ≤ Wx ≤ 100,000)
마지막 줄에는 정인이가 윌을 선물하는 기간 D와 정인이가 선물하는 윌의 양 W가 주어진다. (1 ≤ D ≤ N, 1 ≤ W ≤ 100,000)
<제약조건>
• 전체 데이터의 25%는 N, K ≤ 1,000이다.
• 전체 데이터의 25%는 D = 1이다.
출력
정인이가 윌을 선물하는 시작일 S와 종료일 E를 출력한다. 1 ≤ S ≤ E ≤ N이며, E-S+1 = N 이여야 한다.
답이 여러 개이면 그중 S가 가장 작은 경우를 출력한다.
계산 과정에서 32-bit integer 범위를 넘어갈 수 있으니 주의하여라.
예제 #1
20 4
1 10 5
1 8 3
10 14 6
15 20 5
7 4
1 7
예제 #2
6 6
1 1 5
2 2 6
3 3 2
4 4 7
5 5 3
6 6 4
5 3
2 6
출처
functionx
로그인해야 코드를 작성할 수 있어요.