33826번 - 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$.