Pagini recente » Cod sursa (job #2686917) | Cod sursa (job #1699624) | Cod sursa (job #355035) | Cod sursa (job #1165927) | Cod sursa (job #1528868)
#include <cstdio>
#include <algorithm>
#define right(x) ((x<<1)+1)
#define left(x) (x<<1)
#define dad(x) (x>>1)
using namespace std;
long long ans=0LL;
int nr=0,i,x,n,l,last,j,heap[100007];
pair<int,int> a[100007];
inline void POP(int x)
{
if(right(x)<=nr)
{
if(heap[left(x)]>=heap[right(x)] && heap[left(x)]>heap[x])
{
swap(heap[x],heap[left(x)]);
POP(left(x));
}
else
if(heap[left(x)]<heap[right(x)] && heap[right(x)]>heap[x])
{
swap(heap[x],heap[right(x)]);
POP(right(x));
}
}
else if(left(x)<=nr)
{
if(heap[left(x)]>heap[x])
{
swap(heap[x],heap[left(x)]);
POP(left(x));
}
}
}
inline void INSERT(int p)
{
if(p==1) return;
if(heap[p]>heap[dad(p)])
{
swap(heap[p], heap[dad(p)]);
INSERT(dad(p));
}
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
for(i=1;i<=n;++i)
{
scanf("%d%d",&a[i].first,&a[i].second);
if(!l) {if(a[i].first<=x) ans+=a[i].second;}
else a[i].first=(x-a[i].first)/l;
}
if(!l)
{
printf("%lld\n",ans);
return 0;
}
sort(a+1,a+n+1);
last=a[n].first+1;i=n;
for(x=a[n].first; i ;x=a[i].first)
if(x<0) break;
else
{
while(i && a[i].first==x)
{
heap[++nr]=a[i].second;
INSERT(nr);
--i;
}
for(j=x;nr && j<last;++j)
{
ans+=1LL*heap[1];
heap[1]=heap[nr];
--nr;
POP(1);
}
last=x;
}
for(j=0;nr && j<last;++j)
{
ans+=1LL*heap[1];
heap[1]=heap[nr];
--nr;
POP(1);
}
printf("%lld\n",ans);
return 0;
}