진욱이는 열심히 일하는 장난감 공장의 직원이다.

실제로 진욱이는 앞으로 다가올 N(1≤N≤1,000,000)시간(편의상 시간구간은 순서대로 0부터 N-1의 번호를 붙인다.)

동안 최대한 많은 장남감을 만들고자 한다.

공장장인 동훈이는 M(1≤M≤1,000)개의 서로 겹칠 수 있는 장난감을 만들 수 있는 시간 목록을 가지고 있다.

매 구간은 시작시간(0이상 N-1이하), 종료 시간(시작시간보다 크고 N 이하)과

해당 구간내에서 그 구간 동안 몇 개의 장난감을 만들 수 있는 효율(1이상 1,000,000이하)이 주어지며,

동훈이는 진욱이에게 구간의 시작 시간에 장난감 만들기를 시작하도록 지시할 수 있고,

종료 시간에 장난감 만들기를 종료하도록 지시 할 수 있다.

그 외의 시간에는 명령하지 못하며, 진욱이는 시작한 구간 내에서만 장난감을 만들 수 있다.

하지만 진욱이도 인간이기 때문에,

장난감을 만드는 구간이 종료 되면 반드시 최소한 R(1≤R≤N)분의 시간을 쉬어야 장난감을 만들 수 있다.

만약 5분에 일을 마치고 5분을 쉬어야 한다면, 진욱이는 10분부터 다시 작업을 시작할 수 있게 된다.

동훈이가 가진 구간의 정보가 주어졌을 때 진욱이가 제작 가능한 최대한의 장난감 개수를 알아보는 프로그램을 작성해보자.

장난감 생산 timer 1s memory 128MB

장난감 생산 1s 128MB