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

题目：魔法考试

题目描述

哈利波特在霍格沃茨魔法学校迎来第一次魔法考试。初始能量值为 $S$，魔法值为 $M$。学习了 $N$ 种魔法，每种魔法有 2 种施展方式：第 $i$ 种魔法第一种方式消耗 $s_{i1}$ 能量、获得 $m_{i1}$ 魔法值；第二种方式消耗 $s_{i2}$ 能量、获得 $m_{i2}$ 魔法值。规则是能量不能为负，每种魔法最多选一种方式且最多施展一次。求魔法值能达到的最大值。

输入格式

• 第 1 行：3 个整数 $S, N, M$，空格隔开。
• 接下来 $N$ 行：每行 4 个整数 $m_{i1}, s_{i1}, m_{i2}, s_{i2}$，对应第 $i$ 种魔法的两种施展方式参数。

输出格式

输出魔法值的最大值。

样例

• 输入示例

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

• 输出示例

80

• 解释：选魔法 1 方式 2（消耗 19、得 23 ），魔法 2 方式 1（消耗 10、得 17 ），魔法 3 方式 1（消耗 20、得 20 ）。总消耗 49 ≤ 50 ，魔法值总和 $20 + 23 + 17 + 20 = 80$ 。

数据范围

对于 100% 的数据， $1 \leq N \leq 200$， $1 \leq M, S \leq 10^4$， $1 \leq m_i, s_i \leq 2 \times 10^4$ 。