记录编号	428041	评测结果	AAAAAAAAAA
题目名称	采药(加强版)	最终得分	100
用户昵称	_WA自动机	是否通过	通过
代码语言	C++	运行时间	0.959 s
提交时间	2017-07-24 14:14:26	内存使用	3.30 MiB

#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
int f[40500],V,m,c[250200],w[250200],n[250200];
inline int getint()
{
    char c;
    while (!isdigit(c=getchar()));
    int a=c-48;
    while (isdigit(c=getchar()))
        a=a*10+c-48;
    return a;
}
inline void zop(int ci,int wi)
{
    for (int v=m;v>=ci;--v)
        f[v]=max(f[v],f[v-ci]+wi);
}
inline void cp(int ci,int wi)
{
    for (int v=ci;v<=m;++v)
        f[v]=max(f[v],f[v-ci]+wi);
}
inline void mp(int ci,int wi,int ni)
{
    if (ci*ni>=m) {cp(ci,wi);return;}
    int x=1;
    while (x<ni)
    {
        zop(x*ci,x*wi);
        ni-=x;
        x*=2;
    }
    zop(ni*ci,ni*wi);
}
int main(void)
{
    freopen("crazytime.in","r",stdin);
    freopen("crazytime.out","w",stdout);
    V=getint();m=getint();
    int pos=0;
    for (int i=1;i<=V;++i)
    {
        int vi=getint(),wi=getint();bool ok=false;
        for (int j=1;j<=pos;++j)
        {
            if (c[j]==vi && w[j]==wi)
            {
                n[j]++;
                ok=true;
            }
        }
            if (!ok) {c[++pos]=vi;w[pos]=wi;n[pos]=1;}
    }
    for (int i=1;i<=pos;++i)
        mp(c[i],w[i],n[i]);
    printf("%d\n",f[m]);
    return 0;
}