题目描述

由于天梯上一直被快攻打烂上不去传说，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 想知道他能够获得的最大收益是什么，即最大化：