1347 : Badminton

Zzz chose two badminton lessons before he realized the consequences that such option would cause a tired body. But Zzz could not change his selections. Having taken above into account, Zzz determined to practice his badminton’s skill with the help of new machine called NQ.
NQ is an intelligent robot invented by IvyHole, it can throw the ball across the net. Thus, Zzz wants to use it to advance his understanding of hitting badminton. According to the settings inside the NQ, it will throw out badminton of different sizes, and each badminton has a certain score. In order to hit the ball back, Zzz will lose some energy value which is equal to the volume of each badminton. At the same time, Zzz has to guarantee that his energy value could not less than zero! To gain the better training effect, Zzz wants to know the maximum score he can get before he runs out of his energy to decide whether to hit the current badminton or not.

The first row of input data includes two integer n, h represented the number of badmintons which will be thrown by NQ and the maximum value of Zzz’s energy. ( 1 ≤ n, h ≤ 1000 )
For the following n rows, each row has two integers v, s, represented every badminton’s volume and score.
( 1 ≤ v ≤ h  1 ≤ s ≤ 107 )

Output one integer represented the best achievements can be achieved.

4 5
1 2
2 4
3 4
4 5

8

逆乾 WIT第二届程序设计竞赛(现场赛)