问题 27185 --灵魂分流药剂

27185: 灵魂分流药剂

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 8
[提交][状态][讨论版][命题人:]

题目描述

幽暗城皇家炼金师赫布瑞姆刚刚发明了一种用来折磨战俘的新型药 剂,这种药剂被称为灵魂分流药剂。灵魂分流药剂的妙处在于能够给战俘带来巨大的痛苦,但是却不会让战俘死去。这种药剂中包含了一些治疗的成分,所以即使战 俘想自尽,也会被救活。用这种求生不得,求死不能的感觉,来对付反对希尔瓦娜斯女王的狂徒们,实在是太美妙了。当然,灵魂分流药剂要限定在一个用量范围之 内,过少会达不到效果,而过多会直接杀了战俘。

最近,我们抓获了一个来自暴风城的探子,他掌握了我们的许多重要情报。希尔瓦娜斯女王命令你用最痛苦的手段折磨他。你从你的导师,灵魂分流药剂的发明者——皇家炼金师赫布瑞姆那里获得了N瓶药剂。每瓶按照药性的不同装在M个箱子中。每瓶药剂都有一个规格:对服用者造成的肉体伤害w,对服用者造成的意志折磨v,所属的箱子t,和对服用者造成的痛苦值p。

据我们测试,那个暴风城探子的生命值为A,意志力为B。你要从每个箱子中最多拿取1瓶药剂喂给他。注意,喂给他的药剂造成的总肉体伤害不能超过他的生命值A,否则他会死去,总意志折磨不能超过他的意志力B,否则他会精神崩溃,我们没有必要给一个精神崩溃的傻瓜制造那么多痛苦。在不让他死去或者精神崩溃的前提下,你要尽可能多的给他制造痛苦,你能解决这个问题吗?

输入

第1行:四个整数N,M,A,B,M个箱子的编号为1..M。

第2行至第N+1行:第i+1行四个整数w,v,t,p表示第i瓶药剂的肉体伤害,意志折磨,所属箱子的编号,和造成的痛苦值。

输出

1行:一个整数,表示能够造成的最大的痛苦值。

样例输入

5 3 20 20
5 10 1 200
10 5 1 100
8 11 2 56
10 10 2 50
5 5 3 100

样例输出

300

提示

数据规模


对于30%的数据


N<=30


M<=5



对于100%的数据


N<=100


M<=10


A,B<=100


来源

 

[提交][状态]