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
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 14 14:58:59 2025

@author: ania
"""

        
def przyklad(i):
    if i==1:
        return 4,1,[[1,1],[3,2],[4,3],[4,1]]
    elif i==2:
        return 4,5,[[1,1],[3,2],[4,3],[4,1]]
    elif i==3:
        return 16, 2, [[10,1],[10,7], [9,3],[9,11],[9,7], [7,4],[7,3], [6,3], 
                       [5,1],[5,11],[5,4], [2,1],[2,4],[2,7], [1,4],[1,11] ]
    elif i==4:
        return 16, 5, [[10,1],[10,7], [9,3],[9,11],[9,7], [7,4],[7,3], [6,3], 
                       [5,1],[5,11],[5,4], [2,1],[2,4],[2,7], [1,4],[1,11] ]
 


def readData():
    n, c = [int(x) for x in input().split()]
    klocki = []
    for i in range(n):
        a, w = [int(x) for x in input().split()]
        klocki.append([a,w])
    return n,c,klocki


class wieza:
    def __init__(self, val=0, a=0, kol={}):
        self.val    = val
        self.a      = a
        self.kol    = kol
    
    def update(self, val, a, kol):
        self.val    = val
        self.a      = a
        self.kol    = kol
        
    def items(self):
        return (self.val, self.a, self.kol)
    
        
  
def rozwiazanie(n,c,klocki):
    # --------- spamietywanie najlepszych wiez konczacych sie kazdym kolorem ---------
    # mapa: kolor -> najwyzsza wartosc wiezy zakonczonej tym kolorem
    bestByColor = {} 
    for k in klocki:
        _,w = k
        bestByColor[w]=0    
    
    # --------- szukanie najlepszej wiezy w kolejnych krokach ---------
    best = wieza(0,0,{})
    i = 0
    while i<n:
        a           = klocki[i][0]  # rozmiar klocka       
        new_best    = wieza(0, a, {}) # zawiera: wartosc wiezy, kolory klockow 
       
        # znajdz wszystkie klocki tego samego rozmiaru i policz wartosc wiezy po ich dolozeniu
        j = i
        while j<n and klocki[j][0] == a:
            k = klocki[j][1] # kolor klocka
            j +=1 
        
            if k in best.kol:
                # pasujace kolory - dolozenie klocka bez kary
                val = best.val + a                 
            else:
                # niepasujace kolory - dolozenie klocka z kara lub poszukanie 
                # najlepszej pasujacej wiezy
                val1 = best.val + a - c 
                val2 = bestByColor[k] + a  
                val = max(val1, val2)
                
            if val > new_best.val:
                new_best.update(val, a, {k})
            elif val == new_best.val:
                new_best.kol.add(k)
                
            bestByColor[k] = max(bestByColor[k], val)            
        
        # przesuniecie indeksu i 
        i = j            
            
        # sprawdz czy dolozenie klocka sie oplaca i update best jesli tak
        if new_best.val > best.val:
            best = new_best
                    
    return best.val


# =========== MAIN =========================
n,c,klocki = readData() #   przyklad(1) #

klocki.sort(key=lambda x: (x[0], -x[1]), reverse=True)
best_val = rozwiazanie(n, c, klocki)
    
print(best_val) #, bestByColor, klocki)