메뉴 건너뛰기

문제

00c17 더운 날들 0  

시간메모리제출 올바른 답 비율
1초64MB
43
7
16.3%


나의 횟수나의 최근 판정시도 성공 비율
167
43.8%
더운 날들  

무더운 여름이 지속되고 있는 가운데 패션 감각이 뛰어난 KOI 군은 D일 간의 일기 예보를 토대로 어떤 옷을 입고 외출할지에 대해 계획하고자 한다. KOI군은 D일 동안의 외출에서 동일한 옷을 여러 번 입을 수 있으며, 한 번도 입지 않는 옷이 있을 수 있다.

i일째(1<=i<=D)의 최고 기온은 Ti도라고 예보되어 있다. KOI군은 N개의 옷을 가지고 있으며, 옷에는 1부터 N까지의 일련번호가 붙어있다. 그리고 옷 \(j(1 \leq j \leq N)\)는 최고 기온 \(A_j\)도 이상 \(B_j\)도 이하의 날씨에 적당하기 때문에 \(i\)일의 최고 기온 \(T_i\)에 적합한 옷을 선택해야 한다.

각각의 옷에는 ‘화려함’을 나타내는 정수가 정해져 있는데, 옷 \(j\)의 화려함은 \(C_j\)이다. 비슷한 화려함의 옷을 연속적으로 입는 것을 가급적 피하려고 계획 중인 KOI 군은 연속하는 날에 입는 옷의 화려함 차이의 절대값의 합계를 최대한 늘리려고 한다. 즉, \(|C_1-C_2| + |C_2-C_3| + ... + |C_{D-1}-C_D|\)이 최대가 되도록 계획하고자 한다. 이 최대값을 출력하는 프로그램을 작성하시오.

입력

입력파일의 첫 번째 줄에는 두 개의 정수 \(D, N(2 \leq D \leq, 1 \leq N \leq 200)\)이 공백을 사이에 두고 주어진다. \(D\)는 옷의 계획 일수, \(N \)은 KOI군이 가지고 잇는 옷의 개수를 나타낸다. 다음의 \(D\)개 줄에는 i일째의 최고 기온 \(T_i(0 \leq T_i \leq 60)\)가 주어진다. \(T_i \)\(i\)일의 일기 예보상 최고 기온을 나타낸다. 그 다음의 \(N\)개의 줄에는 옷 \(j\)에 대한 3개의 정수 \(A_j, B_j, C_j (0 \leq A_j \leq B_j \leq 60, 0 \leq C_j \leq 100)\)가 주어진다. 이것은 옷 \(j\)가 최고 기온이 \(A_j\)도 이상, \(B_j\)도 이하의 날씨에 입기 적합하며 화려함이 \(C_j\)임을 나타낸다. 그리고 \(D\)일 동안 각 날씨의 최고 기온에 입기 적합한 옷이 하나 이상 존재한다.

출력

첫 번째 줄에 연속하는 날에 입는 옷의 화려함 차이의 절대값의 합계, 즉, \(|C_1-C_2| + |C_2-C_3| + ... + |C_{D-1}-C_D|\)의 최대값을 출력한다.

 

※ 예시 1 : 예보된 날씨의 최고 기온에 따라 1일째는 옷3, 옷4을 입을 수 있고, 2일째는 옷2 옷3을 입을 수 있으며, 3일째는 옷3만 가능하다. 그러나 1일째 옷4, 2일째 옷2, 3일째 옷3을 선택해야 \(| 40 - 90 | + | 90 - 60 | = 30\) 이 되고 이것이 최대값이다.

※ 예시 2 : 1일째 옷2, 2일째 옷2, 3일째 옷1, 4일째 옷2, 5일째 옷1을 선택해야 \(| 100 - 100 | + | 100 - 0 | + | 0 - 100 | + | 100 - 0 | = 300 \)이 되고 이것이 최대값이다.

예시
1입력
3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40
출력
80
2입력
5 2
26
28
32
29
34
30 35 0
25 30 100
출력
300
위로