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.

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 $\le$ 2³⁰). The next line has two integers, the number of total shares N ( 0 < N $\le$ 500) and the number of packs P ( 0 < P $\le$ 50000). Each one of the following N lines describe the N shares. Each line contains two integers a_i and t_i representing the current price and the expected price for the next day of the ith share ( 1 $\le$ i $\le$ 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 share type you have two integers s_j and q_j ( 1 $\le$ j $\le$ R), where s_j is the id of the jth share and q_j 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
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

Sample Output

52

2168800