记录编号	8412	评测结果	AAAAAAAAAA
题目名称	[BYVoid S1] 灵魂分流药剂	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	2.712 s
提交时间	2008-11-13 22:22:59	内存使用	18.25 MiB

#include <iostream>
#include <string.h>

#define MAXN 15
#define MAXV 111
#define MAXLONG 50

using namespace std;

class hplus{
public:
	short cnt,num[MAXLONG];
	hplus()
	{
		cnt=1;
		num[0]=0;
	}
	void plus(int c)
	{
		short i,max_cnt,jin=0;
		hplus b;
		char zan[MAXLONG];
		sprintf(zan,"%d",c);
		b.cnt=strlen(zan);
		for (i=0;i<b.cnt;i++)
			b.num[i]=zan[b.cnt-i-1]-'0';
		if (cnt>b.cnt)
			max_cnt=cnt;
		else
			max_cnt=b.cnt;
		for (i=0;i<=max_cnt;i++)
		{
			if (i>=cnt)
				num[i]=0;
			if (i>=b.cnt)
				b.num[i]=0;
			num[i]=num[i]+b.num[i]+jin;
			jin=num[i]/10;
			num[i]%=10;
		}
		cnt=max_cnt;
		if (num[cnt]!=0)
			cnt++;
	}

	void copy(hplus b)
	{
		int i;
		cnt=b.cnt;
		for (i=0;i<cnt;i++)
			num[i]=b.num[i];
	}
	int compare(hplus b)
	{
		if (cnt>b.cnt)
			return 1;
		if (cnt<b.cnt)
			return -1;
		int i;
		for (i=cnt-1;i>=0;i--)
		{
			if (num[i]>b.num[i])
				return 1;
			if (num[i]<b.num[i])
				return -1;
		}
		return 0;
	}
	void print()
	{
		int i;
		for (i=cnt-1;i>=0;i--)
			printf("%d",num[i]);
	}
	bool operator >(hplus b)
	{
		if (compare(b)>0)
			return true;
		return false;
	}
	hplus operator =(hplus b)
	{
		copy(b);
		return *this;
	}
	hplus operator +(int b)
	{
		hplus zan=*this;;
		zan.plus(b);
		return zan;
	}
};
typedef hplus var;

int n,v1,v2,c1[MAXN][110],c2[MAXN][110],w[MAXN][110],box[MAXN];
var ans,f[MAXN][MAXV][MAXV];

void run()
{
	int i,j,k,p;
	var max;
	for (k=1;k<=n;k++)
		for (i=0;i<=v1;i++)
			for (j=0;j<=v2;j++)
			{
				//不放
				max=f[k-1][i][j];
				//放一个
				for (p=1;p<=box[k];p++)
				{
					if (i-c1[k][p]>=0 && j-c2[k][p]>=0)
						if (f[k-1][i-c1[k][p]][j-c2[k][p]]+w[k][p]>max)
							max=f[k-1][i-c1[k][p]][j-c2[k][p]]+w[k][p];
				}
				f[k][i][j]=max;
			}
/*	f[n][v1][v2].print();
	cout<<endl;
	(f[n][v1][v2]+4000).print();
	cout<<endl;*/
	for (i=0;i<=v1;i++)
		for (j=0;j<=v2;j++)
			if (f[n][i][j]>ans)
				ans=f[n][i][j];

}

void ini()
{
	int i,u,a,b,c,d,p;
	scanf("%d%d%d%d",&u,&n,&v1,&v2);
	for (i=1;i<=u;i++)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		p=++box[c];
		c1[c][p]=a;
		c2[c][p]=b;
		w[c][p]=d;
	}
}

int main()
{
	freopen("soultap.in","r",stdin);
	freopen("soultap.out","w",stdout);
	ini();
	run();
	ans.print();
//	cout<<ans;
	return 0;
}