Description

一个电力网络由通过电力传输线连接的节点（发电站、用户和中转站）组成。对于节点$u$ ，其他节点为其提供的功率$s (u )≥0$，生产功率$0≤p (u )≤p_{max} (u )$，消耗功率$0≤c (u)≤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 到v 的传输功率$0≤l (u , v )≤l _{max} (u , v )$。设$Con=∑_uc (u )$为网络中的消耗功率，请计算$Con$的最大值。

图中发电站$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$。

Format

Input

输入包含多个数据集。

每个数据集都以4个整数为开头：$0≤n ≤100$（节点）、$0≤np ≤n$（发电站）、$0≤nc ≤n$ （用户）和$0≤m ≤n^2$ （输电线）。

接下来输入$m$ 个三元组$(u , v )z$ ，其中$u$和 $v$ 是节点编号（从$0$开始），$0≤z ≤1000$是$l_{max} (u , v )$的值。

接着输入$np$ 个二元组$(u )z$ ，其中$u$ 是发电站编号，$z$ 是$p_{max} (u )$的值， $0≤z ≤10000$。数据集以$nc$ 个二元组$(u )z$结尾，其中$u$ 是用户编 号，$z$ 是$c_{max} (u )$的值，$0≤z≤10000$。

所有输入的数字都是整数。除了$(u, v )z$ 三元组和$(u )z$ 二元组不包含空格，在输入中都可以自由出现空格。

Output

对每个数据集都单行输出在网络中消耗的最大功率。

Samples

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

15
6

来源

POJ1459