롤러코스터

베시(Bessie)가 여행을 떠나 롤러코스터를 타고 있습니다! 베시는 롤러코스터 타는 것을 정말 좋아하지만, 안타깝게도 자주 어지러움을 느낍니다.

이 롤러코스터는 여러 개의 서로 다른 구간으로 이루어져 있고, 베시는 이 구간들을 순서대로 지나갑니다. 출발할 때 베시의 어지러움 수치와 재미 수치는 모두 0입니다. 각 구간에서 베시는 눈을 뜨거나 감을 수 있으며, 한 구간 동안에는 그 상태를 계속 유지해야 합니다.

• 어떤 구간에서 눈을 뜨면, 그 구간의 재미 값만큼 총 재미가 늘어나고 그 구간의 어지러움 값만큼 어지러움이 늘어납니다.
• 어떤 구간에서 눈을 감으면, 총 재미는 변하지 않지만 어지러움이 롤러코스터 전체에 걸쳐 정해진 일정한 값만큼 줄어듭니다. 단, 어지러움 수치는 절대 0 미만이 될 수 없습니다(0 미만으로 내려가게 되면 0이 됩니다).

만약 어느 순간이라도 베시의 어지러움이 정해진 한계를 넘으면 베시는 멀미를 하게 됩니다. 베시가 멀미하지 않으면서 얻을 수 있는 최대 재미를 구하세요.

입력에는 여러 개의 테스트 케이스가 있습니다. 각 테스트 케이스는 세 정수가 있는 줄로 시작합니다.

N K L

여기서 $N$ ($1 \le N \le 1{,}000$)은 이 롤러코스터의 구간 수, $K$ ($1 \le K \le 500$)는 어떤 구간에서 눈을 감았을 때 어지러움이 줄어드는 양, $L$ ($1 \le L \le 300{,}000$)은 베시가 견딜 수 있는 어지러움 한계입니다. 어지러움이 $L$보다 커지는 순간 베시는 멀미를 합니다.

다음 $N$개의 줄은 각각 한 구간을 설명하며 두 정수를 담고 있습니다.

F D

여기서 $F$ ($1 \le F \le 20$)는 그 구간에서 눈을 떴을 때 늘어나는 재미, $D$ ($1 \le D \le 500$)는 그 구간에서 눈을 떴을 때 늘어나는 어지러움입니다. 구간은 타는 순서대로 주어집니다. 입력은 세 개의 0이 있는 줄로 끝납니다.

각 테스트 케이스마다, 베시가 어지러움 한계를 넘지 않으면서 얻을 수 있는 최대 재미를 정수 하나로 출력하세요. 각 정수는 공백 없이 한 줄에 출력하고, 답 사이에 빈 줄을 넣지 마세요.