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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Author: Bartek Knapik

#include <cstdio>
#include <vector>
#include <set>
#include <unordered_map>

using namespace std;

struct entry
{
    long long h, id;
    bool operator<(const entry &oth) const { if (h != oth.h) return h > oth.h; return id < oth.id; }
};

set<entry> heights;
set<entry> blocks;
unordered_map<long long, long long> best_by_color;
vector<entry> to_add, to_remove;

int n;
long long a, w, c;

int main()
{
    scanf("%d%lld", &n, &c);
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld%lld", &a, &w);
        blocks.insert({ a, w });
    }
    
    auto it = blocks.begin();
    while (it != blocks.end())
    {
        long long cur_height = it->h;
        to_add.clear();
        to_remove.clear();
        while (it != blocks.end() && it->h == cur_height)
        {
            entry single, existing_same, new_same, new_other, candidate;
            
            single = { cur_height, it->id };
            new_same = { -1, -1 };
            new_other = { -1, -1 };
            existing_same = { -1, -1 };
            
            if (best_by_color.count(it->id))
                existing_same = { best_by_color[it->id], it->id };
            
            if (existing_same.id == it->id)
                new_same = { existing_same.h + cur_height, it->id };
            
            auto it_oth = heights.begin();
            while (it_oth != heights.end())
            {
                if (it_oth->id != it->id)
                {
                    new_other = { it_oth->h + cur_height - c, it-> id };
                    break;
                }
                it_oth++;
            }
            if (single < new_same && single < new_other)
                candidate = single;
            else if (new_same < single && new_same < new_other)
                candidate = new_same;
            else
                candidate = new_other;
            
            if (candidate < existing_same)
            {
                to_add.push_back(candidate);
                if (existing_same.h != -1)
                    to_remove.push_back(existing_same);
            }
            it++;
        }
        for (int i = 0; i < to_add.size(); ++i)
        {
            heights.insert(to_add[i]);
            best_by_color[to_add[i].id] = to_add[i].h;
        }
        for (int i = 0; i < to_remove.size(); ++i) heights.erase(to_remove[i]);
    }
    printf("%lld\n", heights.begin()->h);
    return 0;
}