Pagini recente » Cod sursa (job #3176668) | Cod sursa (job #3177932) | Cod sursa (job #3250402) | Cod sursa (job #2908113) | Cod sursa (job #3252977)
/*
__
/\ \
_ __ ___ ___\ \ \/'\ ___ __ ___ ___ __
/\`'__\/ __`\ /'___\ \ , < / __`\ /'__`\ /' _ `\ /' _ `\ /'__`\
\ \ \//\ \L\ \/\ \__/\ \ \\`\ /\ \L\ \/\ \L\.\_/\ \/\ \/\ \/\ \/\ \L\.\_
\ \_\\ \____/\ \____\\ \_\ \_\ \____/\ \__/.\_\ \_\ \_\ \_\ \_\ \__/.\_\
\/_/ \/___/ \/____/ \/_/\/_/\/___/ \/__/\/_/\/_/\/_/\/_/\/_/\/__/\/_/
*/
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using i64 = int64_t;
class heap {
private:
int len = 0;
i64 heap[400004];
void swamp(i64 a, i64 b) { swap(heap[a], heap[b]); }
void up(int pos) {
while (pos > 1 && heap[pos / 2] < heap[pos]) {
swamp(pos, pos / 2);
pos /= 2;
}
}
void down(int pos) {
while (pos * 2 <= len) {
int t = pos * 2;
if (pos * 2 + 1 <= len && heap[pos * 2 + 1] > heap[pos * 2]) {
t++;
}
if (heap[pos] < heap[t]) {
swamp(pos, t);
pos = t;
} else
break;
}
}
public:
bool empty() { return (len == 0); }
void erase(int pos) {
if (pos == len) {
len--;
} else {
swamp(pos, len);
len--;
up(pos);
down(pos);
}
}
i64 max() {
i64 tmp = heap[1];
erase(1);
return tmp;
}
void add(i64 val) {
len++;
heap[len] = val;
up(len);
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// #ifdef LOCAL
ifstream cin{"lupu.in"};
ofstream cout{"lupu.out"};
// #endif
i64 n, m, l;
cin >> n >> m >> l;
vector<pair<i64, i64>> v(n);
int x, y;
for (int i = 0; i < n; i++) {
cin >> x >> y;
v[i] = {x, y};
}
sort(v.begin(), v.end());
heap h;
int res = 0;
int len = ((m - v[0].first) / l) * 2;
int idx = 0;
while (idx < n) {
while (idx < n && v[idx].first + len <= m) {
h.add(v[idx].second);
idx++;
}
res += h.max();
if (idx < n) {
int len2 = ((m - v[idx].first) / l) * l;
while (len + l < len2 && !h.empty()) {
res += h.max();
len += l;
}
len = len2;
}
}
cout << res;
return 0;
}