你有 $n$ 個立方體積木，編號從 $1$ 到 $n$。第 $i$ 個積木的尺寸為 $a_i \times a_i \times a_i$，且表面繪有圖案 $w_i$（圖案以整數識別）。

你的目標是利用選定的積木堆疊出一座評分最高的塔。塔應由若干個積木平放堆疊而成。設 $j_1, \dots, j_m$ 為選定用來建造塔的積木編號（其中 $m$ 為選定積木的數量），按從塔底到塔頂的順序排列。塔的評分標準如下：

• 穩定性：若每個後續的積木都比前一個積木小，即 $a_{j_x} > a_{j_{x+1}}$，則塔是穩定的。不穩定的塔評分為 $0$，不論其他標準為何。
• 高度：若塔的高度為 $h = a_{j_1} + \dots + a_{j_m}$，則評分增加 $h$。
• 風格分數：相鄰且圖案不同的積木（即 $w_{j_x} \neq w_{j_{x+1}}$）會破壞美感，因此每出現一對這樣的相鄰積木，評分就會減少罰款 $c$。

輸入格式

輸入的第一行包含兩個整數 $n$ 和 $c$ ($1 \le n, c \le 500\,000$)，分別代表可用積木的數量以及相鄰圖案不同時的罰款金額。

接下來的 $n$ 行包含各個積木的描述。第 $i$ 個積木的描述位於第 $i$ 行，包含兩個整數 $a_i$ 和 $w_i$ ($1 \le a_i, w_i \le 500\,000$)，分別代表積木的邊長與圖案編號。積木已按尺寸非遞減順序給出，即 $a_i \le a_{i+1}$。

在總分 $5$ 分的測試中，額外滿足 $a_i < a_{i+1}$。

輸出格式

輸出一個整數，代表利用輸入積木所能建造出的最高塔評分。

範例

輸入 1

4 1
1 1
3 2
4 3
4 1

輸出 1

6

輸入 2

4 5
1 1
3 2
4 3
4 1

輸出 2

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$。