1625: 灵魂分流药剂

皇家炼金师发明了一种用来折磨一切生物的新产品，灵魂分流药剂。灵魂分流药剂的妙处在于能够给服用者带来巨大的痛苦，但是却不会让服用者死去，而且可以阻止服用者的自杀。

你拥有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