In the game Primogem Gacha Impact No. 3, players can spend in-game currency for the chance to obtain any of the game's $N$ characters. However, with the passing of a new law banning the gacha mechanic at Bayview Secondary School, the game has been altered to allow players to deterministically buy characters. Specifically, the $i^{\text{th}}$ character now costs $A_i\times X+B_i$ units of in-game currency to buy, where $X$ is the number of other characters the player owns at the time of purchase.

You want to assemble a team of $M$ different characters, but since you're running low on money to whale, you want to do this for as cheap as possible, regardless of what team you end up with. Given that you can buy the characters in any order, what is the minimum cost to obtain a team of $M$ characters?

Constraints

$1\le M\le N\le 5\times {10}^3$

$1\le A_i,B_i\le {10}^9$

Subtask 1 [30%]

$M=N$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains two integers, $N$ and $M$, the total number of characters in the game and the size of the team you wish to assemble.

The next $N$ lines contain two integers each, $A_i$ and $B_i$.

Output Specification

Output a single integer, the minimum cost to buy a team of $M$ characters.

Sample Input

4 2
1 2
3 2
1 4
2 1

Sample Output

4

Explanation

You can buy the fourth character for a cost of $2\times 0+1=1$, then the first character for a cost of $1\times 1+2=3$. In total, this costs $1+3=4$ units of currency. This is the minimum required to buy two characters.