当前没有测试数据。

魔法考试

题目描述

哈里波特在霍格沃茨魔法学校迎来了第一次魔法考试。

考试开始，哈利波特的能量值为 $S$，魔法值为 $M$。本学期，他学习了 $N$ 种魔法，每种魔法都有 $2$ 种不同的施展方式。第 $i$ 种魔法的第 $1$ 种施展方式会消耗 $s_{i1}$ 个点的能量值，获得 $m_{i1}$个点的魔法值；第 $2$ 种施展方式会消耗 $s_{i2}$~ 个点的能量值，获得 $m_{i2}$~ 个点的魔法值。

考试规定，哈利波特不能让自己的能量值消耗到负数，$N$ 种魔法，他可以任意选择，但每种魔法他最多只能选择其中 $1$ 种施展方式，且最多只能施展 $1$ 次。

请问，哈利波特在本次考试中，魔法值最大能达到多少。

输入

第 $1$ 行有 $3$ 个整数 $S,N,M$，数字之间用空格隔开。

接下来 $N$ 行，每行有 $4$ 个整数，第 $i+1$ 行的 $4$ 个整数代表了第 $i$ 种魔法的 $2$ 种施展方式的 $4$ 个参数 $m_{i1}$ ​, $s_{i1}$ ​, $m_{i2}$ , $s_{i2}$​。

输出

请求出哈里波特在考试中魔法值的最大值。

样例

输入复制

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

输出复制

80

说明

样例 $1$ 说明

初始能量值为 $50$，有 $3$ 种魔法，初始魔法值为 $20$。

第 $1$ 种魔法，选择第 $2$ 种施展方式。

第 $2$ 种魔法，选择第 $1$ 种施展方式。

第 $3$ 种魔法，选择第 $1$ 种施展方式。

总能量消耗$=19+10+20=49$ ，没有超过初始能量的限制，获得魔法$=23+17+20=60$，加上初始魔法值 $20$，可以计算出，魔法值最大可以达到 $80$。

数据范围

对于 $100$% 的数据，$1≤N≤200$，$1≤M,S≤10^{4} ，1≤m_{i},s_{i}≤2×10^{4}$。