AT_ddcc_2016_final_d シャツの部屋

[problemUrl]: https://atcoder.jp/contests/ddcc2016-final/tasks/ddcc_2016_final_d 太郎君はタンス、洗濯カゴ、ゴミ箱、服屋、コインランドリーがある部屋にいます。 はじめ、タンスと洗濯カゴとゴミ箱は空で、太郎君はシャツを $ 1 $ 枚も持っていません。 太郎君は毎朝、部屋の中にある服屋でシャツを買うことができます。 服屋で売られているシャツは $ N $ 種類あり、それぞれ $ 10^{100} $ 枚あります。 種類 $ i $ のシャツは $ A_i $ 回洗濯すると破れてしまうシャツで、値段は $ B_i $ 円です。 買ったシャツは、即座にタンスに収納されます。 太郎君は毎日、以下のような生活を行います。 - 朝：服屋でシャツを買うことができる。何種類でも何枚でも買ってよい。 - 昼：タンスから $ 1 $ 枚シャツを選んで着る。その後、着たシャツを洗濯カゴに入れる。 - 夜：洗濯するかどうかを選択する。 - 洗濯する場合：$ C $ 円払ってコインランドリーを利用して、洗濯カゴに入っているシャツを全て洗濯する。その後、洗濯によって破れてしまったシャツをゴミ箱に、それ以外のシャツをタンスにしまう。 - 洗濯しない場合：何も起こらない。 今を $ 1 $ 日目の朝として、$ M $ 日目の夜まで太郎君が毎日シャツを着るために必要な資金の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ C $ $ A_1 $ $ B_1 $ $ : $ $ A_N $ $ B_N $

答えを $ 1 $ 行に出力せよ。

### 制約 - $ 1\ ≦\ N\ ≦\ 500 $ - $ 1\ ≦\ M\ ≦\ 10^{9} $ - $ 1\ ≦\ A_i\ ≦\ 500 $ - $ 1\ ≦\ B_i\ ≦\ 10^{9} $ - $ 1\ ≦\ C\ ≦\ 10^{9} $ - $ B_i\ \,\ C $ はどちらも整数 ### Sample Explanation 1 以下のような行動をするのが最適な行動で、このときに必要な資金は $ 6 $ 円です。 - $ 1 $ 日目 - 朝：種類 $ 1 $ の服を $ 1 $ 枚買う。これを服 $ a $ と呼ぶことにする。 - 昼：タンスにある服 $ a $ を着た後、洗濯カゴに入れる。 - 夜：洗濯をしないことを選ぶ。 - $ 2 $ 日目 - 朝：種類 $ 2 $ の服を $ 1 $ 枚買う。これを服 $ b $ と呼ぶことにする。 - 昼：タンスにある服 $ b $ を着た後、洗濯カゴに入れる。 - 夜：洗濯をする。服 $ a $ は破れてしまうためゴミ箱に、服 $ b $ はタンスにしまわれる。 - $ 3 $ 日目 - 朝：何も買わない。 - 昼：タンスにある服 $ b $ を着た後、洗濯カゴに入れる。 - 夜：洗濯をしないことを選ぶ。