You are a successful business man who uses to invest some money in the shares market. As a successful man you manage a network of well prepared spies assistants that can assure you the values of the shares for the next day. Each day you have a capital that you can spend in the market according to your assistants suggestions. In addition, you can only buy packs of shares from several salesmen.
Your goal is to select which packs should be bought in order to maximize the profits without exceeding the amount of capital you have.
The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.
The first line contains the maximum capital C that you can invest ( 0 < C230). The next line has two integers, the number of total shares N ( 0 < N500) and the number of packs P ( 0 < P50000). Each one of the following N lines describe the N shares. Each line contains two integers ai and ti representing the current price and the expected price for the next day of the ith share ( 1iN), respectively. Finally, the following P lines contain the information of the packs, one per line. For each line, the first integer R represents the number of different shares that contains this pack. Then for each share type you have two integers sj and qj ( 1jR), where sj is the id of the jth share and qj is the quantity of the jth share in this pack.
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
An integer that indicates the maximum expected profit for the next day.
500 4 6 10 15 8 6 20 15 12 12 3 1 6 2 7 3 8 3 3 8 1 10 2 4 3 4 10 2 5 1 10 2 1 4 2 4 1 3 2 2 4 3 2 1 200000000 5 30 2800 3500 1400 4800 2900 2800 500 3800 3300 4700 2 2 13 4 15 4 4 1 1 22 3 17 5 22 1 3 2 1 3 6 4 1 11 2 5 3 7 5 15 1 5 1 4 2 26 1 21 3 8 5 26 2 3 5 2 26 4 2 30 4 12 3 7 5 14 3 3 8 2 20 5 3 1 5 30 2 1 29 3 3 5 3 3 1 20 5 26 4 9 2 25 3 1 2 2 16 3 5 2 5 5 4 26 5 2 18 5 10 4 18 1 12 3 30 3 2 5 3 27 5 4 4 3 2 4 8 1 20 2 6 3 2 14 1 1 4 22 5 2 23 3 26 1 27 5 3 4 6 1 2 16 4 1 13 4 10 2 23 5 2 1 1 14 1 2 20 1 3 14 2 3 21 1 22 1 2 27 3 5 24 1 26 3 13 5 4 15 3 3 2 21 1 5 5 16 4 2 22 5 1 4 10 1 30
52 2168800