1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys

def najlepsza_wieza(n, c, klocki):
    # Dynamiczne programowanie: dp[i] - najlepsza wartość oceny wieży kończącej się klockiem i
    dp = [0] * n  
    
    for i in range(n):
        max_score = klocki[i][0]  # Wysokość wieży z pojedynczym klockiem
        for j in range(i):
            if klocki[j][0] < klocki[i][0]:  # Stabilność
                penalty = c if klocki[j][1] != klocki[i][1] else 0  # Kara za różne wzory
                max_score = max(max_score, dp[j] + klocki[i][0] - penalty)
        dp[i] = max_score
    
    return max(dp)  # Maksymalna wartość oceny wieży

if __name__ == "__main__":
    # Wczytywanie wejścia
    n, c = map(int, sys.stdin.readline().split())
    klocki = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
    
    # Obliczanie i wypisywanie wyniku
    print(najlepsza_wieza(n, c, klocki))