Roller Coaster#1385
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 consists of several distinct sections that Bessie rides in order. At the beginning of the ride, Bessie's dizziness and fun levels are both at . For each section of the roller coaster, Bessie can either keep her eyes open or 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 the Fun factor for that section, and her dizziness increases by the Dizziness factor for that section. However, if she keeps her eyes closed for a section, her total fun does not change, but her dizziness decreases by a value that is constant for the entire ride. (Note that her dizziness can never drop below .)
If at any point Bessie's dizziness exceeds a certain limit, Bessie will get sick. Write a program to determine the maximum amount of fun Bessie can have on the roller coaster without getting sick.
The input contains several test cases. Each test case begins with a line with three integers:
N K L
Where (1 \leq N \leq 1000) is the number of sections in the roller coaster, (1 \leq K \leq 500) is the amount by which Bessie's dizziness decreases if she keeps her eyes closed in a section, and (1 \leq L \leq 300000) is the maximum dizziness Bessie can tolerate. If her dizziness ever exceeds , Bessie will get sick.
Each of the next lines describes a section of the roller coaster. Each line contains two integers:
F D
Where (1 \leq F \leq 20) is the increase to Bessie's total fun if she keeps her eyes open for this section, and (1 \leq D \leq 500) is the increase to her dizziness if she keeps her eyes open for this section. The sections are provided in order. The input ends with a line with three 's.
For each test case, output a single integer representing the maximum amount of fun Bessie can have without exceeding her dizziness limit. Print each integer on its own line with no spaces. Do not print any blank lines between answers.
Example 1