题目描述
已知现在小 A 一共有一定的钱 $y$ 元，猫的饲料有 $m$ 种，每种的质量为定值，已知每种的价钱，且每种只能买一袋，这样其剩下的钱就可以给小 B 买巧克力了。又已知巧克力店有 $x$ 种巧克力，每支有一定的价钱，爱情度为定值，巧克力可以一次性买同种的多块。 现在小 A 想让猫吃最饱的前提下，又想使其送给女朋友小 B 的巧克力的爱情度尽可能的大，请你帮他设计一个方案，解决这个问题。
输入
输入文件第一行为一个整数 $y$，即小A所有的钱。
第二行有一个整数 $m$，为猫饲料的种类。
以下 $m$ 行有两个中间有空格连接的整数 $jg、zl$，其中 $jg$ 为该种饲料的的价格，$zl$ 为该种饲料的质量。
再下面一行是超市巧克力的种类 $x$。
再下面 $x$ 行有两个中间有空格连接的整数 $v,l$，其中 $v$ 为该巧克力的价格， $l$为该种巧克力所拥有的爱情度。
输出
输出格式为一个整数，即最大的爱情度。
样例输入输出
提示
对于 $100\%$ 的数据，$0 \leq y \leq 1000000$，$0 < m < 10$，$0 < jg,zl \leq maxint$，$0 < x < 30$，$0 < v,l \leq maxint$。