暂无测试数据。

背景

• Idea: 北京市赛
• Data: 暂无
• Std: 北京市赛
• 题面: 北京市赛+oistream

描述

忆艾现在手头有 \(n\) 件装备，这些装备目前都是初始状态，我们称之为 \(0\) 级，每件装备恰好可以升级两次，第 \(i\) 件装备从 \(0\) 级升级到 \(1\) 级需要 \(w_{i,1}\) 枚金币，从第 \(1\) 级升级到第 \(2\) 级需要 \(w_{i,2}\) 枚金币。

忆艾想知道如果她总共给装备升级次数为 \(m\)，至少需要花费多少枚金币。

输入格式

• 第一行两个正整数 \(n,m\) 表示总共的装备数量和需要升级的次数。
• 接下来共 \(n\) 行，每行两个正整数 \(w_{i,1},w_{i,2}\) 表示第 \(i\) 件装备两次升级分别需要花费的金币。

输出格式

输出一行一个正整数，表示最少需要花费多少枚金币。

样例

输入样例1

5 7
1 3
2 1
2 5
4 2
1 1

输出样例1

11

样例解释1

选择升级的装备分别是：

• 第一件装备升 \(2\) 级。
• 第二件装备升 \(2\) 级。
• 第三件装备升 \(1\) 级。
• 第五件装备升 \(2\) 级。

总共花费的金币是 \((1+3)+(2+1)+2+(1+1)=11\) 枚。

输入样例2

见附加文件。

输出样例2

见附加文件。

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1\leq n\leq 5\times 10^5,1\leq m\leq 2\times n,w_{i,j}\leq 10^9\)。

• 特殊性质 \(\text{A}\)：对所有 \(i\)，满足 \(w_{i,1}\geq w_{i,2}\)。
• 特殊性质 \(\text{B}\)：对所有 \(i\)，满足 \(w_{i,1}\leq w_{i,2}\)。