Problem D
Shares

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 \leq 2^{30}$). The next line has two integers, the number of total shares $N$ ($ 0 < N \leq 500 $) and the number of packs $P$ ($ 0 < P \leq 50\, 000 $). 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 $i$-th share ($0 < a_ i, t_ i \leq 2^{30}$), 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 ($1 \leq R \leq N$). Then for each share type you have two integers $s_ j$ and $q_ j$, where $s_ j$ is the id of the $j$-th share ($1 \leq s_ j \leq N$) and $q_ j$ is the quantity of the $j$-th share in this pack ($0 < q_ j \leq 2^{30}$).

Output

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

52