Pagini recente » Cod sursa (job #377942) | Cod sursa (job #159313) | Cod sursa (job #535955) | Cod sursa (job #1886033) | Cod sursa (job #675705)
Cod sursa(job #675705)
#include <cstdio>
#include <utility>
#include <functional>
#include <algorithm>
#define MAXN 1000001
using namespace std;
int n, x, l;
long long sum;
pair<int, int> oi[ MAXN ];
int h[MAXN], size;
void read()
{
freopen("lupu.in", "r", stdin);
freopen("lupu.out", "w", stdout);
scanf("%d%d%d", &n, &x, &l);
for(int i = 1; i <= n; ++i)
{
int dist, value;
scanf("%d%d", &dist, &value);
oi[i] = make_pair(dist, value);
}
}
void po()
{
for(int i = 1; i <= n; ++i)
printf("%d %d\n", oi[i].first, oi[i].second);
}
void urca(int nod)
{
int v = h[ nod ];
while( nod > 1 && v < h[ nod/2 ] )
{
h[ nod ] = h[ nod/2 ];
nod = nod/2;
}
h[ nod ] = v;
}
void coboara(int nod)
{
int son = nod;
do {
nod = son;
if( 2 * nod <= size && h[ nod ] > h[ 2 * nod ] ) son = 2 * nod;
if( 2 * nod + 1 <= size && h[ son ] > h[ 2 * nod + 1 ] ) son = 2 * nod + 1;
if( son != nod )
{
swap(h[ nod ], h[ son ]);
}
else
break;
} while(true);
}
void ph()
{
for(int i = 1; i <= size; ++i)
printf("%d ", h[i]);
printf("\n");
}
void solve()
{
sort(&oi[1], &oi[n+1], greater< pair<int,int> >());
for(int i = 1; i <= n; ++i)
{
if( oi[i].first <= x )
{
x -= l;
h[++size] = oi[i].second;
urca(size);
} else
{
if( oi[i].second > h[1] )
{
h[1] = oi[i].second;
coboara(1);
}
}
}
for(int i = 1; i <= size; ++i)
sum += h[i];
}
void printResult()
{
printf("%lld\n", sum);
}
int main()
{
read();
solve();
printResult();
return 0;
}