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

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

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

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

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

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