# Poj Solution 2431

```http://poj.org/problem?id=2431

#include<iostream>
#include"algorithm"
using namespace std;
const int size=10010;

struct stop
{
int f,x;
}p[size];
int n,l,h;

bool cmp(stop a,stop b)
{
return a.x>b.x;
}

void init()
{
int i;

cin>>n;
for(i=0;i<n;i++)
{
cin>>p[i].x>>p[i].f;
}
cin>>l>>h;

p[n+1].x=l;p[n+1].f=0;
p[n].x=0;p[n].f=0;
n+=2;
std::sort(p,p+n,cmp);

if(p[0].x!=l)
while(1)
cout<<"faint"<<endl;
}

int mem[2][size],down;
int *best=mem[0],*temp=mem[1];

void doit()
{
int i,j,t;

down=0;

best[0]=h;
for(i=1;i<n;i++)
{
for(j=down;j<=i;j++)
temp[j]=-1;
for(j=down;j<=i;j++)
{
if(j<i&&best[j]-(p[i-1].x-p[i].x)>temp[j])
temp[j]=best[j]-(p[i-1].x-p[i].x);

if(j>down && (t=best[j-1]-(p[i-1].x-p[i].x))>=0 && (t+=p[i].f) >temp[j])
temp[j]=t;

if(temp[j]<0)
down=j+1;
}
std::swap(best,temp);
}
}

int main()
{
int i;
init();
doit();

for(i=down;i<n-1;i++)
if(best[i]>=0)break;
if(i<n-1)
cout<<i<<endl;
else cout<<-1<<endl;

return 0;
}
```
This entry was posted in poj. Bookmark the permalink.