Pagini recente » Cod sursa (job #1715022) | Cod sursa (job #2221681) | Cod sursa (job #2624932) | Cod sursa (job #1929700) | Cod sursa (job #1233161)
#include<cstdio>
#include<algorithm>
using namespace std;
pair<int,int> oaie[100001];
int i, n, x, l, d, a[100001], crt, mx, k;
long long sum;
void swap(int &a, int &b){int aux; aux=a; a=b; b=aux;}
void heap_down(int poz, int n){
if (2*poz<=n) {
if (2*poz+1<=n) {if ((a[2*poz]>a[poz])||(a[2*poz+1]>a[poz])){
if (a[2*poz]>a[2*poz+1]) {
swap(a[poz], a[2*poz]); heap_down(2*poz, n);
} else {
swap(a[poz], a[2*poz+1]); heap_down(2*poz+1, n);
}}
} else if (a[2*poz]>a[poz]) swap(a[poz], a[2*poz]);
}
}
void heap_up(int poz){
if ((poz>1)&&(a[poz]>a[poz/2])) {
swap(a[poz], a[poz/2]);
heap_up(poz/2);
}
}
int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d", &n, &x, &l); crt=0; sum=0;
for (i=1;i<=n;i++) {
scanf("%d%d", &d, &oaie[++crt].second);
if (d>x) {crt--; continue;}
oaie[i].first=(x-d)/l;
if (oaie[i].first>mx) mx=oaie[i].first;
}
sort(oaie+1, oaie+crt+1); k=crt;
for (i=mx;i>=0;i--) {
while ((oaie[k].first>=i)&&(k>0)) {
a[++a[0]]=oaie[k].second; heap_up(a[0]); k--;
}
if (a[0]>0) {sum+=a[1]; swap(a[1], a[a[0]]); a[0]--; heap_down(1, a[0]);}
}
printf("%lld\n", sum); return 0;
}