← 返回题目列表

AtCoder · awc0067_c

C. 杂货店购物

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

分数: 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