憶艾現在手頭有 $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輸出
11說明
選擇升級的裝備分別是：
- 第一件裝備升 2 級。
- 第二件裝備升 2 級。
- 第三件裝備升 1 級。
- 第五件裝備升 2 級。
總共花費的金幣是 $(1+3)+(2+1)+2+(1+1)=11$ 枚。
範例 2
見下載目錄下的 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}$