Power Network

A power network consists of nodes (power stations, consumers, and dispatchers) connected by power transport lines. A node $u$ may be supplied with an amount $s(u) \ge 0$ of power, may produce an amount $0 \le p(u) \le p_{\max}(u)$ of power, may consume an amount $0 \le c(u) \le \min(s(u), c_{\max}(u))$ of power, and may deliver an amount $d(u) = s(u) + p(u) - c(u)$ of power. The following restrictions apply: $c(u) = 0$ for any power station, $p(u) = 0$ for any consumer, and $p(u) = c(u) = 0$ for any dispatcher. There is at most one power transport line $(u, v)$ from a node $u$ to a node $v$ in the network; it transports an amount $0 \le l(u, v) \le l_{\max}(u, v)$ of power delivered by $u$ to $v$. Let $Con = \sum_u c(u)$ be the total power consumed in the network. Your task is to compute the maximum possible value of $Con$.

Figure 1. A power network.

The example above illustrates one valid state of the network. The label $x/y$ of a power station $u$ means $p(u) = x$ and $p_{\max}(u) = y$. The label $x/y$ of a consumer $u$ means $c(u) = x$ and $c_{\max}(u) = y$. The label $x/y$ of a power transport line $(u, v)$ means $l(u, v) = x$ and $l_{\max}(u, v) = y$. Here the power consumed is $Con = 6$. There are other possible states of the network, but the value of $Con$ can never exceed 6.

The input contains several data sets. Each data set encodes one power network. It begins with four integers: the number of nodes $0 \le n \le 100$, the number of power stations $0 \le n_p \le n$, the number of consumers $0 \le n_c \le n$, and the number of power transport lines $0 \le m \le n^2$.

Then follow $m$ triplets of the form (u,v)z, where $u$ and $v$ are node identifiers (numbered from 0) and $0 \le z \le 1000$ is the value of $l_{\max}(u, v)$.

Then follow $n_p$ doublets of the form (u)z, where $u$ is the identifier of a power station and $0 \le z \le 10000$ is the value of $p_{\max}(u)$.

The data set ends with $n_c$ doublets of the form (u)z, where $u$ is the identifier of a consumer and $0 \le z \le 10000$ is the value of $c_{\max}(u)$.

All input numbers are integers. Apart from the (u,v)z triplets and the (u)z doublets, which contain no white space, white space may appear freely in the input. The input terminates at end of file and is guaranteed to be correct.

For each data set, print on a separate line the maximum amount of power that can be consumed in the corresponding network. Every result is an integer and is printed starting at the beginning of its own line.