Roller Coaster

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

The roller coaster has a number of distinct sections that Bessie rides in order. At the start of the ride, both her dizziness and her fun are 0. For each section of the roller coaster, Bessie can either keep her eyes open or keep them closed, and she must keep them that way for the whole section.

• If she keeps her eyes open for a section, her total fun increases by that section's fun factor and her dizziness increases by that section's dizziness factor.
• 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 roller coaster. Her dizziness can never go below 0 (if a decrease would take it below 0, it becomes 0).

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

The input contains several test cases. Each test case begins with a line containing three integers:

N K L

where $N$ ($1 \le N \le 1{,}000$) is the number of sections in this roller coaster, $K$ ($1 \le K \le 500$) is the amount Bessie's dizziness goes down if she keeps her eyes closed on any section, and $L$ ($1 \le L \le 300{,}000$) is the dizziness limit Bessie can tolerate — if her dizziness ever becomes larger than $L$, Bessie gets sick.

Each of the next $N$ lines describes one section of the roller coaster and contains two integers:

F D

where $F$ ($1 \le F \le 20$) is the increase to Bessie's total fun if she keeps her eyes open on that section, and $D$ ($1 \le D \le 500$) is the increase to her dizziness if she keeps her eyes open on that section. The sections are listed in ride order. The input ends with a line containing three 0s.

For each test case, output a single integer: the maximum amount of fun Bessie can have on that roller coaster without exceeding her dizziness limit. Print each integer on its own line with no spaces, and do not print any blank lines between answers.