어떤 가게에 각 물건 마다 정수 단위로 가격이 매겨져 있다. 예를 들어 하나의 꽃은 2 원 꽃 병의 가격은 5 원 ...

손님들의 관심을 끌기 위해 특별한 바겐 세일을 하기로 했다.

예를 들어 3 개의 꽃을 사면 6 원이 아닌 5 원으로 , 한송이 꽃과 2 개의 꽃 병을 사면 12 원이 아닌 10 원으로

가장 최적의 가격으로 살수 있는 가격을 출력하는게 문제이다. 단, 물건 값을 더 낮추기 위해서 물품을 추가해서는 안된다.

위에서 주어진 가격으로 3 송이 꽃과 두 개의 꽃병을 사기위한 가격은 14 원이다. 2 개의 꽃 병과 한 송이를 사는데 10 원 + 두 송이 꽃을 정상 가격으로 사는데 4 원

입력 형식

• 첫 줄에는 세일하는 물품의 수가 주어진다. (0 <= s <= 99).
• 다음 s 줄에는 할인하는 물품의 묶음 수 n (1 <= n <= 5) 이 주어진다. 다음에는 c , k 의 쌍으로 n 개가 주어진다. c ( 1 <= c <= 999) 는 물건의 코드번호이고 k 는 이 물건의 개수( 1 <= k <= 5) 이다. 마지막 수 p 는 할인된 가격을 나타낸다 ( 1 <= p <= 9999 ) . 할인가는 정상가보다 항상 싸다.
• 다음 줄에는 사야 하는 물건의 수 b 가 주어진다. (0 <= b <= 5)
• 다음 b 줄에는 세 개의 정수가 주어진다. c 는 물건의 코드 번호이고 ,k 는 사야할 물건의 수이고 (1 <= k <= 5) , 다음 p (1 <= p <= 999) 는 이 물건의 가격이다. 최대 5*5 = 25 개의 물건을 배스킷에 담을수 있다.

출력 형식

입력과 출력의 예

 
입력

2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5

출력

14

입출력 보충

출처: ioi