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
import sys
from collections import defaultdict


def najlepsza_wieza(n, c, klocki):
    dp = defaultdict(lambda: -float('inf'))  # Najlepsze wyniki dla (rozmiar, wzorek)

    najlepszy_wynik = 0  # Przechowujemy globalnie najlepszy wynik

    for i in range(n):
        ai, wi = klocki[i]

        # Nowa wieża z tym klockiem
        najlepsze_dla_tego_klocka = ai

        # Sprawdzamy możliwe dołączenia do poprzednich wież
        for (aj, wj), wartosc in list(dp.items()):
            if aj < ai:  # Stabilność: musimy kłaść mniejszy klocek na większy
                kara = c if wi != wj else 0
                najlepsze_dla_tego_klocka = max(najlepsze_dla_tego_klocka, wartosc + ai - kara)

        # Aktualizujemy najlepszą wartość dla tego wzoru
        dp[(ai, wi)] = max(dp[(ai, wi)], najlepsze_dla_tego_klocka)

        # Aktualizujemy najlepszy globalny wynik
        najlepszy_wynik = max(najlepszy_wynik, dp[(ai, wi)])

    return najlepszy_wynik


# Wczytywanie danych
n, c = map(int, sys.stdin.readline().split())
klocki = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]

# Wypisanie wyniku
print(najlepsza_wieza(n, c, klocki))