#P1111. 【挑战题】买干草

【挑战题】买干草

题目描述

约翰的干草库存已经告罄,他打算为奶牛们采购 H(1H50000)H(1 \leq H \leq 50000) 磅干草。

他知道 N(1N100)N(1 \leq N\leq 100) 个干草公司,现在用 11NN 给它们编号。第 ii 公司卖的干草包重量为 Pi(1Pi5,000)P_i (1 \leq P_i \leq 5,000) 磅,需要的开销为 Ci(1Ci5,000)C_i (1 \leq C_i \leq 5,000) 美元。每个干草公司的货源都十分充足, 可以卖出无限多的干草包。

帮助约翰找到最小的开销来满足需要,即采购到至少 HH 磅干草。

输入格式

* 第一行包含两个整数: NNHH

* 第2行到第n+1行: 第i+1行 包含两个整数 P_iP\_iC_iC\_i

输出格式

一个整数表示最小的开销来满足需要,即采购到至少 HH 磅干草。

样例 #1

样例输入 #1

2 15 
3 2 
5 3

样例输出 #1

9