题目描述

卢卡斯计划成立一家 AI 公司，它需要采购一些芯片，使得这些芯片的算力总和达到 $H$（即算力总和 $\ge H$）。

有 $N$ 家芯片公司，现在用 $1$ 到 $N$ 给它们编号。第 $i$ 家芯片公司生产的每块芯片的算力为 $P_i$，价格为 $C_i$ 元每块。

每家芯片公司的货源都十分充足，可以卖出无限多的芯片。

帮助卢卡斯找到最小的成本来满足需要，即采购的芯片算力总和达到 $H$。

输入格式

第一行，两个整数 $N$ 和 $H$，以空格分隔。

接下来 $N$ 行，每行包含两个整数 $P_i$ 和 $C_i$，以空格分隔。

输出格式

输出一个整数，表示卢卡斯购买的芯片算力总和 $\ge H$ 所需的最少花费。

样例

2 15 
3 2
5 3

9

3 100
70 33
22 15
10 8

56

说明/提示

样例 1 解释

在第 $2$ 家芯片公司购买 $3$ 块芯片。

样例 2 解释

在三家芯片公司各购买 $1$ 块芯片。

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 10$，$p_i, c_i \le 50$，$H \le 500$
• 对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le p_i, c_i \le 5000$，$1 \le H \le 50000$