846. [DreamTeam] 终极装备

【题目描述】

近日DT中的Henry和Geer两人沉迷于仙剑1这款经典的游戏中（都怪Michael，是他把这个游戏推荐给他们的，才让他们如此沉迷，无心学习！不过这款游戏的确不错，想当年……哦，对不起，扯远了，回正题）。

Henry和Geer经过一段复杂的迷宫（游戏里的迷宫多得很，有不好走！苦了两位啊），并且在Michael的帮助之下，他们终于到了女娲遗迹这个地方，并且各自学会了一套终极魔法！同时还得到了一批终极装备！（晕！一批终极装备！真不知道编游戏的人怎么想的，既然是终极装备，为何弄那么多出来啊！）问题来了，在他们得到这些终极装备之前他们还有一些能和终极装备媲美的装备，并且数量和终极装备的数量一样，他们得到这些终极装备后就想让自己操控的游戏人物变得更强，但是一个人物最大负重为M，每个装备可提升人物V[i]能量值，自身重量为W[i]（我们把这两个值称为该装备的属性），Henry和Geer想让自己操控的人物在最大负重的范围内获得最大的能量值，（并且同一种装备只能选择一样或者不选）{A：什么叫同一种装备？B：这个，这个… 晕！ 就是如果V1[i]和V2[i]就是同一种装备，就是i相同}于是作为Oier的他们编写了一个程序来帮他们来选择装备！（学习这个就是安逸，打游戏都要轻松一点！）

【输入格式】

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

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

V1[i],W1[i]：表示原来装备的属性（V1[i]：能量值；W1[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

【数据范围】

1<=M,T<=10000,1<=N<=200

1<=W[i],V[i]<=10000