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
// PA2025, @mjm, r4c-wie

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
using namespace std;
using ull = unsigned long long;
inline int nextInt() { int n; scanf("%d", &n); return n; }
inline ull nextUll() { ull n; scanf("%llu", &n); return n; }
inline int myMin(int a, int b) { return a <= b ? a : b; }
inline ull myMax(ull a, ull b) { return a >= b ? a : b; }

class ProjectSet {
	unordered_map<int, ull> byColor;
	set<pair<ull, int>> byValue;
public:
	void clear() {
		byColor.clear();
		byValue.clear();
	}
	int size() const {
		return byValue.size();
	}
	bool empty() const { return 0 == size(); }
	bool contains(int color) {
		return byColor.count(color) > 0;
	}
	bool containsExcept(int color) {
		if (empty()) return false;
		if (size() > 1) return true;
		return !contains(color);
	}
	ull at(int color) {
		return byColor[color];
	}
	ull best() {
		return byValue.rbegin()->first;
	}
	ull bestExcept(int color) {
		auto it = byValue.rbegin();
		if (it->second == color) ++it;
		return it->first;
	}
	void insert(int color, ull value) {
		if (contains(color)) {
			ull oldValue = at(color);
			byValue.erase({ oldValue, color });
		}
		byColor[color] = value;
		byValue.insert({ value, color });
	}
};

ull solve() {
	int n = nextInt();
	ull tax = nextInt();
	map<int, set<int> > h2color;
	for (int i = 0; i < n; ++i) {
		int h = nextInt();
		int color = nextInt();
		h2color[h].insert(color);
	}

	ProjectSet ps;

	for (auto it = h2color.rbegin(); it != h2color.rend(); ++it) {
		int curH = it->first;
		const set<int>& s = it->second;
		unordered_map<int, ull> updateValues;
		for (auto i = s.begin(); i != s.end(); ++i) {
			int color = *i;
			ull best1 = curH;
			if (ps.contains(color))
				best1 += ps.at(color);
			ull best2 = best1;
			if (ps.containsExcept(color)) {
				ull cur = ps.bestExcept(color);
				cur += curH;
				if (cur >= tax)
					best2 = cur - tax;
			}
			updateValues[color] = myMax(best1, best2);
		}
		for (auto i = updateValues.begin(); i != updateValues.end(); ++i) {
			ps.insert(i->first, i->second);
		}
	}

	return ps.best();
}

int main() {
	ull res = solve();
	printf("%llu\n", res);
	return 0;
}