描述
一个电力网络由节点（发电站、消费者和调度员）通过电力传输线连接而成。节点 $u$ 可以被供应 $s(u) \geq 0$ 的电力，可以生产 $0 \leq p(u) \leq p_{\text{max}}(u)$ 的电力，可以消耗 $0 \leq c(u) \leq \min(s(u), c_{\text{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)$；它输送的电力为 $0 \leq l(u,v) \leq l_{\text{max}}(u,v)$，由 $u$ 输送到 $v$。设 $Con = \sum_u c(u)$ 为网络中消耗的总电力。问题在于计算 $Con$ 的最大值。

图1中给出了一个例子。发电站 $u$ 的标签 $x/y$ 表示 $p(u) = x$ 且 $p_{\text{max}}(u) = y$。消费者 $u$ 的标签 $x/y$ 表示 $c(u) = x$ 且 $c_{\text{max}}(u) = y$。电力传输线 $(u,v)$ 的标签 $x/y$ 表示 $l(u,v) = x$ 且 $l_{\text{max}}(u,v) = y$。消耗的电力为 $Con = 6$。注意，网络可能存在其他状态，但 $Con$ 的值不会超过6。

输入

输入中包含多个数据集。每个数据集编码一个电力网络。它以四个整数开头：

• $0 \leq n \leq 100$（节点数），
• $0 \leq np \leq n$（发电站数），
• $0 \leq nc \leq n$（消费者数），
• $0 \leq m \leq n^2$（电力传输线数）。

接下来是 $m$ 个数据三元组 $(u,v)z$，其中 $u$ 和 $v$ 是节点标识符（从0开始），$0 \leq z \leq 1000$ 是 $l_{\text{max}}(u,v)$ 的值。然后是 $np$ 个数据对 $(u)z$，其中 $u$ 是发电站的标识符，$0 \leq z \leq 10000$ 是 $p_{\text{max}}(u)$ 的值。数据集以 $nc$ 个数据对 $(u)z$ 结束，其中 $u$ 是消费者的标识符，$0 \leq z \leq 10000$ 是 $c_{\text{max}}(u)$ 的值。所有输入数字均为整数。除了 $(u,v)z$ 三元组和 $(u)z$ 数据对（不包含空格），输入中的其他位置可以自由出现空格。输入数据以文件结束符终止，并且是正确的。

输出

对于输入中的每个数据集，程序在标准输出上打印该对应网络中可消耗的最大电力值。每个结果均为整数，并从单独一行的开头开始打印。

输入数据 1

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  

输出数据 1

15  
6  

提示

示例输入包含两个数据集。第一个数据集编码了一个具有2个节点的网络，发电站0的 $p_{\text{max}}(0) = 15$，消费者1的 $c_{\text{max}}(1) = 20$，以及两条电力传输线，其 $l_{\text{max}}(0,1) = 20$ 和 $l_{\text{max}}(1,0) = 10$。$Con$ 的最大值为15。第二个数据集编码了图1中的网络。

来源

Southeastern Europe 2003