分数: 366 分
问题陈述
高桥要去杂货店购买下一顿饭 高桥附近的 D 天。
有 N 商店。的 i第商店 (1 \leq i \leq N) 出售食品包,每个费用 C_i 日元和覆盖物 F_i 几天的膳食。
高桥可以使用任意商店组合,并从每个商店购买任意数量的食物包(包括 0)。求出所需的最低总成本,使得所购买的食品包所涵盖的总天数至少为 D。请注意,如果总天数超过则可以接受 D.
约束
- 1 \leq N \leq 3000
- 1 \leq D \leq 3000
- 1 \leq C_i \leq 10^6
- 1 \leq F_i \leq 10^4
- 所有输入值均为整数。
输入
N D C_1 F_1 C_2 F_2 \vdots C_N F_N
- 第一行包含一个整数 N 代表商店数量和一个整数 D 代表要覆盖的天数,以空格分隔。
- 以下 N 行每行描述一个商店: i第行 (1 \leq i \leq N) 包含价格 C_i 一个食品包 i第商店和天数 F_i 它覆盖,并用空格分隔。
输出
在一行上打印至少覆盖所需的最低总成本 D 几天的膳食。
示例输入 1
3 5 3 2 4 3 10 6
示例输出 1
7
示例输入 2
2 5 6 4 5 3
示例输出 2
10
示例输入 3
7 23 14 4 27 8 33 10 5 1 60 18 90 30 22 7
示例输出 3
76
示例输入 4
15 120 120 20 75 12 40 6 210 35 18 2 95 15 130 22 52 8 300 50 11 1 160 27 68 11 500 90 260 44 33 5
示例输出 4
682
示例输入 5
1 3000 1000000 1
示例输出 5
3000000000