$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$ だけ減少します。

入力

入力の最初の行には、2つの整数 $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$) を表す2つの整数で構成されています。ブロックはサイズの昇順（$a_i \le a_{i+1}$）で与えられます。

$5$ 点分のテストケースでは、さらに $a_i < a_{i+1}$ が成り立ちます。

出力

入力として与えられたブロックから構築できる塔の最高評価値を表す整数を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: 4つのブロックのセットは両方のテストで同じです。テストの違いはペナルティ $c$ のみです。最初のテストでは $c = 1$、2番目のテストでは $c = 5$ です。

図2: 最初のテストにおける最適な塔。高さは 8 で、ペナルティが2回発生します。評価は $8 - 2 \cdot 1 = 6$ です。ペナルティ $c = 5$ の場合、これらの塔の評価は $8 - 2 \cdot 5 = -2$ と低くなります。

図3: 2番目のテストにおける最適な塔。高さは 5 で、ブロックの模様が同じであるためペナルティはありません。評価は $5 - 0 \cdot c = 5$ です。