레모네이드 바

앞에 있는 수많은 문제를 풀어낸 근수는 너무 피곤해서 레모네이드 바에 들어가서 휴식을 취하려 한다.

레모네이드 바에는 $N$개의 레모네이드가 있다. 레모네이드 $i$는 시각 $t_i$에 청량감 $x_i$를 가지고 나온다. 시간이 지나면 탄산이 빠져서, 시간이 1만큼 지날 때마다 청량감은 1씩 떨어진다. 시각 $T$ ($T \ge t_i$)에 레모네이드 $i$의 청량감은 $x_i - (T - t_i)$이다.

근수의 갈증 수치는 $K$이므로, 최대 $K$개의 레모네이드를 마실 수 있다. 목이 마를 때 마신 레모네이드일수록 더 큰 행복을 준다. 근수가 처음 마시는 레모네이드는 청량감의 $K$배만큼 행복을 준다. 두 번째로 마시는 레모네이드는 청량감의 $K-1$배를 주고, 근수가 $i$번째로 마시는 레모네이드는 청량감의 $K+1-i$배를 준다. 즉 레모네이드 $i$를 $j$번째로 마시고, 시각 $T$ ($T \ge t_i$)에 마셨다면 행복은 $(x_i - (T - t_i)) \times (K+1-j)$만큼 증가한다.

레모네이드를 마시는 데 걸리는 시간은 무시할 만큼 짧다. 같은 시각에 레모네이드 여러 잔을 임의의 순서로 마실 수 있다.

근수의 현재 행복은 0이다. 레모네이드를 적절히 마셔서 근수의 행복을 최대로 만들어 주자.

첫 번째 줄에 레모네이드의 개수 $N$과 현재 갈증 수치 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 2\,000$; $1 \le K \le 12$)

두 번째 줄부터 $N+1$번째 줄까지 각 레모네이드가 나오는 시각 $t_i$와 초기 청량감 $x_i$가 공백으로 구분되어 주어진다. ($1 \le t_i, x_i \le 10^{12}$)

근수가 얻을 수 있는 행복의 최댓값을 출력한다.