Power Network

A power network contains power stations, consumers, dispatchers, and directed transport lines. Station u can produce at most p_{max}(u), consumer u can consume at most c_{max}(u), and directed line (u,v) can transport at most l_{max}(u,v). Dispatchers neither produce nor consume. Flow is conserved at every node. Find the maximum total power consumed.

In the figure, an x/y label shows current flow or production/consumption x and capacity y.

Input

The input contains data sets until end of file. Each begins with four integers n,n_p,n_c,m: the numbers of nodes, power stations, consumers, and directed lines, where 0 \le n \le 100, 0 \le n_p,n_c \le n, and 0 \le m \le n^2.

Next come m triplets (u,v)z, giving directed-line capacities. Then come n_p doublets (u)z giving station capacities, followed by n_c doublets (u)z giving consumer capacities. Node IDs start at 0. Line capacities are at most 1000; station and consumer capacities are at most 10000. Whitespace may occur freely between complete triplets or doublets.

Output

For each data set, print the maximum total consumed power.

Example

Input:

2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7
(3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5
(0)5 (1)2 (3)2 (4)1 (5)4

Output:

15
6