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 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. Obviously, you can buy each pack only once. Input 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 < C ≤ 230). The next line has two integers, the number of total shares N (0 < N ≤ 500) and the number of packs P (0 < P ≤ 50000). 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 (1 ≤ i ≤ N), 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 sharetypeyouhavetwointegerssj andqj (1≤j≤R),wheresj istheidofthejthshareandqj is the quantity of the jth share in this pack. Output 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. Sample Input 500 46 10 15 86 20 15 12 12 3162738 3 3 8 1 10 2 4 3 4 10 2 5 1 10 21424 132 24321 200000000 5 30 2800 3500 1400 4800 2900 2800
2/2 500 3800 3300 4700 2 2 13 4 15 4 4 1 1 22 3 17 5 22 132 136 4 1 11 2 5 3 7 5 15 151 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 Sample Output 52 2168800