Yi Ai currently has $n$ pieces of equipment, all of which are in their initial state, which we call level $0$. Each piece of equipment can be upgraded exactly twice. For the $i$-th piece of equipment, upgrading from level $0$ to level $1$ costs $w_{i,1}$ gold coins, and upgrading from level $1$ to level $2$ costs $w_{i,2}$ gold coins.

Yi Ai wants to know the minimum number of gold coins required to perform a total of $m$ upgrades across her equipment.

Input

The input is read from standard input.

The first line contains two positive integers $n$ and $m$, representing the total number of equipment pieces and the total number of upgrades required.

The next $n$ lines each contain two positive integers $w_{i, 1}$ and $w_{i, 2}$, representing the costs of the two upgrades for the $i$-th piece of equipment.

Output

The output is written to standard output.

Output a single positive integer representing the minimum number of gold coins required.

Examples

Input 1

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

Output 1

11

Note 1

The chosen upgrades are:

• Upgrade the first piece of equipment to level 2.
• Upgrade the second piece of equipment to level 2.
• Upgrade the third piece of equipment to level 1.
• Upgrade the fifth piece of equipment to level 2.

The total cost is $(1+3)+(2+1)+2+(1+1)=11$ gold coins.

Input 2

See ex_2.in and ex_2.ans in the download directory.

Subtasks

For $100\%$ of the data, it is guaranteed that $1\le n \le 5 \times 10^{5}, 1\le m\le 2n, w_{i,j} \le 10^{9}$.

Special Property A: For all $i$, $w_{i,1} \ge w_{i,2}$ holds.

Special Property B: For all $i$, $w_{i,1} \le w_{i,2}$ holds.