时间限制： 1.0 秒

空间限制： 512 MB

题目描述

由于天梯上一直被快攻打烂上不去传说，Xf 最近一直特别懊恼。他觉得是自己的传说牌不够多，所以很想开出多几份高质量的金色传说卡牌。

Xf 来找到酒店老板，酒店老板展示了一对琳琅满目的卡牌包让他目不暇接。酒店老板告诉他，第 $i$ 号卡牌包有一定的价值 $a_i$，也有一定的价格 $b_i$，Xf 想要挑选其中的 $k$ 个卡牌包。但是卡牌包的购买方式比较特别，Xf 排列他们的方式影响了购买的价格。

Xf 挑选好 $k$ 个卡牌包，并且按照自己喜欢的任意方式依次排开。设 Xf 的开包的卡牌包编号按开包顺序为 $c_1,...,c_k$，则它们的价值总和为 $\sum\limits_{i=1}^k a_{c_i}$，而购买的价格是 $\sum\limits_{i=1}^{k-1} |b_{c_i}-b_{c_{i+1}}|$。Xf 获得的受益是价值总和减去购买价格，现在 Xf 想知道他能够获得的最大收益是什么，即最大化：

$$\sum\limits_{i=1}^k a_{c_i}-\sum\limits_{i=1}^{k-1} |b_{c_i}-b_{c_{i+1}}| $$

你能帮帮他吗？

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 $n$ 和 $k$，表示卡牌包个数和 Xf 需要选择的卡牌包个数。

接下来输入 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 个卡牌包的价值和价格。

输出格式

输出到标准输出。

输出一个整数，表示 Xf 能够获得的最大收益。

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

11

样例 1 解释

将五个卡包都买下来，并按照第 5,4,3,2,1 的顺序开包，其价值总和为 $5+4+3+2+1=15$，购买价格为 $|1-2|+|2-3|+|3-4|+|4-5|=4$，此时的最大收益为 $15-4=11$。

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

8

样例 2 解释

选择购买第 4 和第 5 个卡包，按照任意顺序开包的最大收益均为 $(4+5)-|1-2|=8$。

子任务

对于全部的数据，保证 $2\le k\le n\le 5000,1\le a_i,b_i\le 10^9$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	$a_i,b_i\le$	其他限制
1	20	$10$	$100$	无
2		$100$	$10^9$
3		$5000$		$k=2$
4			$100$	无
5			$10^9$