H :: Shares

Time Limit: 2 Seconds    Memory Limit: 131072 KB

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 first line contains the maximum capital C that you can invest (0 < C ≤ 2^30). 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 a_i and t_i 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 share type you have two integers s_j and q_j (1 ≤ j ≤ 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

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

Submit

Source: SWERC 2012