AT_joisc2019_j.ケーキの貼り合わせ (Cake 3)

今天是 IOI 酱的生日。为此 JOI 君预订了生日蛋糕，但本以为预订的是整块蛋糕，却不小心预订成了切片蛋糕。JOI 君购买的切片蛋糕个数为 $N$。切片蛋糕从 $1$ 到 $N$ 编号，第 $i$ 个切片蛋糕 $(1\le i\le N)$ 的价值为 $V_i$，颜色浓度为 $C_i$。

于是 JOI 君决定从这些切片中选出互不相同的 $M$ 个，按任意顺序圆形排列并粘合，做成一个整块蛋糕。若按顺序排列的切片为 $k_1,\ldots,k_m$，则该整块蛋糕的美丽度定义为

$$\sum_{j=1}^M V_{k_j} - \sum_{j=1}^m |C_{k_j}-C_{k_{j+1}}|$$

（其中 $k_{M+1}=k_1$）。也就是说，美丽度等于所用切片的价值之和减去相邻切片颜色浓度之差的绝对值之和。JOI 君希望使整块蛋糕的美丽度尽可能大。

现在给出切片蛋糕的个数、每个切片蛋糕的价值与颜色浓度，以及要粘合的切片个数，编写程序计算整块蛋糕的最大美丽度。

第一行两个正整数 $N,M$。

第 $2$ 至第 $N+1$ 行，第 $i$ 行两个正整数 $V_{i-1},C_{i-1}$。

请在标准输出的一行中输出整块蛋糕的最大美丽度。

【数据范围】

• $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 200$。
2. （$19$ 分）$N\le 2\ 000$。
3. （$76$ 分）没有额外约束。

【样例 1 解释】

选取切片 $1, 3, 2$，按此顺序圆形排列并粘合得到整块蛋糕时，价值之和为 $2 + 6 + 4 = 12$，相邻切片颜色浓度差的绝对值之和为 $|1 − 4| + |4 − 2| + |2 − 1| = 6$。因此美丽度为 $12 − 6 = 6$。

若选取切片 $2, 3, 4$ 并按该顺序排列粘合，整块蛋糕的美丽度亦为 $6$。

因此无法构造出美丽度更大的整块蛋糕，输出 $6$。

由 ChatGPT 4.1 翻译