哈里波特在霍格沃茨魔法学校迎来了第一次魔法考试。
考试开始，哈利波特的能量值为 S，魔法值为 M。本学期，他学习了 N 种魔法，每种魔法都有 2 种不同的施展方式。第 i 种魔法的第 1 种施展方式会消耗 si1 个点的能量值，获得 mi1 个点的魔法值；第 2 种施展方式会消耗 si2 个点的能量值，获得 mi2 个点的魔法值。
考试规定，哈利波特不能让自己的能量值消耗到负数，N 种魔法，他可以任意选择，但每种魔法他最多只能选择其中 1 种施展方式，且最多只能施展 1 次。
请问，哈利波特在本次考试中，魔法值最大能达到多少。
第 1 行有 3 个整数 S,N,M，数字之间用空格隔开。
接下来 N 行，每行有 4 个整数，第 i+1 行的 4 个整数代表了第 i 种魔法的 2 种施展方式的 4 个参数 mi1,si1,mi2,si2。
请求出哈里波特在考试中魔法值的最大值。
50 3 20 12 18 23 19 17 10 30 24 20 20 17 20
80
初始能量值为 50，有 3 种魔法，初始魔法值为 20。
第 1 种魔法，选择第 2 种施展方式。
第 2 种魔法，选择第 1 种施展方式。
第 3 种魔法，选择第 1 种施展方式。
总能量消耗=19+10+20=49，没有超过初始能量的限制，获得魔法=23+17+20=60，加上初始魔法值 20，可以计算出，魔法值最大可以达到 80。
对于 100\% 的数据，1 \le N \le 200，1 \le M,S \le 10^4，1 \le m_i,s_i \le 2 \times 10^4。
东方博宜OJ