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
/* 2025
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>

int blocks;
int penalty;
int size;
int color;

int prev_size;
int mem;

const int COLORS = 524288;

long long int result[2][COLORS];
int prev_color[COLORS];
int prev_colors;

int main(void)
{
    scanf("%d %d", &blocks, &penalty);
    for(int b = 0; b < blocks; ++b)
    {
        scanf("%d %d", &size, &color);
        if(prev_size != size)
        {
            mem ^= 1;
            for(int c = 0; c < prev_colors; ++c)
                result[mem][prev_color[c]] = result[mem ^ 1][prev_color[c]];

            result[mem][COLORS - 1] = result[mem ^ 1][COLORS - 1];
            prev_colors = 0;
            prev_size = size;
        }

        prev_color[prev_colors++] = color;
        result[mem][color] = std::max(result[mem][color], result[mem ^ 1][COLORS - 1] + size - penalty);
        result[mem][color] = std::max(result[mem][color], result[mem ^ 1][color] + size);
        result[mem][COLORS - 1] = std::max(result[mem][COLORS - 1], result[mem][color]);
    }

    printf("%lld\n", result[mem][COLORS - 1]);
    return 0;
}