장인

일본 전역에서 많은 의뢰가 들어오는 유명한 장인 Takeshi가 있다. 그러나 지금 쓰고 있는 도구는 너무 낡았다. 그래서 그는 새 도구를 사서 다음에 도구를 사용하기 전에 낡은 도구를 교체하려 한다. 어떤 의뢰는 도구 교체를 요구하므로 그에게 비용이 발생할 수도 있다. 따라서 받은 주문을 모두 수락하는 것이 항상 최선은 아니다. 이제 당신은 그의 제자 중 한 명이다. 주어진 주문 목록과 도구 가격에 대해 그의 수익을 최대화하는 수락할 주문 집합을 계산하는 것이 당신의 임무다. 그의 수익은 판매 수입과 교체 비용으로 인해 오르내릴 수 있다.

그는 항상 친구 가게에서 도구를 산다. 가게에서는 일부 물품 쌍을 동시에 구매하면 가격을 할인해 준다. 할인도 고려해야 한다. 지불할 총액은 개별 가격의 단순한 합과 같지 않을 수 있다.

가게의 모든 도구는 충분히 튼튼하다고 가정해도 된다. Takeshi는 이번에 교체한 도구로 모든 주문을 완료할 수 있다. 따라서 각 종류의 도구는 많아야 하나만 사면 된다.

입력은 다음 형식을 따른다:

N M P
X1 K1 I1,1 ... I1, K1
...
XN KN IN,1 ... IN, KN
Y1
...
YM
J1,1 J1,2 D1
...
JP,1 JP,2 DP

여기서 N, M, P는 각각 주문의 수, 가게에서 파는 도구의 수, 할인 가능한 물품 쌍의 수다.

다음 N개의 줄은 주문의 세부 사항을 나타낸다. Xi는 i번째 주문의 보수이고, Ki는 그 주문을 완료하는 데 필요한 도구의 수다. 각 줄의 나머지 부분은 주문을 완료하는 데 필요한 도구를 나타낸다. 도구는 1부터 M까지의 정수로 지정된다.

다음 M개의 줄은 Takeshi 친구 가게의 가격표다. 정수 Yi는 i번째 도구의 가격을 나타낸다.

각 테스트 케이스의 마지막 P개의 줄은 할인 대상 물품 쌍을 나타낸다. Takeshi가 Ji,1번째 도구와 Ji,2번째 도구를 동시에 사면, 개별 가격의 합 대신 Di엔만 지불하면 된다. 할인 목록에 어떤 도구도 두 번 이상 나오지 않으며, 모든 할인 가격에 대해 max{Yi, Yj} < Di,j < Yi + Yj임이 보장된다. 여기서 Di,j는 i번째 도구와 j번째 도구를 동시에 살 때의 할인 가격이다.

또한 1 ≤ N ≤ 100, 2 ≤ M ≤ 100, 1 ≤ Ki ≤ 100, 1 ≤ P ≤ M/2, 1 ≤ Xi, Yi ≤ 1000임이 보장된다.

Takeshi가 얻을 수 있는 최대 수익을 표준 출력으로 출력한다.