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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <map>
#include <list>
#include <queue>

using namespace std;

int penalty;

class Item {
public:
    int a;
    int color;
    long long cost;

    Item *apply(int a2, int color2) {
        long long cost2 = cost + a2;
        if (color != 0 && color != color2) {
            cost2 -= penalty;
        }

        return new Item(a2, color2, cost2);
    }
};

class CmpItemPtrs {
public:
    bool operator()(const Item *lhs, const Item *rhs) const {
        return lhs->cost < rhs->cost;
    }
};

map<int, Item *> m;
priority_queue<Item *, vector<Item *>, CmpItemPtrs> q;
list<Item *> items;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n >> penalty;
    int lastA = 0;
    q.push(new Item(0, 0, 0));
    for (int i = 0; i < n; i++) {
        int a, color;
        cin >> a >> color;

        if (a > lastA) {
            lastA = a;
            auto it2 = items.begin();
            while (it2 != items.end()) {
                auto item = (*it2);
                q.push(item);
                it2 = items.erase(it2);
                auto it1 = m.find(item->color);
                if (it1 != m.end()) {
                    Item *item2 = (*it1).second;
                    if (item->cost > item2->cost) {
                        m[item->color] = item;
                    }
                } else {
                    m[item->color] = item;
                }
            }
        }

        long long bestCost = 0;
        auto it1 = m.find(color);
        if (it1 != m.end()) {
            Item *item = (*it1).second;
            if (item->a < a) {
                Item *item2 = item->apply(a, color);
                m[color] = item2;
                items.push_back(item2);
                bestCost = item2->cost;
            }
        }

        while (!q.empty()) {
            auto item = q.top();
            auto it3 = m.find(item->color);
            if (item->color == color && it3 != m.end() && item->cost < it3->second->cost) {
                q.pop();
            } else {
                Item *item2 = item->apply(a, color);
                if (item2->cost > bestCost) {
                    bestCost = item2->cost;
                    items.push_back(item2);
                }
                break;
            }
        }
        if (a > bestCost) {
            items.push_back(new Item(a, color, a));
        }
    }

    auto it2 = items.begin();
    while (it2 != items.end()) {
        auto item = (*it2);
        q.push(item);
        it2 = items.erase(it2);
    }

    long long best = 0;
    if (!q.empty()) {
        Item *item = q.top();
        if (item->cost > best) {
            best = item->cost;
        }
    }

    cout << best;

    return 0;
}