2640: 省钱买巧克力

因全球金融危机，GoldenSun的经济有点困难了。为了凑齐给Yoyo_Yao买巧克力的钱，他只得从自己家里唯一的猫的饲料费中扣除了。

已知现在GoldenSun一共有一定的钱y元，猫的饲料有m种，每种的质量为定值，已知每种的价钱，且每种只能买一袋，这样其剩下的钱就可以给Yoyo_Yao买巧克力了。又已知巧克力店有x种巧克力，每支有一定的价钱，爱情度为定值，巧克力可以一次性买同种的多块。

现在GoldenSun想尽量喂饱猫，又想使其送给女朋友Yoyo_Yao的巧克力的爱情度尽可能的大，请你帮他设计一个方案，解决这个问题。

第一行为一个整数y，即GoldenSun所有的钱。(0<y<=1000000)

第二行有一个整数m，为猫饲料的种类。(0<m<10)

以下m行有两个中间有空格连接的整数jg、zl，其中jg为该种饲料的的价格，zl为该种饲料的质量。(0<jg,zl<=maxint)

再下面一行是超市巧克力的种类x。(0<x<30)

再下面x行有两个中间有空格连接的整数v、l，其中v为该巧克力的价格，l为该种巧克力所拥有的爱情度。(0<v,l<=maxint)

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

3
1
1 1
1
1 3

6