1. 题意整理

我们有 $N$ 块蛋糕，每块蛋糕有：

• 价值 $V_i$
• 颜色深度 $C_i$

我们要选择 $M$ 块不同的蛋糕，排列成一个环（圆形），美观度定义为：

$$\text{美观度} = \sum_{j=1}^M V_{k_j} - \sum_{j=1}^M |C_{k_j} - C_{k_{j+1}}| $$

其中 $k_{M+1} = k_1$。

目标：最大化美观度。

---

2. 初步分析

美观度公式可以写成：

$$\text{美观度} = \left( \sum_{j=1}^M V_{k_j} \right) - \left( \sum_{j=1}^M |C_{k_j} - C_{k_{j+1}}| \right) $$

在环上，颜色深度差的绝对值之和，取决于我们如何排列这些蛋糕。

---

3. 排列的最优结构

考虑将选中的 $M$ 块蛋糕按颜色深度 $C$ 从小到大排序，设排序后为：

$$C_{p_1} \le C_{p_2} \le \dots \le C_{p_M}$$

那么环上相邻颜色深度差的绝对值之和，在按颜色顺序排列成环时，可以最小化这个和。

为什么？
因为对于任意排列，相邻颜色深度差的绝对值之和至少为：

$$2 \times (C_{p_M} - C_{p_1})$$

（因为从最小到最大再到最小，至少走两遍这个跨度）

而按颜色顺序排列成环时，相邻差为：

$$(C_{p_2} - C_{p_1}) + (C_{p_3} - C_{p_2}) + \dots + (C_{p_M} - C_{p_{M-1}}) + (C_{p_M} - C_{p_1}) $$

注意最后一项是 $C_{p_M} - C_{p_1}$，因为 $p_M$ 到 $p_1$ 的跨度是 $C_{p_M} - C_{p_1}$（排序后 $C_{p_1}$ 最小，$C_{p_M}$ 最大）。

实际上，我们仔细计算：

按颜色顺序排成环时，路径是：

$$p_1 \to p_2 \to p_3 \to \dots \to p_M \to p_1$$

颜色差的和为：

$$(C_{p_2} - C_{p_1}) + (C_{p_3} - C_{p_2}) + \dots + (C_{p_M} - C_{p_{M-1}}) + (C_{p_M} - C_{p_1}) $$

前 $M-1$ 项相加得到 $C_{p_M} - C_{p_1}$，再加最后一项 $C_{p_M} - C_{p_1}$，得到：

$$2 \times (C_{p_M} - C_{p_1})$$

所以最优排列就是按颜色排序后成环，此时颜色深度差之和就是：

$$2 \times (C_{\max} - C_{\min})$$

其中 $C_{\max}$ 和 $C_{\min}$ 是所选集合中颜色深度的最大值和最小值。

---

4. 问题转化

美观度公式变为：

$$\text{美观度} = \sum_{i \in S} V_i - 2 \times (C_{\max} - C_{\min}) $$

其中 $S$ 是我们选的 $M$ 块蛋糕的集合，$C_{\max} = \max_{i \in S} C_i$，$C_{\min} = \min_{i \in S} C_i$。

问题变成：
选择 $M$ 块蛋糕，使得 $\sum V_i - 2 \times (C_{\max} - C_{\min})$ 最大。

---

5. 进一步转化

我们可以枚举 $C_{\min}$ 和 $C_{\max}$：

假设我们固定 $C_{\min} = C_l$，$C_{\max} = C_r$（$C_l \le C_r$），那么所有选择的蛋糕必须满足 $C_l \le C_i \le C_r$。

在这些蛋糕中，我们选 $M$ 块价值最大的，设其价值和为 $sumV_{\text{topM}}$，那么美观度为：

$$sumV_{\text{topM}} - 2 \times (C_r - C_l)$$

于是问题变成：

$$\max_{C_l \le C_r} \left[ sumV_{\text{topM}}(C_l, C_r) - 2 \times (C_r - C_l) \right] $$

其中 $sumV_{\text{topM}}(C_l, C_r)$ 表示在颜色区间 $[C_l, C_r]$ 内的蛋糕中，价值最大的 $M$ 块的价值和（如果不足 $M$ 块则忽略）。

---

6. 双指针优化

我们可以将蛋糕按 $C_i$ 排序，然后用双指针维护区间 $[l, r]$，保证区间内蛋糕数量 $\ge M$。

我们需要动态维护区间内价值最大的 $M$ 块蛋糕的价值和。

方法：

• 用两个堆（或平衡树）：
  • 一个大根堆保存未被选中的蛋糕（候选）
  • 一个小根堆保存当前选中的 $M$ 块蛋糕（便于替换最小值）
• 当 $r$ 右移时，加入新蛋糕，如果选中堆大小小于 $M$ 则直接加入，否则若新蛋糕价值大于选中堆的最小值，则替换。
• 当 $l$ 左移时，移除蛋糕，如果它在选中堆中，则从选中堆移除，并从候选堆补一个最大的进来；否则直接从候选堆移除。

但这样实现较复杂，更简单的是用平衡树（如 std::multiset）维护前 $M$ 大值，并记录它们的和。

---

7. 算法步骤

1. 将蛋糕按 $C_i$ 排序。
2. 初始化 $l = 0$，用平衡树（或堆）维护当前区间 $[l, r]$ 内蛋糕的价值，并保持只保留最大的 $M$ 个，并记录它们的和 $sumM$。
3. 遍历 $r = 0 \dots N-1$：
   • 将 $C_r$ 对应的蛋糕加入结构，更新 $sumM$。
   • 如果当前区间内蛋糕数量 $\ge M$：
     • 计算美观度 $sumM - 2 \times (C_r - C_l)$，更新答案。
     • 尝试右移 $l$：不断移除 $C_l$ 对应的蛋糕，更新 $sumM$，直到区间内蛋糕数 $= M$，同时更新答案（因为区间缩小可能更优）。
4. 输出最大美观度。

---

8. 时间复杂度

排序 $O(N \log N)$，双指针 $O(N)$，每次插入删除 $O(\log N)$，总 $O(N \log N)$。

---

9. 核心公式总结

• 最优排列美观度：

$$\text{美观度} = \sum_{i \in S} V_i - 2 \times (\max_{i \in S} C_i - \min_{i \in S} C_i) $$

• 双指针区间 $[l, r]$ 时：

$$\text{美观度} = sumV_{\text{topM}}(l, r) - 2 \times (C_r - C_l) $$

---

10. 示例验证

样例 1：

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

排序后：

(2,1), (4,2), (6,4), (8,8), (10,16)

当选择 $(4,2), (6,4), (8,8)$ 时： 价值和 = 18，$C_{\max} - C_{\min} = 8 - 2 = 6$，美观度 = 18 - 2×6 = 6。

---

这样我们就得到了一个 $O(N \log N)$ 的解法，可以处理 $N \le 2\times 10^5$ 的数据。