쇼핑 특가

가게에서는 상품 종류마다 정가가 정해져 있습니다. 예를 들어 꽃 한 송이의 가격은 2 ICU(Informatics Currency Unit, 정보학 화폐 단위)이고 꽃병 하나의 가격은 5 ICU입니다. 더 많은 손님을 끌기 위해 가게는 몇 가지 특별 할인을 제공합니다.

하나의 특별 할인은 여러 상품을 묶어 정가보다 싼 가격에 파는 것입니다. 예를 들어 꽃 3송이를 원래 가격 6 ICU 대신 5 ICU에 팔거나, 꽃병 2개와 꽃 1송이를 원래 가격 12 ICU 대신 10 ICU에 파는 식입니다.

손님이 사려는 물건들을 특별 할인을 최대한 활용하여 가장 싸게 사는 가격을 구하는 프로그램을 작성하세요. 단, 가격이 더 싸진다고 하더라도 사려는 목록에 없는 물건을 추가로 살 수는 없습니다.

위에서 든 가격과 할인(꽃 2 ICU, 꽃병 5 ICU)을 기준으로 하면, 꽃 3송이와 꽃병 2개를 사는 가장 싼 가격은 14 ICU입니다. 꽃병 2개와 꽃 1송이를 할인가 10 ICU에 사고, 남은 꽃 2송이를 정가 4 ICU에 사면 됩니다.

첫째 줄에는 장바구니에 담긴 서로 다른 상품 종류의 개수 $b$가 주어집니다 ($0 \le b \le 5$). 이어지는 $b$개의 줄에는 각각 세 정수 $c$, $k$, $p$가 주어집니다. $c$는 상품의 서로 다른 고유 번호이고 ($1 \le c \le 999$), $k$는 그 상품이 장바구니에 담긴 개수이며 ($1 \le k \le 5$), $p$는 그 상품 하나의 정가입니다 ($1 \le p \le 999$). 따라서 장바구니에는 최대 $5 \times 5 = 25$개의 물건이 담길 수 있습니다.

그 다음 줄에는 특별 할인의 개수 $s$가 주어집니다 ($0 \le s \le 99$). 이어지는 $s$개의 줄은 각각 하나의 할인을 나타냅니다. 줄의 첫 수 $n$은 그 할인에 포함된 서로 다른 상품 종류의 개수입니다 ($1 \le n \le 5$). 이어지는 $n$개의 정수 쌍 $(c, k)$는 상품 번호 $c$($1 \le c \le 999$)의 물건 $k$개($1 \le k \le 5$)가 그 할인에 포함됨을 뜻합니다. 줄의 마지막 수 $p$는 그 할인의 할인가입니다 ($1 \le p \le 9999$). 각 할인의 할인가는 포함된 물건들의 정가 합보다 항상 작습니다.

입력에 주어진 물건들을 모두 사기 위해 지불해야 하는 가장 낮은 가격을 한 줄에 출력합니다.