该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

花园中有 $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$

特别的，题目保证 $m > \sum{min(b1_i,b2_i)}$

样例输入

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

样例输出

80