AT_awc0001_d 街道の商人

高橋君は東西に伸びる街道沿いで商売をしている商人です。この街道には $ N $ 個の町が一列に並んでおり、西から順に $ 1 $ 番目、 $ 2 $ 番目、...、 $ N $ 番目と番号が付けられています。 $ i $ 番目の町で商売をすると $ A_i $ の利益が得られますが、滞在費として $ B_i $ 円かかります。 高橋君は、これらの町の中からいくつかを選んで商売をすることにしました。ただし、高橋君の馬車には以下の制限があります。 - 訪れる町は、番号が連続している必要はないが、訪れる町の番号を小さい順に並べたとき、隣り合う番号の差がすべて $ K $ 以下でなければならない。つまり、訪れる町の番号を小さい順に $ p_1, p_2, \ldots, p_m $ としたとき、すべての $ 1 \leq j \leq m - 1 $ について $ p_{j+1} - p_j \leq K $ が成り立つ必要がある。これは、馬車が一度に移動できる距離に限界があるためである。 高橋君が用意できる滞在費の総額は $ M $ 円です。訪れる町の滞在費の合計が $ M $ 円以下となるように町を選ぶとき、得られる利益の合計の最大値を求めてください。 なお、どの町も訪れない場合、利益の合計は $ 0 $ とします。

> $ N $ $ M $ $ K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_N $ $ B_N $ - $ 1 $ 行目には、町の数を表す $ N $ 、用意できる滞在費の総額を表す $ M $ 、一度に移動できる町の数の上限を表す $ K $ が、スペース区切りで与えられる。 - $ 2 $ 行目から $ N + 1 $ 行目では、各町の情報が与えられる。 - $ 1 + i $ 行目では、 $ i $ 番目の町で得られる利益 $ A_i $ と滞在費 $ B_i $ が、スペース区切りで与えられる。

条件を満たすように町を選んだとき、得られる利益の合計の最大値を $ 1 $ 行で出力せよ。

### Constraints - $ 1 \leq N \leq 200 $ - $ 1 \leq M \leq 200 $ - $ 1 \leq K \leq N $ - $ 1 \leq A_i \leq 10^9 $ - $ 1 \leq B_i \leq M $ - 入力はすべて整数