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
import heapq as hq
def main():
    n,c=list(map(int,input().split()))
    k=[]
    for i in range(n):
        k.append(list(map(int,input().split())))
    x=[0 for i in range(500001)]
    k.append([1000000,0])
    pp=[0]
    b=0
    g=set()
    mm=0
    for a,w in k:
        if a==b:
            g.add(w)
        else:
            r=mm
            for z in g:
                x[z]=max(b-c+r,b+x[z])
                if x[z]>mm:
                    mm=x[z]
            b=a
            g=set()
            g.add(w)
    print(mm)
        
        
    
main()