Pagini recente » Cod sursa (job #1115015) | Cod sursa (job #3201483) | Cod sursa (job #295647) | Cod sursa (job #2837605) | Cod sursa (job #400913)
Cod sursa(job #400913)
//#include<fstream>
#include<stdio.h>
#include<algorithm>
#define inf "lupu.in"
#define outf "lupu.out"
#define NMax 100010
using namespace std;
//fstream f(inf,ios::in),g(outf,ios::out);
int N;
long long X,L;
long long d[NMax],a[NMax];
typedef int Heap[NMax];
Heap H;
int hdim;
struct elem
{
long long t;
int l;
};
elem v[NMax];
void read()
{
//f>>N>>X>>L;
scanf("%d %lld %lld",&N, &X, &L);
for(int i=1;i<=N;i++)
{
//f>>d[i]>>a[i];
scanf("%lld %lld",&d[i], &a[i]);
v[i].t = ( (X-d[i])/L ) + 1 ;
v[i].l = i;
}
}
bool rule(elem a,elem b)
{
if( a.t < b.t ) return false;
return true;
}
void upheap(int nod)
{
int s;
while( nod>1 )
{
s= (nod>>1) ;
if( a[ H[s] ] < a[ H[nod] ] )
{
swap( H[s], H[nod] );
nod=s;
}
else break;
}
}
void downheap(int nod)
{
int f;
while( true )
{
f= (nod<<1) ;
if( f<=hdim )
{
if( f+1<=hdim && a[ H[f+1] ]>a[ H[f] ] ) ++f ;
if( a[ H[f] ] > a[ H[nod] ] )
{
swap( H[f], H[nod] );
nod=f;
}
else break;
}
else break;
}
}
void solve()
{
long long j=1;
long long s=0;
sort(v+1, v+N+1, rule);
for(int i=v[1].t ; i>=1; --i)
{
while( v[j].t == i && j<=N)
{
++hdim;
H[hdim] = v[j].l ;
upheap( hdim );
++j;
}
if( hdim )
{
s+= a [ H[1] ];
H[1]=H[hdim];
--hdim;
downheap( 1 );
}
}
printf("%lld",s);
//g<< s ;
}
int main()
{
freopen( inf , "r", stdin );
freopen( outf, "w", stdout );
read();
solve();
/*f.close();
g.close();*/
return 0;
}