전력망

전력망은 여러 노드(발전소, 소비자, 중계기)가 송전선으로 연결되어 이루어진다. 노드 $u$는 전력 $s(u) \ge 0$을 공급받을 수 있고, 전력 $0 \le p(u) \le p_{\max}(u)$을 생산할 수 있으며, 전력 $0 \le c(u) \le \min(s(u), c_{\max}(u))$을 소비할 수 있고, 전력 $d(u) = s(u) + p(u) - c(u)$을 송출할 수 있다. 다음 제약이 적용된다. 발전소는 $c(u) = 0$, 소비자는 $p(u) = 0$, 중계기는 $p(u) = c(u) = 0$이다. 노드 $u$에서 노드 $v$로 가는 송전선 $(u, v)$은 최대 한 개만 존재하며, 이 선은 $u$가 송출한 전력을 $0 \le l(u, v) \le l_{\max}(u, v)$만큼 $v$로 전달한다. 전력망에서 소비되는 총 전력을 $Con = \sum_u c(u)$라고 하자. $Con$의 최댓값을 구하여라.

그림 1. 전력망의 예.

위 예시는 전력망의 유효한 상태 하나를 나타낸다. 발전소 $u$의 라벨 $x/y$는 $p(u) = x$이고 $p_{\max}(u) = y$임을 뜻한다. 소비자 $u$의 라벨 $x/y$는 $c(u) = x$이고 $c_{\max}(u) = y$임을 뜻한다. 송전선 $(u, v)$의 라벨 $x/y$는 $l(u, v) = x$이고 $l_{\max}(u, v) = y$임을 뜻한다. 이 상태에서 소비되는 전력은 $Con = 6$이다. 다른 상태들도 가능하지만 $Con$은 결코 6을 넘을 수 없다.

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 하나의 전력망을 나타낸다. 각 집합은 네 개의 정수로 시작한다. 노드 수 $0 \le n \le 100$, 발전소 수 $0 \le n_p \le n$, 소비자 수 $0 \le n_c \le n$, 송전선 수 $0 \le m \le n^2$이다.

이어서 (u,v)z 형태의 삼중쌍이 $m$개 주어진다. 여기서 $u$와 $v$는 노드 번호(0부터 시작)이고, $0 \le z \le 1000$은 $l_{\max}(u, v)$의 값이다.

이어서 (u)z 형태의 이중쌍이 $n_p$개 주어진다. 여기서 $u$는 발전소의 번호이고, $0 \le z \le 10000$은 $p_{\max}(u)$의 값이다.

마지막으로 (u)z 형태의 이중쌍이 $n_c$개 주어진다. 여기서 $u$는 소비자의 번호이고, $0 \le z \le 10000$은 $c_{\max}(u)$의 값이다.

모든 입력 수는 정수이다. 공백을 포함하지 않는 (u,v)z 삼중쌍과 (u)z 이중쌍을 제외하면, 입력 곳곳에 공백이 자유롭게 나타날 수 있다. 입력은 파일 끝에서 종료되며 항상 올바르다.

각 데이터 집합마다, 해당 전력망에서 소비할 수 있는 전력의 최댓값을 한 줄에 하나씩 출력한다. 모든 결과는 정수이며 각각 새로운 줄의 처음부터 출력한다.