记录编号	516820	评测结果	AAAAAAAAAA
题目名称	采药(加强版)	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.499 s
提交时间	2018-10-26 13:09:01	内存使用	2.60 MiB

#include<bits/stdc++.h>
using namespace std;
int cc[21][21];
int w[250001],v[250001];
int f[100001];
int m,n,k,cnt;
int main()
{ freopen("crazytime.in","r",stdin);
  freopen("crazytime.out","w",stdout);
  memset(cc,0,sizeof(cc));
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;i++)
  { int a,b;
    scanf("%d%d",&a,&b);
    cc[a][b]++;
  }
  for (int i=1;i<=20;i++)
   for (int j=1;j<=20;j++)
  { int z=cc[i][j];
    if (!z) continue;
    for (int k=1;k<=z;k<<=1)
    { cnt++;
      w[cnt]=i*k;
      v[cnt]=j*k;
      z-=k;
	}
	if (z) {cnt++;w[cnt]=i*z;v[cnt]=j*z;}
   }
   for (int i=1;i<=cnt;i++)
    for (int j=m;j>=w[i];j--)
  f[j]=max(f[j],f[j-w[i]]+v[i]);
  printf("%d",f[m]);
  return 0;	 
}