P14349 [JOISC 2019] 蛋糕 3 / Cake 3

今天是 IOI-chan 的生日，所以她的哥哥 JOI-kun 预订了她的生日蛋糕。虽然他本打算买一个完整的蛋糕，却误订了 $N$ 块蛋糕。这些蛋糕从 $1$ 到 $N$ 编号，每块蛋糕都有价值和颜色。第 $i$ 块蛋糕（$1 \le i \le N$）的价值为 $V_i$，其颜色的深度为 $C_i$。 为了组成一个完整的蛋糕，他决定选择 $M$ 块不同的蛋糕，并将它们按任意顺序排列成环形。他所制作的完整蛋糕的“美丽值”定义为： $$ \sum_{j=1}^{M} V_{k_j} - \sum_{j=1}^{M} \left| C_{k_j} - C_{k_{j+1}} \right| $$ 如果他选择了蛋糕 $k_1, \dots, k_M$ 并按此顺序排列（这里我们设 $k_{M+1} = k_1$）。换句话说，完整蛋糕的美丽值等于其所有蛋糕价值之和，减去每两个相邻蛋糕颜色深度之差的绝对值之和。JOI-kun 希望使完整蛋糕尽可能美丽。 请编写一个程序，给定蛋糕总数、组成完整蛋糕所需的蛋糕数，以及每块蛋糕的价值和颜色深度，计算 JOI-kun 能制作出的完整蛋糕的最大美丽值。

从标准输入读取以下数据。输入中的所有值均为整数。 $N$ $M$ $V_1$ $C_1$ $\vdots$ $V_N$ $C_N$

向标准输出写入一行。输出应包含 JOI-kun 能制作出的完整蛋糕的最大美丽值。

### 样例 1 解释 如果 JOI-kun 选择蛋糕 1、3 和 2，并按此顺序排列，则其蛋糕价值之和为 $2 + 6 + 4 = 12$，颜色深度之差的绝对值之和为 $|1 - 4| + |4 - 2| + |2 - 1| = 6$。因此，完整蛋糕的美丽值为 $12 - 6 = 6$。 如果他选择蛋糕 2、3 和 4 并按此顺序排列，也能制作出美丽值为 6 的完整蛋糕。 由于他无法制作出更美丽的完整蛋糕，你应输出 6。 ### 数据范围 - $3 \le N \le 200\,000$。 - $3 \le M \le N$。 - $1 \le V_i \le 1\,000\,000\,000$（$1 \le i \le N$）。 - $1 \le C_i \le 1\,000\,000\,000$（$1 \le i \le N$）。 ### 子任务 1. （5 分）$N \le 100$。 2. （19 分）$N \le 2000$。 3. （76 分）无额外限制。 翻译由 Qwen3-235B 完成