Problem Description
N items are to be processed with two product lines. YY operates the first line, and LMY operates the second. YY can use X processing modes for the first product
line, with his ith mode, processing an item costs Ai units of material while the item’s value increases by Pi units. Similarly LMY can use Y modes for the second
product line, with her ith mode processing an item will cost Bi units of material and get Qi units of value increment. All items must be processed in both of the
product lines, each with one of their modes, to satisfy both YY and LMY. Note that when processing an item with some mode of a product line, the cost and value
increment are totally irrelevant to the mode chosen in the other line. YY and LMY want the value increment of the items to be maximized, but there are only M
units of material available. So they have to choose their modes carefully, use no more than M units of material and still make the value increment as large as possible.
Input
The input file contains several test cases.
The first line of each test case contains two integers N and M indicating the number of items to be processed and the quantity of material available. The next line
contains an integer X, the number of modes YY has. X lines follow, the ith line of which contains two integers Ai and Pi, the material utilized and the value
increased by YY’s ith mode of the first product line. The next line contains an integer Y, the number of modes LMY has. Y lines follow, the ith line of which contains
two integers Bi and Qi, the material utilized and the value increased by LMY’s ith mode of the second product line.
All integers except N are less than or equal to 800 and non-negative, while X and Y are always positive. N is a non-negetive integer no more than 100000.
A line with N=M=0 indicates the end of input, and should not be processed.
Output
For each test case, output one line containing an integer, the maximum value increment after YY and LMY have processed all the N items with no more than M
units of material cost.
Sample Input
3 100
1
1 1
1
2 2
0 0
Sample Output
9
