한 시간이면 끝낼 수 있는 여러 작업이 주어지고 이 작업의 마감시간과 이익이 할당되어 있다.

목표는 총이익이 최대가 되게 작업의 스케쥴을 짜는 것이다. 모든 작업을 스케쥴에 포함시켜야 하는 것은 아니고 마감시간 전에 일을 끝 마쳐야 주어지는 이익을 얻을수가 있다.

'작업 1 의 마감시간이 2 이다' 란 의미는

작업 1 을 시점 1 에서 시작하여 작업을 끝낼수도 시점 2 에서 시작하여 작업을 끝낼수도 있다

1 번 작업과 3 번 작업은 같은 마감시간이 2 지만, 한 작업은 시점 1 에서 가능하고 , 남은 한 작업은 시점 2 에서 가능하므로 같이 계획 할 수 있지만, 작업 2 와 작업 4 는 같이 계획할 수 없다. 작업시간의 시작은 1 이다.

이 때의 최대 이익은 1 번작업과 4 번작업을 계획하는 것이 70 으로 최대이다.

입력

입력의 끝은 EOF 이다.

출력

입출력 예

입력

2 30
1 30
2 25
1 40

출력

70