lhs 的花园计划 1539

Time Limit: 1 Sec Memory Limit: 256 MB

Submission：16 AC：7 Score：100

Description

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

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

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

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

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

Input

输入第一行有三个整数 $m,n,S$ ，表示 lhs 一共有 $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$

Output

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

Samples

input:

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

output: