Cod sursa(job #407909)
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,w,e[1003],c[1003],i,j,ma,rez=10000000,a[200000];
int main()
{
freopen("energii.in","r",stdin);
freopen("energii.out","w",stdout);
scanf("%d%d",&n,&w);
for(i=1;i<=n;++i)
scanf("%d%d",&e[i],&c[i]);
a[0]=1;
int lim=0;
for(i=1;i<=n;++i)
{ for(j=lim;j>=0;--j)
if(a[j])
if(!a[j+e[i]]||a[j+e[i]]>a[j]+c[i])
{
a[j+e[i]]=a[j]+c[i];
if(j+e[i]>=w) rez=min(rez,a[j+e[i]]);
lim=max(lim,j+e[i]);
}
lim=min(lim,w);
}
printf("%d\n",rez-1);
fclose(stdin);
fclose(stdout);
return 0;
}