小明和小刚得到了一些终极装备。之前他们还有一些装备，并且数量和终极装备的数量一样，他们得到这些终极装备后就想让自己操控的游戏人物变得更强。
但是一个人物最大负重为 $M$，每个装备可提升人物 $V[i]$ 的能量值，物品自身重量为 $W[i]$（我们把这两个值称为该装备的属性），小明和小刚想让自己操控的人物在最大负重的范围内获得最大的能量值。

第一行 $3$ 个数：$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