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
n,c = map(int,input().split())


maxW = 500000

# P = 1
# while maxW > P: P *= 2
# tree = [0]*(2*P)

# def setmax(v, val):
# 	v += P-1
# 	tree[v] = val
# 	v //= 2
# 	while v > 0:
# 		tree[v] = max(tree[v],tree[v * 2])
# 		tree[v] = max(tree[v],tree[v * 2 + 1])
# 		v //= 2

# def get1max(v):
# 	return tree[v+P-1]
	
# def getmax(a, b):
# 	a += P-1
# 	b += P-1
# 	ans = max(tree[a],tree[b])
# 	while b>a+1:
# 		#print(a,b,ans)
# 		if a % 2 == 0:
# 			ans = max(ans,tree[a + 1])
# 		if b % 2 == 1:
# 			ans = max(ans,tree[b - 1])
# 		a //= 2
# 		b //= 2
# 	return ans

M = [0]*(maxW+1)
Maxall = 0
old_a = 0
best = 0
d = {}
for i in range(n):
	a,w = map(int,input().split())
	if a != old_a:
		for k in d:
			#setmax(k,d[k])
			M[k]=d[k]
		d = {}
		old_a = a
		Maxall = max(Maxall,best)
		best = 0
		#print("new", tree)
	#print(a,w,tree)
	if w not in d:
		nocost = M[w]+a
		withcost = Maxall +a -c
		better = max(nocost,withcost)
		d[w] = better
		best = max(best,better)
		# other = 0
		# if w>1:
		# 	other = max(other,getmax(1,w-1))
		# if w<maxW:
		# 	other = max(other,getmax(w+1,maxW))
		# withcost = other + a - c
		# d[w] = max(nocost,withcost)
		#print(a,w,nocost,other,withcost,d)
else:
	for k in d:
		#setmax(k,d[k])
		M[k]=d[k]
	Maxall = max(Maxall,best)
print(Maxall)
#print(tree)
#print(tree[1])