D. 可恶的小偷

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

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

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

输入数据有若干行；

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

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

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

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