1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
n, c = map(int, input().split())
klocki = []
for _ in range(n):
    a, w = map(int, input().split())
    klocki.append((a, w))

klocki.sort(reverse=True)
ocena = 0

dp = {(0, frozenset()):0}
for a, w in klocki:
    tmp = dp.copy()
    for (ostatni, used), wynik in dp.items():
        if not a in used:
            nowy = (w, used|{a})
            kara = c if ostatni != 0 and ostatni != w else 0
            tmp[nowy] = max(tmp.get(nowy, 0), wynik+a-kara)
    dp = tmp 
ocena = max(dp.values())

print(ocena)