Cod sursa(job #439899)
#include <stdio.h>
#include <stdlib.h>
int sort(const void *x, const void *y) {
return (*(int*)y - *(int*)x);
}
void sorta2(unsigned long int a[][2],unsigned long int n){
qsort(a,n,sizeof(unsigned long int[2]),sort);
}
unsigned long int minim (unsigned long int a[][2], int n,unsigned long int u){
unsigned long int m=1000000000,j=-1;
for(int i=0;i<n;i++)
if(a[i][0]<m&&a[i][1]==0) {
m=a[i][0];
j=i;
}
if (u>m)
a[j][1]=1;
return m;
}
unsigned long int gutui(unsigned long int c[][2],unsigned long int n,unsigned long int h,unsigned long int u){
unsigned long int i,k=0,m=0,z;
unsigned long int a[n][2];
unsigned long int r=0;
if(u>=h) {
for(i=0;i<n;i++)
if(m<c[i][1]&&c[i][0]<=h)
m=c[i][1];
return m;
}
sorta2(c,n);
for(i=0;i<n;i++)
if(k<=h-c[i][0]) {
m=m+c[i][1];
a[r][0]=c[i][1];
a[r][1]=0;
r++;
k=k+u;
}
else {
z=minim(a,r,c[i][1]);
if(c[i][1]>z) {
m=m-z;
m=m+c[i][1];
a[r][0]=c[i][1];
a[r][1]=0;
r++;
}
}
return m;
}
int main(){
unsigned long int c[100000][2];
unsigned long int i,n,h,gr,j,u;
freopen("gutui.in", "r", stdin);
freopen("gutui.out", "w", stdout);
scanf("%ld",&n);
scanf("%ld",&h);
scanf("%ld",&u);
for (i=0;i<n;i++) {
scanf("%ld",&c[i][0]);
scanf("%ld",&c[i][1]);
c[i][2]=0;
}
gr=gutui(c,n,h,u);
printf("%ld\n",gr);
return 0;
}