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
from collections import defaultdict


if __name__ == '__main__':
    first_line = input().split()
    n = int(first_line[0])
    c = int(first_line[1])

    blocks_by_width = defaultdict(list)

    unique_colors = set()
    for _ in range(n):
        line = input().split()
        a = int(line[0])
        w = int(line[1])

        blocks_by_width[a].append(w)
        unique_colors.add(w)

    scores = {}
    for color in unique_colors:
        scores[color] = 0
    max_so_far = 0

    for width in sorted(blocks_by_width):
        new_scores = {}
        for color in blocks_by_width[width]:
            new_color_score = max(scores[color] + width, max_so_far + width - c)
            new_scores[color] = new_color_score
        
        for color, score in new_scores.items():
            scores[color] = max(scores[color], score)
            max_so_far = max(max_so_far, score)
        # print(scores)
    
    print(max_so_far)
    # print(scores)