当前没有测试数据。

1.购买商品

题目描述

小明带着$Money$元去商场买礼物。$A$商品有$m$种，已知每种的价钱及价值，且每种商品只能购买一个，剩下的钱买$B$商品。

$B$商品有$n$种，已知每种的价钱及价值，每种可以购买多个。

求小明在购买$A$商品价值之和最大的情况下，购买$B$商品价值之和的最大值。

输入格式

输入文件第一行为一个整数$Money$。

第二行有一个整数$m$，为$A$商品的种类。

以下$m$行每行有两个整数，分别为一种$A$商品的价格$v_1$和价值$g_1$。

再下面有一个整数$n$，为$B$商品的种类。

再下面$n$行每行有两个整数，分别为一种$B$商品的价格$v_2$和价值$g_2$。

输出格式

输出一个整数，即最大的爱情度。

数据范围与提示

对于$100\%$的数据：

• $0 \leq Money \leq 1000000$
• $0 < m < 10$
• $0 < n < 30$
• $0 < v_1, g_1 \leq maxint$
• $0 < v_2, g_2 \leq maxint$

样例

3
1
1 1
1
1 3

6