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
def score_tower(n, tower, c, w):
    output = 0
    previous_color = -1
    for i in range(n):
        if w[i] != -1:
            previous_color = w[i]
            break
    for i in range(n):
        if tower[i] == -1:
            continue
        output += tower[i]
        if w[i] != previous_color:
            output -= c
        previous_color = w[i]
    return output

buf = input()
n = int(buf.split()[0])
c = int(buf.split()[1])
a = []
w = []
for i in range(n):
    buf = input()
    a.append(int(buf.split()[0]))
    w.append(int(buf.split()[1]))

all_colors = []
for i in range(n):
    if not (w[i] in all_colors):
        all_colors.append(w[i])

max_color = -1
for i in range(len(all_colors)):
    if all_colors[i] > max_color:
        max_color = all_colors[i]
max_color += 1

heights_by_color = [0] * max_color
for i in range(n):
    heights_by_color[w[i]] += a[i]

max_height = -1
max_height_color = -1
for i in range(max_color):
    if heights_by_color[i] > max_height:
        max_height = heights_by_color[i]
        max_height_color = i

current_score = 0
latest_height = 0
for i in range(n):
    if a[i] == latest_height:
        iteration = 0
        if w[i] == max_height_color:
            while a[i+iteration] == a[i]:
                iteration += 1
                if not i+iteration < n:
                    iteration -= 1
                    break
            a[i-1] = -1
            for j in range(1, iteration+1):
                a[i+j] = -1
        else:
            a[i] = -1
        continue
    latest_height = a[i]
    current_score = score_tower(n, a, c, w)
    current_block = a[i]
    a[i] = -1
    if score_tower(n, a, c, w) <= current_score or w[i] == max_height_color:
        a[i] = current_block

print(score_tower(n, a, c, w))