AT_joig2022_e エゴイ展 (EGOI Exhibition)

在 JOI 美术馆里，有 $N$ 幅画按顺序排成一列。馆中展示的画总共有 $M$ 个种类，种类编号从 $1$ 到 $M$。排在左边第 $i$ 幅画（$1 \le i \le N$）的种类是 $A_i$，其价值为 $V_i$。**注意：$V_i$ 可以是负数。** 下个月，JOI 美术馆将举办「Egoi 展 2022」，预计届时将吸引大量游客。为了美化展览效果，馆长理惠决定撤下一些画，以确保相邻的画不属于同一类型。 此外，为了增加展览的吸引力，她希望剩余画的价值总和尽可能大。 请编写程序，计算在给定的 $N$ 幅画、及其种类与价值信息下，所能保留的画的最大价值总和。

输入数据以以下格式提供： > $N$ $M$ $A_1$ $V_1$ $A_2$ $V_2$ $\ldots$ $A_N$ $V_N$

输出一个数，为剩余画的最大价值总和。

### 约束条件 - $1 \le N \le 150\,000$ - $1 \le M \le N$ - $1 \le A_i \le M$ （$1 \le i \le N$） - $-10\,000 \le V_i \le 10\,000$ （$1 \le i \le N$） - 所有输入数据均为整数 ### 子任务 1. （4 分）$M = 1$，$N \le 15$，$V_i \ge 1$ （$1 \le i \le N$） 2. （17 分）$V_i \ge 1$ （$1 \le i \le N$） 3. （21 分）$N \le 15$ 4. （27 分）$N \le 100$ 5. （19 分）$M \le 100$ 6. （12 分）无其他限制 ### 评分细则 所提交的代码将在评测系统中进行自动测试。程序若能在所有子任务测试数据上给出正确结果，则被认为通过该子任务。 每次提交的得分等于其正确通过的子任务所获得分数的总和。 最终得分取所有提交中的最高得分。 在「提交结果」页面的「我的得分情况」中可以查看当前得分。 ### 示例解释 - 示例 1：如果只保留左数第二幅画，价值总和为 $V_2 = 123$。该示例满足所有子任务的限制。 - 示例 2：如果保留左数第 1、3 和 4 幅画，总价值为最大。该示例满足子任务 2、3、4、5 和 6 的限制。 - 示例 3：保留所有画是最优方案。该示例满足子任务 3、4、5 和 6 的限制。 - 示例 4：最优解是不留任何画。该示例满足子任务 3、4、5 和 6 的限制。 - 示例 5: 此示例满足子任务 4、5 和 6 的限制。 **本翻译由 AI 自动生成**