Reseller's Eye

Every morning, Minhyuk the reseller browses all sorts of fan-hobby sites to check the going prices of goods. While researching prices as usual, he felt the phone in his hand getting hot but paid it no mind, and before long the phone exploded!

When he came to, Minhyuk had gained a superpower: whenever he sees an item posted on the Peaceful Secondhand Land marketplace, he can tell the price at which he could resell that item tomorrow. Delighted, he named this power the Reseller's Eye.

On the marketplace's 'quitting the hobby' board, people who have given up their hobby sell their goods; they part with their beloved collectibles all at once to sever their ties. In other words, to buy from a person, you must buy all of that person's collectibles.

Now a true reseller, Minhyuk wants to buy collectibles from these people and resell them at a high price tomorrow. Buying without exceeding his capital, from which people should he buy to maximize the profit he makes tomorrow?

The first line contains $C$, the capital the reseller has today. ($0 < C \le 2^{30}$)

The second line contains two integers $N$ and $P$: $N$ is the number of kinds of collectibles, and $P$ is the number of people selling goods. ($0 < N \le 500$, $0 < P \le 50000$)

Each of the next $N$ lines contains two integers $a_i$ and $t_i$: $a_i$ is the current price of the $i$-th collectible and $t_i$ is its tomorrow price revealed by the Reseller's Eye. ($1 \le i \le N$; this $i$ is called the item number.)

Finally, $P$ lines describe the collectibles each person sells. Each line begins with $R$, the number of kinds of collectibles that person has, followed by the item number $s_j$ and the count $q_j$ of each collectible that person sells. ($1 \le j \le R$)

Print the maximum profit the reseller can make tomorrow.