문제
한국이 겨울인 시기, 남반구에 있는 호주에서는 더운 날이 계속되고 있다.
호주에 사는 별리는 D일 동안의 일기예보를 바탕으로 입을 옷의 계획을 세우기로 했다.
i 일째 (1 ≤ i ≤ D)의 최고 기온은 Ti ℃라고 예보되고 있다.
별리는 N 종류의 옷을 가지고 있으며, 여기에는 1에서 N까지 번호가 붙어있다.
옷 j (1 ≤ j ≤ N)는 최고 기온이 Aj ℃ 이상, Bj ℃ 이하의 날에 입기에 적당하다.
또한 각각의 옷에는 '화려함'의 정도가 정수값으로 정해져 있어서 옷 j의 화려함 수치는 Cj 이다.
D일간 각각에 대해 별리는 최고 기온이 예보되었을 때 입는 적당한 옷 중 하나를 입는 옷으로 선택한다.
같은 옷을 여러 번 선택해도 좋고, D 일 동안 한 번도 선택되지 않는 옷이 있을 수도 있다.
비슷한 옷을 연속적으로 입는 것을 가급적 피하려고 생각한 별리는
연속하는 날에 입는 옷의 화려함 차이의 절대값의 합계를 최대한 늘리려고 생각했다.
즉, i 번째 날에 옷 xi를 선택하고,
다시말해 |Cx1 - Cx2| + |Cx2 - Cx3| + … + |CxD-1 - CxD|를 최대로 하고 싶다.
이 최대값을 구하는 프로그램을 작성하시오.
입력
첫번째 줄에는 두 개의 정수 D, N (2 ≤ D ≤ 200, 1 ≤ N ≤ 200)이 공백을 구분하여 입력된다. D는 옷을 입는 날수, N은 별리가 가지고 있는 옷의 종류의 수를 나타낸다.
계속되는 D 개의 행 중 i 번째 행(1 ≤ i ≤ D)에는 하나의 정수 Ti (0 ≤ Ti ≤ 60)가 적혀있다. 이것은 i 일 최고 기온이 Ti ℃라고 예보된 것을 나타낸다.
마지막 N 개의 행 중 j 번째 행 (1 ≤ j ≤ N)에는 3 개의 정수 Aj , Bj , Cj (0 ≤ Aj ≤ Bj ≤ 60, 0 ≤ Cj ≤ 100)가 적혀있다. 옷 j는 최고기온이 Aj 도 이상 Bj 도 이하의 날에 입기에 적합하며 화려함이 Cj 임을 나타낸다.
최고기온이 예보되었을 때 입는 적당한 옷이 D일 동안 어떤 날에 대해서도 하나 이상 존재하는 것이 보장되어있다.
출력
연속하는 날에 입는 옷의 화려 함 차이의 절대 값의 합계, 즉 값 | Cx1 - Cx2 | + | Cx2 - Cx3 | + ... + | CxD-1 - CxD |의 최대값을 한 줄에 출력하라.
예제 #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
로그인해야 코드를 작성할 수 있어요.