#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node
{
    int c;
    int w;
}a[1001];

int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int i,n,v,j;
    int f[1001];
    while(scanf("%d%d",&n,&v)&&(n||v))
    {
         for(i=0;i<n;++i)
             scanf("%d%d",&a[i].c,&a[i].w);
         memset(f,0,sizeof(f));
         for(i=0;i<n;++i)
         {
             for(j=v;j>=a[i].c;j--)
                 f[j]=max(f[j],f[j-a[i].c]+a[i].w);
         }
         printf("%d\n",f[v]);
    }
    return 0;
}

         

刚开始也是想着贪心，让价值除以大小，作为权值去比较，但是后来发现，不对，还是用了 背包