题目描述

今天是 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 能制作出的完整蛋糕的最大美丽值。

5 3
2 1
4 2
6 4
8 8
10 16

6

8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879

2323231661

提示

样例 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 完成