记录编号	559789	评测结果	AAAAAAAAAA
题目名称	3549.自助者天助	最终得分	100
用户昵称	佚名	是否通过	通过
代码语言	C++	运行时间	0.429 s
提交时间	2021-03-24 19:06:06	内存使用	5.25 MiB

#include<bits/stdc++.h>
using namespace std;
int a[1009][1009]={0},n,m,mx=0,my=0,w[30009],v[30009],tot=0,x[30009];
int main()
{
	freopen("delicious.in","r",stdin);
	freopen("delicious.out","w",stdout);
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
	    int x,y;
	    cin>>x>>y;
	    a[x][y]++;
	    mx=max(mx,x);
	    my=max(my,y);
    }
    for(int i=1;i<=mx;i++)
    {
        for(int j=1;j<=my;j++)
        {
            if(a[i][j])
            {
                for(int k=0;(1<<k)<=a[i][j];k++)
                {
				    a[i][j]-=(1<<k);
				    w[++tot]=(1<<k)*i;
				    v[tot]=(1<<k)*j;
			    }
			    if(a[i][j])
			    {
			        w[++tot]=a[i][j]*i;
			        v[tot]=a[i][j]*j;
			    }
            }
        }
    }
    for(int i=1;i<=tot;i++)
	{
		for(int j=m;j>=0;j--)
		{
			if(w[i]<=j)
			{
				x[j]=max(x[j],x[j-w[i]]+v[i]);
			}
		}
	}
	cout<<x[m];
	return 0;
}