/
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君はこれから D 日間の食事を賄うために、食料を買い出しに行くことにしました。
高橋君の近所には N 個の店があります。i 番目の店 (1 \leq i \leq N) では食料パックが売られており、1 個あたりの価格は C_i 円、1 個で 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
- 1 行目には、店の数を表す整数 N と、賄うべき日数を表す整数 D が、スペース区切りで与えられる。
- 続く N 行のうち i 行目 (1 \leq i \leq N) には、i 番目の店の食料パック 1 個の価格 C_i と、それで賄える日数 F_i が、スペース区切りで与えられる。
出力
D 日以上の食事を賄うために必要な最小の合計金額を 1 行で出力せよ。
入力例 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
Score : 366 pts
Problem Statement
Takahashi is going grocery shopping to cover his meals for the next D days.
There are N stores in Takahashi's neighborhood. The i-th store (1 \leq i \leq N) sells food packs, each costing C_i yen and covering F_i days' worth of meals.
Takahashi can use any combination of stores and purchase any number of food packs from each store (including 0). Find the minimum total cost required so that the total number of days covered by the purchased food packs is at least D. Note that it is acceptable if the total number of days exceeds D.
Constraints
- 1 \leq N \leq 3000
- 1 \leq D \leq 3000
- 1 \leq C_i \leq 10^6
- 1 \leq F_i \leq 10^4
- All input values are integers.
Input
N D C_1 F_1 C_2 F_2 \vdots C_N F_N
- The first line contains an integer N representing the number of stores and an integer D representing the number of days to cover, separated by a space.
- The following N lines each describe a store: the i-th line (1 \leq i \leq N) contains the price C_i of one food pack at the i-th store and the number of days F_i it covers, separated by a space.
Output
Print on a single line the minimum total cost required to cover at least D days' worth of meals.
Sample Input 1
3 5 3 2 4 3 10 6
Sample Output 1
7
Sample Input 2
2 5 6 4 5 3
Sample Output 2
10
Sample Input 3
7 23 14 4 27 8 33 10 5 1 60 18 90 30 22 7
Sample Output 3
76
Sample Input 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
Sample Output 4
682
Sample Input 5
1 3000 1000000 1
Sample Output 5
3000000000