한국이 겨울인 시기, 남반구에 있는 호주에서는 더운 날이 계속되고 있다.

호주에 사는 별리는 D일 동안의 일기예보를 바탕으로 입을 옷의 계획을 세우기로 했다.

i 일째 (1 ≤ i ≤ D)의 최고 기온은 Ti ℃라고 예보되고 있다.

별리는 N 종류의 옷을 가지고 있으며, 여기에는 1에서 N까지 번호가 붙어있다.

옷 j (1 ≤ j ≤ N)는 최고 기온이 Aj ℃ 이상, Bj ℃ 이하의 날에 입기에 적당하다.

또한 각각의 옷에는 '화려함'의 정도가 정수값으로 정해져 있어서 옷 j의 화려함 수치는 Cj 이다.

D일간 각각에 대해 별리는 최고 기온이 예보되었을 때 입는 적당한 옷 중 하나를 입는 옷으로 선택한다.

같은 옷을 여러 번 선택해도 좋고, D 일 동안 한 번도 선택되지 않는 옷이 있을 수도 있다.

비슷한 옷을 연속적으로 입는 것을 가급적 피하려고 생각한 별리는

연속하는 날에 입는 옷의 화려함 차이의 절대값의 합계를 최대한 늘리려고 생각했다.

즉, i 번째 날에 옷 xi를 선택하고,

이 최대값을 구하는 프로그램을 작성하시오.

더운 날들 (Hot days) timer 1s memory 256MB

더운 날들 (Hot days) 1s 256MB