Pagini recente » Cod sursa (job #1051163) | Cod sursa (job #2624998) | Cod sursa (job #2967982) | Cod sursa (job #1423854) | Cod sursa (job #918457)
Cod sursa(job #918457)
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
struct oita {
int distanta,lana,strat;
};
oita oaie[100005];
int n,i,k,l;
long long totaldelana;
struct comp {
inline bool operator()(const int &a,const int &b) {
return (a>b);
}
};
multiset <int,comp> heap;
bool cmp(oita a,oita b) {
return (a.strat>b.strat);
}
int main() {
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d %d %d",&n,&l,&k);
for (i=1;i<=n;i++) {
scanf("%d %d",&oaie[i].distanta,&oaie[i].lana);
oaie[i].strat = (l-oaie[i].distanta)/k;
}
sort(oaie+1,oaie+n+1,cmp);
heap.insert(oaie[1].lana);
for (i=2;i<=n;i++) {
if (oaie[i].strat == oaie[i-1].strat)
heap.insert(oaie[i].lana);
else {
int x = oaie[i-1].strat - oaie[i].strat;
for (int j=1;j<=x;j++) {
if (heap.empty()) break;
totaldelana += (long long)*heap.begin();
heap.erase(heap.begin());
}
heap.insert(oaie[i].lana);
if (oaie[i].strat < 0) break;
}
}
if (oaie[n].strat == 0 && !heap.empty()) totaldelana += (long long)*heap.begin();
printf("%lld\n",totaldelana);
return 0;
}