0870 - パンケーキ射的

問題

パンケーキは一定量水を蓄えると崩壊する。この性質を利用して水鉄砲を使ってパンケーキを崩壊させる射的が作られた。
この射的は1回でkリットルの水を発射できる水鉄砲でm回パンケーキを撃つことができる。
的になるパンケーキはn個あり並べられている。i番目のパンケーキx_iリットル水を蓄えると崩壊し崩壊させるとt_i点得点が入る。
パンケーキは自ら水を蓄えようとするので狙ったパンケーキに百発百中させることができる。
パンケーキの情報と撃てる回数と水鉄砲が1回発射する水の量が与えられた時の得点の最大を出力するプログラムを作成せよ。
1回の発射で狙えるパンケーキは1個だけで、パンケーキは全て最初は0リットルの水えを蓄えているものとする。

入力

n m k
x0 t0
: :
: :
xi ti

1 行目にパンケーキの数nと水鉄砲が撃てる回数mと水鉄砲が1回で撃てる水の量kが与えられる。

2 行目からn+1行目までパンケーキが崩壊する水の量x_iと得点t_iが与えられる。

出力

射的でとれる得点の最大値を1行で出力せよ。出力の最後に改行を入れること。

制約

1≦n≦100
1≦m≦10000
1≦k≦100
1≦x_i≦10000
1≦t_i≦100

---

入出力例

入力例1

4 5 10
30 2
20 1
40 3
20 2

出力例1

4

入力例2

6 7 11
14 3
21 6
1 1
12 7
48 9
30 5

出力例2

18