分组 dp

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int N=110,M=30,mW=1000;
int n,W;
struct node{int w,v,a,b;}s[N];
LL f[M+10][mW+10];

bool cmp(node x,node y)
{   return x.b<y.b;   }
LL mmax(LL x,LL y)
{   return x>y?x:y;   }

int main()
{
    while (1)
    {
      scanf("%d%d",&n,&W);
      if (n==-1&&W==-1) break;
      for (int i=1;i<=n;i++)
      {
        scanf("%d%d",&s[i].w,&s[i].v);
        s[i].a=s[i].w,s[i].b=0;
        while (s[i].a%2==0) s[i].a/=2,s[i].b++;
      }
      sort(s+1,s+1+n,cmp);
      int l,r;
      l=1;
      memset(f,0,sizeof(f));
      for (int i=0;i<=M;i++)
      {
        r=l-1;//
        while (r<n && s[r+1].b==i) r++;//<n
        for (int j=l;j<=r;j++)
         for (int k=mW;k>=s[j].a;k--)
           f[i][k]=mmax(f[i][k],f[i][k-s[j].a]+s[j].v);
        for (int j=0;j<=mW;j++)//or (int j=mW;j>=0;j--)
          if (W&(1<<i)) f[i+1][j>>1]=mmax(f[i+1][j>>1],f[i][j]);
          else f[i+1][(j+1)>>1]=mmax(f[i+1][(j+1)>>1],f[i][j]);
        l=r+1;
      }
      printf("%lld\n",f[31][0]);
    }
    return 0;
}