되팔렘

되팔렘 민혁이는 매일 아침 물건 시세를 알아보기 위해 온갖 덕질 사이트들을 돌아다닌다. 평소와 같이 시세를 조사하던 민혁이는 손에 들린 핸드폰이 뜨거워짐을 느꼈지만 신경을 쓰지 않았고 이윽고 핸드폰이 폭발하고 말았다!

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

중고로운 평화나라의 탈덕 게시판에서는 덕질을 그만둔 사람들이 물건을 파는데 자신의 일부와도 같았던 덕질용품들을 한꺼번에 팔아 덕질과의 연을 끊도록 되어있다.

진정한 되팔렘으로 거듭난 민혁이는 덕질을 그만둔 사람들에게서 그들의 덕질용품을 모두 사들여 비싼 값에 되팔려고 한다. 과연 어떤 사람들에게서 물건을 사들여야 엄청난 이득을 내는 되팔렘이 될 수 있을까?

첫 번째 줄에는 오늘 되팔렘이 가진 자본금 C가 입력된다. (0 < C ≤ 230)

다음 줄에는 두개의 정수가 입력되는데 하나는 덕질용품의 개수 N과 물건들을 팔려고 하는 사람들의 수 P다. (0 < N ≤ 500), (0 < P ≤ 50000)

이후 N개의 줄에서는 두 개의 정수가 입력되는데 각 줄에는 i 번째 덕질용품의 현재 가격인 ai와 되팔렘의 눈으로 알아낸 이 물건의 내일 가격 ti 이다.  (1 ≤ i ≤ N) (i는 품번이라고 부른다)

마지막으로는 P개의 줄이 입력되는데 각 줄에는 사람이 파는 덕질용품들의 정보다. 처음에는 이 사람이 가진 덕질용품의 종류 수 R이 입력된다. 그 뒤로는 이 사람이 파는 덕질용품의 품번 sj와 갖고 있는 개수 qj가 입력된다. (1 ≤ j ≤ R)

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