Pagini recente » Cod sursa (job #742814) | Cod sursa (job #1677124) | Cod sursa (job #129821) | Cod sursa (job #2058899) | Cod sursa (job #2645769)
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX=10000;
int d[NMAX+5];
int main()
{
freopen("rucsac.in","r",stdin);
freopen("rucsac.out","w",stdout);
int n,i,j,g,p,gmax,last,maxp;
scanf("%d%d",&n,&gmax);
last=0;
for(i=1;i<=gmax;i++)
d[i]=-1;
for(i=1;i<=n;i++)
{
scanf("%d%d",&g,&p);
for(j=last;j>=0;j--)
if(d[j]!=-1 and j+g<=gmax)
{
d[j+g]=max(d[j]+p,d[j+g]);
if(j+g>last)
last=j+g;
}
}
maxp=0;
for(i=1;i<=gmax;i++)
maxp=max(maxp,d[i]);
printf("%d",maxp);
return 0;
}