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
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <algorithm>
#include <cstdio>
#include <limits>
#include <map>
#include <set>

using big_t = long long;

struct Proto
{
	int a, w;

	bool operator<(const Proto& p) const {
		if (a < p.a) return true;
		if (a > p.a) return false;
		return w < p.w;
	}

	bool operator==(const Proto& p) const {
		return a == p.a && w == p.w;
	}
};

struct Klocek
{
	int a;
	int wzorek;
	big_t punkty;
	int layer;
	int poprzedni_klocek;
};

struct Layer
{
	int a;
	int first_index;
	int last_index;
	big_t max_punkty;
	big_t sum_a;
};

Proto proto[500001];
Klocek klocki[500001]; // 0 jako start + od 1 do N
Layer layers[500001]; // 0 jako start + od 1 do L

big_t suma_warstw(int first_l, int last_l) {
	if (first_l > last_l) {
		return 0;
	}
	big_t wynik = layers[last_l].sum_a;
	if (first_l > 0) {
		wynik -= layers[first_l-1].sum_a;
	}
	return wynik;
}

int main() {
	int N, C; scanf("%d%d", &N, &C);
	proto[0] = { -1, -1 };
	for (int i=1; i<=N; ++i) {
		scanf("%d%d", &proto[i].a, &proto[i].w);
	}
	std::sort(proto, proto+N+1);
	N = std::unique(proto, proto+N+1)-1 - proto;
	//printf("new N = %d\n", N);

	int L = 0;
	std::map<int, int> ostatni_klocek; // poprzedni tego samego koloru

	klocki[0].a = 0;
	klocki[0].wzorek = -1;
	klocki[0].punkty = 0;
	klocki[0].layer = 0;
	klocki[0].poprzedni_klocek = -1;

	layers[0].a = 0;
	layers[0].first_index = 0;
	layers[0].last_index = 0;
	layers[0].max_punkty = 0;
	layers[0].sum_a = 0;

	for (int i=1; i<=N; ++i) {
		klocki[i].a = proto[i].a;
		klocki[i].wzorek = proto[i].w;
		klocki[i].punkty = 0;

		auto it = ostatni_klocek.find(klocki[i].wzorek);
		klocki[i].poprzedni_klocek = (it == ostatni_klocek.end()) ? 0 : it->second;

		if (klocki[i].a != klocki[i-1].a) {
			layers[L++].last_index = i-1;
			layers[L] = { klocki[i].a, i, N, 0, layers[L-1].sum_a + klocki[i].a };
		}

		klocki[i].layer = L;
		ostatni_klocek[klocki[i].wzorek] = i;
	}

	big_t super_max_punkty = 0;
	for (int l=1; l<=L; ++l) {
		//printf("layer %d (%d): %d-%d\n", l, layers[l].a, layers[l].first_index, layers[l].last_index);
		//layers[l].sum_a = layers[l-1].sum_a + layers[l].a;
		// rozpatrujemy kolejną warstwę
		layers[l].max_punkty = layers[l-1].max_punkty;
		for (int i=layers[l].first_index; i<=layers[l].last_index; ++i) {
			//printf("klocek %d: a=%d w=%d poprzedni=%d\n", i, klocki[i].a, klocki[i].wzorek, klocki[i].poprzedni_klocek);

			// tutaj mamy dwie opcje
			// albo bierzemy z poprzedniej warstwy zakładając, że będzie kara za różnicę
			// (ale tylko, jeśli poprzednia warstwa ma a > C)
			// albo skaczemy do poprzedniej warstwy o tym samym kolorze (czyli np. do początku)

			big_t punkty = klocki[klocki[i].poprzedni_klocek].punkty;
			//printf("skok -> punkty=%lld\n", punkty);

			if (l > 1) {
				// możemy też przejść do poprzedniej warstwy, zakładając karę
				//printf("krok -> punkty=%lld\n", layers[l-1].max_punkty - C);
				punkty = std::max(punkty, layers[l-1].max_punkty - C);
			}
			punkty += klocki[i].a;

			klocki[i].punkty = punkty;
			//printf("w sumie -> punkty=%lld\n", punkty);
			layers[l].max_punkty = std::max(layers[l].max_punkty, punkty);
		}
		super_max_punkty = std::max(super_max_punkty, layers[l].max_punkty);
	}
	printf("%lld\n", super_max_punkty);
}