問題文

太郎君はタンス、洗濯カゴ、ゴミ箱、服屋、コインランドリーがある部屋にいます。 はじめ、タンスと洗濯カゴとゴミ箱は空で、太郎君はシャツを 1 枚も持っていません。

太郎君は毎朝、部屋の中にある服屋でシャツを買うことができます。 服屋で売られているシャツは N 種類あり、それぞれ 10^{100} 枚あります。 種類 i のシャツは A_i 回洗濯すると破れてしまうシャツで、値段は B_i 円です。 買ったシャツは、即座にタンスに収納されます。

太郎君は毎日、以下のような生活を行います。

• 朝：服屋でシャツを買うことができる。何種類でも何枚でも買ってよい。
• 昼：タンスから 1 枚シャツを選んで着る。その後、着たシャツを洗濯カゴに入れる。
• 夜：洗濯するかどうかを選択する。
  • 洗濯する場合：C 円払ってコインランドリーを利用して、洗濯カゴに入っているシャツを全て洗濯する。その後、洗濯によって破れてしまったシャツをゴミ箱に、それ以外のシャツをタンスにしまう。
  • 洗濯しない場合：何も起こらない。

今を 1 日目の朝として、M 日目の夜まで太郎君が毎日シャツを着るために必要な資金の最小値を求めてください。

制約

• 1 ≦ N ≦ 500
• 1 ≦ M ≦ 10^{9}
• 1 ≦ A_i ≦ 500
• 1 ≦ B_i ≦ 10^{9}
• 1 ≦ C ≦ 10^{9}
• B_i \, C はどちらも整数

入力例 1

2 3 1
1 2
2 3

出力例 1

6

以下のような行動をするのが最適な行動で、このときに必要な資金は 6 円です。

• 1 日目
  • 朝：種類 1 の服を 1 枚買う。これを服 a と呼ぶことにする。
  • 昼：タンスにある服 a を着た後、洗濯カゴに入れる。
  • 夜：洗濯をしないことを選ぶ。
• 2 日目
  • 朝：種類 2 の服を 1 枚買う。これを服 b と呼ぶことにする。
  • 昼：タンスにある服 b を着た後、洗濯カゴに入れる。
  • 夜：洗濯をする。服 a は破れてしまうためゴミ箱に、服 b はタンスにしまわれる。
• 3 日目
  • 朝：何も買わない。
  • 昼：タンスにある服 b を着た後、洗濯カゴに入れる。
  • 夜：洗濯をしないことを選ぶ。

入力例 2

15 551 34
7 78
24 9
7 20
23 17
22 64
3 37
5 18
14 11
1 16
23 43
19 51
2 4
14 11
23 44
21 78

出力例 2

788

入力例 3

1 1000000000 1000000000
1 1000000000

出力例 3

1000000000000000000