Pagini recente » Ciorna | Cod sursa (job #2321533) | Cod sursa (job #519331) | Cod sursa (job #1186336) | Cod sursa (job #2277388)
#include <fstream>
#define MARE 6000000
using namespace std;
ifstream cin("energii.in");
ofstream cout("energii.out");
int n,w,g[1005],p[1005],v[6000],i,j,cf,s=0,sp=0;
int main()
{
cin>>n>>w;
for(i=1;i<=w+1000;i++)
v[i]=MARE;
for(i=1;i<=n;i++)
{
cin>>g[i]>>p[i];
s=s+g[i];
sp=sp+p[i];
}
if(s<w)
{
cout<<-1;
return 0;
}
if(s==w)
{
cout<<sp;
return 0;
}
for(i=1;i<=n;i++)
{
for(j=w-g[i]+500;j>=0;j--)
{
if(v[j+g[i]]>v[j]+p[i])
v[j+g[i]]=v[j]+p[i];
}
}
for(i=w;i<=w+500;i++)
{
if(v[i]!=MARE)
{
cout<<v[i];
return 0;
}
}
return 0;
}