Roller Coaster

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

The roller coaster is made up of several distinct sections, which Bessie rides in order. At the start of the ride, both Bessie's dizziness and fun are 0. For each section, Bessie can keep her eyes either open or closed, and she must hold that choice 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 fun does not change, but her dizziness decreases by a value that is fixed for the whole roller coaster. (Her dizziness can never drop below 0.)

If at any moment Bessie's dizziness rises above a certain limit, she gets sick. Write a program to 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 of three integers.

N K L

• $N$ ($1 \le N \le 1{,}000$): the number of sections in this roller coaster
• $K$ ($1 \le K \le 500$): the amount Bessie's dizziness decreases when she keeps her eyes closed on a section
• $L$ ($1 \le L \le 300{,}000$): the dizziness limit Bessie can tolerate. If her dizziness ever exceeds $L$, she gets sick.

Each of the next $N$ lines contains two integers.

F D

• $F$ ($1 \le F \le 20$): the fun gained if she keeps her eyes open on that section
• $D$ ($1 \le D \le 500$): the dizziness gained if she keeps her eyes open on that section

The sections are given in order. The input ends with a line containing three 0s, which should not be processed.

For each test case, output a single integer on its own line: the maximum amount of fun Bessie can have without exceeding her dizziness limit.