2009: 终极装备

近日DT中的Henry和Geer两人沉迷于仙剑1这款经典的游戏中。

Henry和Geer经过一段复杂的迷宫，并且在Michael的帮助之下，他们终于到了女娲遗迹这个地方，并且各自学会了一套终极魔法！同时还得到了一批终极装备！问题来了，在他们得到这些终极装备之前他们还有一些能和终极装备媲美的装备，并且数量和终极装备的数量一样，他们得到这些终极装备后就想让自己操控的游戏人物变得更强，但是一个人物最大负重为M，每个装备可提升人物V[i]能量值，自身重量为W[i]（我们把这两个值称为该装备的属性），Henry和Geer想让自己操控的人物在最大负重的范围内获得最大的能量值，（并且同一种装备只能选择一样或者不选）于是作为Oier的他们编写了一个程序来帮他们来选择装备！（学习这个就是安逸，打游戏都要轻松一点！）

第一行3个数：M，N，T。M代表人物的最大负重，N为得到的终极装备数量，T为人物不带任何装备的能量值。

  接下来N行，一行4个数，V1[i],W1[i],V2[i],W2[i]   

V1[i],W1[i]：表示原来装备的属性（V1[i]：能量值；W2[i]：物品重量）；

V2[i],W2[i]：表示得到的终极装备属性（V2[i]：能量值；W2[i]：物品重量）；

一个数，就是人物能够达到的最大能量值。

50  3  20
12  18  23  19
17  10  30  24
20  20  17  20

    80