说明

徐老师买下了一个花园，现在他想在这个花园里种一些花来让花园变得好看起来。

花园中有 $n$ 个花盆，石老师给了徐老师两种种花方案，但是徐老师对两种都不是特别满意，于是他决定自己综合一下这两种方案。

对于一种方案：石老师给出了第 $i$ 个花盆上种的花的价格是 $v_i$，这盆花可以给花园提供 $b_i$ 点美丽值。

虽然徐老师希望花园尽可能美丽，可是囊中羞涩的他总共只有 $m$ 元钱，现在他想问你花园的美丽值最多可以是多少？

注意花园本身也是有美丽值的！而且一个花盆只能种一种花！

输入格式

输入第一行有三个整数 $m,n,S$ ，表示徐老师一共有 $m$ 元钱，花园中有 $n$ 个花盆和花园本身的美丽值 $S$

接下来 $N$ 行，每行四个整数$b1_i,v1_i,b2_i,v2_i$ 

分别表示石老师给出的第一种方案第 $i$ 盆花的价格 $v1_i$ 和美丽值 $b1_i$，第二种方案第 $i$ 盆花的价格 $v2_i$ 和美丽值 $b2_i$。

对于 $60\%$ 的数据中，$1 \leq n \leq 40, 1 \leq m,S,v_i,b_i \leq 10000$

对于 $100\%$ 的数据中，$1 \leq n \leq 200, 1 \leq m,S,v_i,b_i \leq 10000$

输出格式

输出只有一行仅包含一个整数，表示花园的最大美丽值之和。

样例

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

80