되팔렘

되팔렘 민혁이는 매일 아침 물건 시세를 알아보기 위해 온갖 덕질 사이트를 돌아다닙니다. 여느 때처럼 시세를 조사하던 민혁이는 손에 든 핸드폰이 뜨거워지는 것을 느꼈지만 대수롭지 않게 여겼고, 이윽고 핸드폰이 폭발하고 말았습니다!

정신을 차린 민혁이에게는 초능력이 생겼습니다. 중고로운 평화나라에 올라온 물건을 보면, 그 물건을 내일 되팔 때의 가격을 알 수 있게 된 것입니다. 신이 난 민혁이는 이 초능력을 되팔렘의 눈이라고 불렀습니다.

중고로운 평화나라의 탈덕 게시판에서는 덕질을 그만둔 사람들이 물건을 파는데, 자신의 일부와도 같았던 덕질용품들을 한꺼번에 팔아 덕질과의 연을 끊습니다. 즉, 한 사람에게서 물건을 사려면 그 사람의 덕질용품을 전부 사들여야 합니다.

진정한 되팔렘으로 거듭난 민혁이는, 덕질을 그만둔 사람들에게서 덕질용품을 사들여 내일 비싼 값에 되팔려고 합니다. 가진 자본금을 넘지 않게 물건을 사들일 때, 어떤 사람들에게서 사야 내일 얻는 이익을 최대로 만들 수 있을까요?

첫 번째 줄에는 오늘 되팔렘이 가진 자본금 $C$가 주어집니다. ($0 < C \le 2^{30}$)

두 번째 줄에는 두 정수 $N$과 $P$가 주어집니다. $N$은 덕질용품의 종류 수, $P$는 물건을 파는 사람의 수입니다. ($0 < N \le 500$, $0 < P \le 50000$)

이어지는 $N$개의 줄에는 각각 두 정수 $a_i$와 $t_i$가 주어집니다. $a_i$는 $i$번째 덕질용품의 현재 가격, $t_i$는 되팔렘의 눈으로 알아낸 내일 가격입니다. ($1 \le i \le N$이며, 이 $i$를 품번이라고 부릅니다.)

마지막으로 $P$개의 줄에는 각 사람이 파는 덕질용품의 정보가 주어집니다. 각 줄은 그 사람이 가진 덕질용품의 종류 수 $R$로 시작하고, 그 뒤로 그 사람이 파는 덕질용품의 품번 $s_j$와 그 개수 $q_j$가 차례로 주어집니다. ($1 \le j \le R$)

되팔렘이 내일 낼 수 있는 최대 이익을 출력합니다.