配点 : 1000 点
問題文
太郎所在的房间里有梳妆台、洗衣篮、垃圾桶、服装店和投币式洗衣机。 起初,梳妆台、洗衣篮、垃圾桶都是空的,太郎还穿着衬衫。 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 都是整数
入力
输入将以以下形式从标准输入给出。
N M C A_1 B_1 : A_N B_N
出力
答案 1 行输出。 从
入力例 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