题目描述

题目译自 PA 2025 Runda 4 Wieża

你手头有 $n$ 个立方体积木，编号从 $1$ 到 $n$。编号为 $i$ 的积木尺寸是 $a_{i} \times a_{i} \times a_{i}$，表面涂有图案 $w_{i}$（图案用整数标识）。

你的目标是用这些积木搭一座评分最高的塔。你可以挑选一些积木，从下到上平放叠成塔。假设选了 $m$ 个积木，编号为 $j_{1}, \ldots, j_{m}$，从底部到顶部依次排列。塔的评分基于以下规则：

• 稳定性：塔要稳定，需保证每块积木比上方的积木大，即 $a_{j_{x}} > a_{j_{x+1}}$。不稳定的塔评分直接为 $0$，其他规则不再考虑。
• 高度：塔高为 $h = a_{j_{1}} + \ldots + a_{j_{m}}$，评分增加 $h$ 分。
• 风格分：相邻积木图案不同（即 $w_{j_{x}} \neq w_{j_{x+1}}$）会影响美观，每对这样的相邻积木扣除 $c$ 分。

输入格式

输入的第一行包含两个整数 $n$ 和 $c$ $(1 \leq n, c \leq 500000)$，分别表示积木数量和相邻不同图案的扣分值。

接下来的 $n$ 行描述每个积木。第 $i$ 行包含两个整数 $a_{i}$ 和 $w_{i}$ $(1 \leq a_{i}, w_{i} \leq 500000)$，分别表示积木的边长和图案编号。积木按边长非递减顺序给出，即 $a_{i} \leq a_{i+1}$。

输出格式

输出一个整数，表示用给定的积木能搭建出的最高评分塔的分数。

4 1
1 1
3 2
4 3
4 1

6

4 5
1 1
3 2
4 3
4 1

5

样例解释

• 图 1：两个样例中的四块积木相同，仅扣分值 $c$ 不同。第一个样例 $c=1$，第二个样例 $c=5$。
• 图 2：第一个样例的最佳塔。高度 8，扣双倍罚分。评分计算为 $8 - 2 \cdot 1 = 6$。若 $c=5$，这些塔评分较低，为 $8 - 2 \cdot 5 = -2$。
• 图 3：第二个样例的最佳塔。高度 5，无扣分，因积木图案相同。评分为 $5 - 0 \cdot c = 5$。

数据范围与提示

对于 $50\%$ 的数据，满足 $a_{i} < a_{i+1}$。