846. [DreamTeam] 终极装备

【题目描述】

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

Henry 和 Geer 经过一段复杂的迷宫（游戏里的迷宫多得很，有不好走！苦了两位啊），并且在 Michael 的帮助之下，他们终于到了女娲遗迹这个地方，并且各自学会了一套终极魔法！同时还得到了一批终极装备！（晕！一批终极装备！真不知道编游戏的人怎么想的，既然是终极装备，为何弄那么多出来啊！）

问题来了，在他们得到这些终极装备之前他们还有一些能和终极装备媲美的装备，并且数量和终极装备的数量一样，他们得到这些终极装备后就想让自己操控的游戏人物变得更强，但是一个人物最大负重为 $M$，每个装备可提升人物 $V[i]$ 能量值，自身重量为 $W[i]$（我们把这两个值称为该装备的属性）， Henry 和 Geer 想让自己操控的人物在最大负重的范围内获得最大的能量值，（并且同一种装备只能选择一样或者不选）

{$A$：什么叫同一种装备？$B$：就是如果 $V_1[i]$ 和 $V_2[i]$ 就是同一种装备，就是 $i$ 相同} 于是作为 Oier 的他们编写了一个程序来帮他们来选择装备！

【输入格式】

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

接下来 $N$ 行，一行 $4$ 个数，$V_1[i],W_1[i],V_2[i],W_2[i]$

$V_1[i],W_1[i]$：表示原来装备的属性（$V_1[i]$：能量值；$W_1[i]$：物品重量）；

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

【输出格式】

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

【样例输入】

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

【样例输出】

80

【数据规模与约定】

$1 \leq M,T \leq 10000,1 \leq N \leq 200$

$1 \leq W[i],V[i] \leq 10000$