忆艾は現在 $n$ 個の装備を持っており、これらの装備はすべて初期状態（レベル $0$）です。各装備はちょうど $2$ 回までアップグレードでき、第 $i$ 番目の装備をレベル $0$ からレベル $1$ にアップグレードするには $w_{i,1}$ 枚の金貨が、レベル $1$ からレベル $2$ にアップグレードするには $w_{i,2}$ 枚の金貨が必要です。

装備のアップグレード回数の合計が $m$ 回であるとき、必要な金貨の最小枚数を求めてください。

入力

標準入力からデータを読み込みます。

一行目に、$2$ つの正整数 $n, m$ が与えられます。これは装備の総数と必要なアップグレード回数を表します。

続く $n$ 行には、各行に $2$ つの正整数 $w_{i, 1}, w_{i, 2}$ が与えられます。これは第 $i$ 番目の装備の $2$ 回のアップグレードにそれぞれ必要な金貨の枚数を表します。

出力

標準出力に出力します。

必要な金貨の最小枚数を表す正整数を一行に出力してください。

入出力例

入力 1

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

出力 1

11

注記

アップグレードする装備の選択は以下の通りです：

• 第 $1$ 番目の装備を $2$ レベルアップさせる。
• 第 $2$ 番目の装備を $2$ レベルアップさせる。
• 第 $3$ 番目の装備を $1$ レベルアップさせる。
• 第 $5$ 番目の装備を $2$ レベルアップさせる。

合計で消費する金貨は $(1+3)+(2+1)+2+(1+1)=11$ 枚です。

入力 2

ダウンロードディレクトリ内の ex_2.in と ex_2.ans を参照してください。

小課題

すべてのデータにおいて、$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}$ を満たす。