题目描述
忆艾现在手头有 $n$ 件装备，这些装备目前都是初始状态，我们称之为 $0$ 级，每件装备恰好可以升级两次，第 $i$ 件装备从 $0$ 级升级到 $1$ 级需要 $w_{i,1}$ 枚金币，从第 $1$ 级升级到第 $2$ 级需要 $w_{i,2}$ 枚金币。
忆艾想知道如果她总共给装备升级次数为 $m$，至少需要花费多少枚金币。
输入格式
从标准输入读入数据。
第一行两个正整数 $n, m$ 表示总共的装备数量和需要升级的次数。
接下来共 $n$ 行，每行两个正整数 $w_{i, 1}, w_{i, 2}$ 表示第 $i$ 件装备两次升级分别需要花费的金币。
输出格式
输出到标准输出。
输出一行一个正整数，表示最少需要花费多少枚金币。
样例
输入
5 7
1 3
2 1
2 5
4 2
1 1输出
11解释
选择升级的装备分别是：
- 第一件装备升 2 级。
- 第二件装备升 2 级。
- 第三件装备升 1 级。
- 第五件装备升 2 级。
总共花费的金币是 $(1+3)+(2+1)+2+(1+1)=11$ 枚。
样例二
见下载目录下的 ex_2.in 与 ex_2.ans。
子任务
对于 $100\%$ 的数据，保证 $1\le n \le 5 \times 10^{5}, 1\le m\le 2n, w_{i,j} \le 10^{9}$
| 测试点 | $n$ | 特殊性质 |
|---|---|---|
| 1,2,3 | $\le 3,000$ | 无 |
| 4,5,6 | $\le 10^{5}$ | A |
| 7,8 | B | |
| 9 | 无 | |
| 10 | $\le 5 \times 10^{5}$ |
特殊性质 A：对所有 $i$，满足 $w_{i,1} \ge w_{i,2}$
特殊性质 B：对所有 $i$，满足 $w_{i,1} \le w_{i,2}$
时空限制：1s, 256MB