Cod sursa(job #518141)
#include <fstream>
using namespace std;
ifstream in("energii.in");
ofstream out("energii.out");
int ct[100000],g[20000],c[20000],ok,i,j,n,w,minim,maxim,maxt;
int main()
{
in>>n;
in>>w;
for(i=0;i<=10000;i++)
ct[i]=-1;
for(i=1;i<=n;i++)
{
in>>g[i];
in>>c[i];
}
for(i=1;i<=n;i++)
{
for(j=maxim;j>=0;j--)
if(j==0 && (ct[j+g[i]]==-1||ct[j+g[i]]>ct[j]+c[i]))
{
ct[j+g[i]]=ct[j]+c[i]+1;
if(j+g[i]>maxim) maxim=j+g[i];
}
else
if(j!=0&&ct[j]!=-1&&(ct[j+g[i]]>ct[j]+c[i]||ct[j+g[i]]==-1))
{
ct[j+g[i]]=ct[j]+c[i];
if(j+g[i]>maxim)
maxim=j+g[i];
}
if(maxim>=w)
{
if(maxt<maxim) maxt=maxim;
maxim=w;
}
}
minim=32000;
if(maxt==0)
{
out<<"-1";
return 0;
}
if(maxt==w)
{
out<<ct[w];
return 0;
}
for(i=w;i<=maxt;i++)
if(minim>ct[i]&&ct[i]!=-1) minim=ct[i];
out<<minim;
return 0;
}