22815_RollerCoaster

Bessie has gone on a trip, and she's riding a roller coaster! Bessie really likes riding the roller coaster, but unfortunately she often gets dizzy.

The roller coaster has a number of distinct sections that Bessie rides in order. Atthe beginning of the ride, Bessie's dizziness and fun levels are both at 0. For each section of the roller coaster, Bessie can either keep her eyes open or keep them closed (and must keep them that way for the whole section). If she keeps her eyes open for a section, her total fun increases by a Fun factor for that section, and her dizziness increases by a Dizziness factor for that section. However, if she keeps her eyes closed for the section, her total fun will not change, but her dizziness will decrease by a value that's constant for the entire roller coaster. (Note that her dizziness can never go below 0.)

If at any point, Bessie's dizziness is above a certain limit, Bessie will get sick. Write a program to find the maximum amount of fun Bessie can have without getting sick.

Therewill be several test cases in the data file. Each test case will begin with aline with three integers:

N  K  L

where N ( 1 ≤ N ≤ 1000 ) is the number of sections in this particular the roller coaster; K ( 1 ≤ K ≤ 500 ) is the amount that Bessies dizziness level will go down if she keeps her eyes closed on any section of the ride; and L ( 1 ≤ L ≤ 300000 ) is the limit of dizziness that Bessie can tolerate? If her dizziness ever becomes larger than L, Bessie will get sick, and thatsnot fun!

Eachof the next N lines will have two integers:

F  D

where F ( 1 ≤ F ≤ 20 ) is the increase to Bessies total fun that shell get if she keeps her eyes open on that section, and D ( 1 ≤ D ≤ 500 ) is the increase to her dizziness level if she keeps her eyes open on that section. The sections will be listed in order.

The data file will end with a line with three 0s.

For each test case, output line containing asingle integer, representing the maximum amount of fun Bessie can have on that roller coaster without exceeding her dizziness limit.

3 1 2
2 1
3 1
5 2
4 1 1
2 1
3 1
2 2
3 3
0 0 0

7
3