题目描述

忆艾现在手头有 $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}$

​

特殊性质 A：对所有 $i$，满足 $w_{i,1} \ge w_{i,2}$

特殊性质 B：对所有 $i$，满足 $w_{i,1} \le w_{i,2}$

时空限制：1s, 256MB