問題文

1つの古びたバッグがあります。このバッグには大きさ$H$の穴が開いており、 このバッグに入れる荷物の大きさの和は、$W$以下でなければなりません。

このバッグには次のような性質があります。

• 穴がふさがっていない状態で、穴の大きさ以下の大きさの荷物を入れると、荷物が穴から落下する。

• 穴の大きさより大きい荷物を入れると、穴はふさがり、以降、どんな大きさの荷物を入れても荷物が穴から落下することはない。

現在、机の上には$N$個の荷物が積まれており、上から$\ i\ (1 \leq i \leq N)$番目の荷物の大きさは$w_i$、価値は$v_i$です。

荷物を上から順番に、捨てるか、バッグに入れるかを選択するとき、バッグに入れることのできる荷物の価値の総和の最大値を求めて下さい。 ただし、価値の総和には、捨てた荷物や穴から落下した荷物の価値は含まれません。

制約

入力は全て整数
$1\leq N \leq 2\times 10^3$
$1\leq H \leq 2\times 10^3$
$1\leq W \leq 2\times 10^3$
$1\leq w_i,v_i\leq 2\times 10^3$

入力

$N \ H \ W$
$w_1 \ v_1$
...
$w_N \ v_N$

出力

価値の総和の最大値を出力して下さい。

サンプル

8 10 50
1 10
11 5
5 6
3 2
9 7
10 2
8 1
7 10

32