1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys

def najlepsza_wieza(n, c, klocki):
    # Sortujemy klocki malejąco po rozmiarze, bo wejście może nie spełniać tego warunku
    klocki.sort(reverse=True, key=lambda x: x[0])
    
    # Słownik do przechowywania najlepszej oceny dla danej wysokości i wzoru
    najlepsza_ocena = {}
    
    # Przechowujemy najwyższą ocenę
    max_ocena = 0
    
    for a, w in klocki:
        nowa_ocena = []
        
        for (wysokosc, wzor), ocena in najlepsza_ocena.items():
            # Sprawdzamy, czy nowy klocek można dołożyć
            if a < wysokosc:
                kara = c if wzor != w else 0
                nowa_ocena.append(((wysokosc + a, w), ocena + a - kara))
                max_ocena = max(max_ocena, ocena + a - kara)
        
        # Dodajemy przypadek zaczęcia wieży od tego klocka
        nowa_ocena.append(((a, w), a))
        max_ocena = max(max_ocena, a)
        
        # Aktualizujemy najlepsze oceny
        for klucz, ocena in nowa_ocena:
            if klucz not in najlepsza_ocena or najlepsza_ocena[klucz] < ocena:
                najlepsza_ocena[klucz] = ocena
    
    return max_ocena

if __name__ == "__main__":
    n, c = map(int, sys.stdin.readline().split())
    klocki = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
    print(najlepsza_wieza(n, c, klocki))