返回小组 Start 2019-10-07 08:30:00

201910练习赛(提高组)

End 2019-10-07 12:30:00
Contest is over.
Now 2021-12-01 23:11:55

D. 可恶的小偷

Description

随着电脑和网络的普及,打游戏越来越成为现代人休闲娱乐的一种新方式。但是在游戏中,人性的弱点可能会被无数倍的放大。就像是小明,昨天刚刚充钱买的装备今天打开一看就被人偷了。虽然小明已经把这个小偷抓住了,但是小明的所有装备已经被他全部卖掉了。小明非常气愤,他想在游戏里好好的教训教训这个人,小明找到了你帮忙,希望你能帮他想办法折磨这个小偷,以解他心头之恨。

小明现在拥有N瓶药剂,按照成分配比的不同装在M个箱子中。每瓶药剂的有以下参数:对服用 者造成的肉体伤害w,精神伤害v,所属的箱子t,和对服用者造成的痛苦程度p。小偷的生命值为A,意志力为B。你只能从每个箱子中最多拿取1瓶药剂喂给他。注意,喂给他的药剂造成的总肉体伤害不能超过他的生命值A,否则他会死去(会受到系统惩罚),总的精神伤害不能超过他的意志力B,否则他会精神崩溃(我们没有必要给一个精神崩溃的傻瓜制造那么多痛苦)。

请你在不让他死去而且没有精神崩溃的前提下,你要尽可能给他制造更多的痛苦。

Input

输入数据有若干行;

第一行为四个整数N、M、A、BM个箱子的编号为1..M。 

第二行至第N+1行,第i+1行四个整数w、v、t、p表示第i瓶药剂的肉体伤害,精神伤害,所属箱子的编号,和造成的痛苦值。

Output

输入数据为一行一个整数,表示能够给小偷造成的最大的痛苦值。

Examples

Input

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

Output

300

Hint

对于 30%的数据,N\leq 30、M\leq 5; 
对于 100%的数据,N\leq 100、M\leq 10、A,B\leq 100。 


Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit