Wieża

Masz do dyspozycji $n$ sześciennych klocków, ponumerowanych liczbami od $1$ do $n$. Klocek numer $i$ ma wymiary $a_i \times a_i \times a_i$ oraz jest pomalowany we wzorek $w_i$ (wzorki są identyfikowane liczbami całkowitymi).

Twoim celem jest zbudowanie wieży o najwyższej możliwej ocenie, przy użyciu wybranych przez siebie klocków. Wieża powinna składać się z pewnej liczby klocków, ustawionych płasko, jeden na drugim. Niech $j_1, \dots , j_m$ oznaczają numery klocków wybranych do budowy wieży (gdzie $m$ to liczba wybranych klocków), w kolejności od podstawy do szczytu. Wieża jest oceniana według następujących kryteriów:

• Stabilność. Wieża jest stabilna, jeśli każdy kolejny klocek jest coraz mniejszy, tzn. $a_{j_x} > a_{j_{x+1}}$. Niestabilne wieże dostają ocenę $0$, bez względu na pozostałe kryteria.
• Wysokość. Jeśli wieża ma wysokość $h = a_{j_1} + \dots + a_{j_m}$, to ocena jest zwiększana o wartość $h$.
• Noty za styl. Sąsiadujące klocki o różnych wzorkach (tzn. $w_{j_x} \ne w_{j_{x+1}}$) psują estetykę, więc za każdą taką parę sąsiednich klocków ocena jest zmniejszana o karę $c$.

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $n$ oraz $c$ ($1 ≤ n, c ≤ 500\, 000$), oznaczające odpowiednio liczbę dostępnych klocków oraz wysokość kary za sąsiadujące klocki o różnych wzorkach.

W kolejnych n wierszach występują opisy poszczególnych klocków. Opis klocka numer $i$ znajduje się w $i$-tym wierszu i składa się z dwóch liczb całkowitych $a_i$ oraz $w_i$ ($1 ≤ a_i , w_i ≤ 500\, 000$), oznaczających długość boku sześciennego klocka oraz numer wzorku. Klocki są podane w kolejności niemalejących rozmiarów, tzn. $a_i ≤ a_{i+1}$.

W testach wartych $5$ punktów zachodzi dodatkowo: $a_i < a_{i+1}$.

Na wyjściu powinna znaleźć się jedna liczba całkowita – wartość oceny najlepszej wieży, jaką da się zbudować z klocków podanych na wejściu.

Wyjaśnienie do przykładów:

Rysunek 1: Zestaw czterech klocków jest taki sam w obu testach. Testy różnią się tylko karą $c$. W pierwszym teście $c = 1$, a w drugim $c = 5$.

Rysunek 2: Najlepsze wieże dla pierwszego testu. Wysokość $8$ i podwójna kara. Ocena to $8 - 2 \cdot 1 = 6$. Dla kary $c = 5$, te wieże mają niską ocenę $8 - 2 \cdot 5 = -2$.

Rysunek 3: Najlepsza wieża dla drugiego testu. Wysokość $5$ i brak kary, ponieważ klocki mają ten sam wzorek. Ocena to $5 - 0 \cdot c = 5$.