【问题描述】

TIM神牛的VIPER已经超神，因此他已经不关心游戏的进行了。目前他手上已经积累了很多金币，于是他回到生命之泉找卖武器的大叔买武器以尽量提高自己的攻击力。大叔说：“我这里给你每个身体部位都有两种装备，当然价格不同提升的攻击力也不同，你自己选吧。”可是TIM神牛已经杀红了眼，无法思考问题了，于是他找到了你威胁你说：“你要是不能把我的攻击力提到最高我就一口喷死你！”可怜你的也只有着手解决这个问题了。

【输入数据】

第一行有三个数M，N，T，分别表示TIM神牛手中的金币、TIM神牛身上的身体部位数量以及TIM神牛的初始攻击力。

接下来的一共N行，第i行有4个数 V1[i],W1[i],V2[i],W2[i]，分别表示第i个身体部位可装备的第一种和第二种装备的提升的攻击力以及价格。注意，每个部位最多只能装备一种武器。

【输出数据】

一个数，表示TIM神牛可以达到的最大攻击力。

【样例输入】

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

【样例输出】

80

【数据规模】

对于100%的数据，1<=M,T,V,W<=10000，N<=200。