JOI 2012/2013 예선 4- 더운 날들 (Hot days) > 문제은행 : 정보올림피아드&알고리즘




2949 : 더운 날들 (Hot days)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
37 회   
시도횟수
113 회   

문제

윤기는 학교에 관심 있는 누군가(?)가 생겼기 때문에, D일동안(1일~D일) 입을 옷을 계획하기로 했다. 옷의 스타일과 최고 기온은 매우 밀접한 관계가 있기 때문에, 윤기는 D일 동안 일기 예보를 바탕으로 계획을 세우려고 한다. i일의 최고 기온은 Ti이다.

 

윤기는 총 N가지 옷을 가지고 있고, 이 옷은 모두 1번에서 N까지 번호가 붙여져 있다. 옷 j(1 ≤ j ≤ N)는 최고 기온이 Aj 이상 Bj 이하인 날에만 입을 수 있다. 또, 각 옷의 화려한 정도는 Cj이다.

 

윤기는 일기예보를 참고해 어느 날 어떤 옷을 입을지 결정하려고 한다. 같은 옷을 여러 번 입어도 되고, 한 번도 입지 않은 옷이 있어도 상관없다.

비슷한 옷을 연속해서 입는다면, 그 사람이 윤기에게 호감을 느끼지 않을 수 있다. 따라서, 옷의 화려함의 차이의 합이 최대가 되도록 옷을 입으려고 한다. 즉, i일에 옷 xi을 입었다면, |Cx1 - Cx2| + |Cx2 - Cx3| + ... + |CxD-1 - CxD|를 최대로 하려고 한다.

 

화려함의 차이의 합의 최대값을 구하는 프로그램을 작성하시오.

 

입력 예를 보면
1일에 옷 4, 2일에 옷 2, 3일에 옷 3을 입는다면, 절대값의 차이는 |40 - 90| + |90 - 60| = 80이 되고, 이 값이 최대값이다.

 


입력형식

첫 행에 D와 N이 주어진다. (2 <= D, N <= 200) 다음 D개 줄에는 i일의 의 최고 기온 Ti가 주어진다. (0 <= Ti <= 60) 다음 N개 줄에는 윤기가 가지고 있는 옷의 정보가 주어진다. (0 <= Aj <= Bj <= 60, 0 <= Cj <= 100) 윤기가 입을 수 있는 옷이 없는 날은 없다.

출력형식

첫 행에 윤기가 입는 옷의 화려함의 차이의 합의 최대값을 출력한다.

입력 예

3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40

출력 예

80


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP