U177859 装备升级（upgrade）

忆艾现在手头有 $n$ 件装备，这些装备目前都是初始状态，我们称之为 $0$ 级，每件装备恰好可以升级两次，第 $i$ 件装备从 $0$ 级升级到 $1$ 级需要 $w_{i,1}$ 枚金币，从第 $1$ 级升级到第 $2$ 级需要 $w_{i,2}$ 枚金币。 忆艾想知道如果她总共给装备升级次数为 $m$，至少需要花费多少枚金币。

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

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

选择升级的装备分别是： * 第一件装备升 2 级。 * 第二件装备升 2 级。 * 第三件装备升 1 级。 * 第五件装备升 2 级。 总共花费的金币是 (1 + 3) + (2 + 1) + 2 + (1 + 1) = 11 枚。 **【子任务】** 对于 $100\%$ 的数据，保证 $1 ≤ n ≤ 5 × 10^5$ , $1 ≤ m ≤ 2n,w_{i, j} ≤ 10^9$  特殊性质 A：对所有 $i$，满足 $w_{i,1}$ ≥ $w_{i,2}$ 特殊性质 B：对所有 $i$，满足 $w_{i,1}$ ≤ $w_{i,2}$