Lem0nad3's Bar

Geunsu has solved countless problems and is exhausted, so he goes into a lemonade bar to rest.

The bar has $N$ lemonades. Lemonade $i$ comes out at time $t_i$ with a fizz level of $x_i$. The carbonation fades as time passes, so the fizz level drops by 1 for every unit of time. At time $T$ ($T \ge t_i$), the fizz level of lemonade $i$ is $x_i - (T - t_i)$.

Geunsu has a thirst level of $K$, so he can drink at most $K$ lemonades. A lemonade drunk while thirsty gives more happiness. The first lemonade he drinks gives happiness equal to $K$ times its fizz level. The second gives $K-1$ times its fizz level, and the $i$-th lemonade he drinks gives $K+1-i$ times its fizz level. In other words, if lemonade $i$ is the $j$-th one he drinks, and he drinks it at time $T$ ($T \ge t_i$), his happiness increases by $(x_i - (T - t_i)) \times (K+1-j)$.

Drinking takes negligible time. Several lemonades can be drunk at the same time, in any order.

Geunsu starts with 0 happiness. Drink the lemonades in the best way to give Geunsu the maximum happiness.

The first line contains $N$ and $K$, separated by a space. ($1 \le N \le 2\,000$; $1 \le K \le 12$)

Each of the next $N$ lines contains $t_i$ and $x_i$, separated by a space. ($1 \le t_i, x_i \le 10^{12}$)

Print the maximum happiness Geunsu can obtain.