← 返回题目列表

AtCoder · ddcc_2016_final_d

D. 衬衫房

中文机器翻译题面 查看原题

配点 : 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