U423276 金色传说

**时间限制：** 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}}| $$ 你能帮帮他吗？

无

无

### 样例 1 解释 将五个卡包都买下来，并按照第 5,4,3,2,1 的顺序开包，其价值总和为 $5+4+3+2+1=15$ ，购买价格为 $|1-2|+|2-3|+|3-4|+|4-5|=4$ ，此时的最大收益为 $15-4=11$ 。 ### 样例 2 解释 选择购买第 4 和第 5 个卡包，按照任意顺序开包的最大收益均为 $(4+5)-|1-2|=8$ 。 ### 数据范围 对于全部的数据，保证 $2\le k\le n\le 5000,1\le a_i,b_i\le 10^9$ 。每个子任务分别有 4 组数据，捆绑给分。 | 子任务编号 | 分值 | $n\le$ | $a_i,b_i\le$ | 其他限制 | | :----: | :-----: | :-----: | :-----: |:-----: | | 1| 20 | $10$ | $100$ |无 | | 2| 20 | $100$ | $10^9$ | 无 | | 3|20 | $5000$ | $10^9$ | $k=2$| | 4|20 | $5000$ | $100$ | 无| | 5|20 | $5000$ | $10^9$ |无 |