Lem0nad3's Bar

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

레모네이드 바에는 $N$개의 레모네이드가 각각 $t_i$의 시각에 $x_i$의 청량감을 가지고 나온다. 시간이 지날수록 레모네이드 안에 든 탄산이 빠지기 때문에 레모네이드가 나오고 $1$만큼의 시간이 지날 때마다 레모네이드의 청량감은 $1$씩 떨어진다. 즉 $T$ $(T \ge t_i)$의 시각에서 레모네이드의 청량감은 $x_i - (T - t_i)$가 된다.

근수는 $K$만큼의 갈증이 있으므로 최대 $K$개만큼의 레모네이드를 마실 수 있다. 목이 마를 때 마시는 레모네이드는 더 많은 행복함을 준다. 근수가 첫 번째로 마시는 레모네이드는 청량감의 $K$배의 행복함을 준다. 두 번째로 마시는 레모네이드는 청량감의 $K-1$배의 행복함을 주고, $i$ 번째로 마시는 레모네이드는 청량감의 $K+1-i$배의 행복함을 준다. 즉 $T$ $(T \ge t_i)$의 시각에서 $i$번째 레모네이드를 $j$번째에 마셨을 때 행복함은 $(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}$)

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