一个电网包含一些结点(电站、消费者、调度站)，这些结点通过电线连接。每个结点 u 可能被供给 s(u) 的电能，s(u)≥0，同时也可能产生p(u) 的电能，0≤p(u)≤pmax(u)；站点 u 还有可能消费 c(u) 电能，0≤c(u)≤min(s(u), cmax(u) )，可能传输 d(u) 的电能，d(u)=s(u)+p(u)- c(u)。以上这些量存在以下限制关系：对每个电站，c(u) = 0；对每个消费者，p(u) = 0；对每个调度站，p(u) = c(u) = 0。 在电网中两个结点 u 和 v 之间最多有一条电线连接。从结点 u 到结点 v 传输 L(u, v) 的电能，0≤L(u, v)≤L_{max(u, v)}。定义 C 为各消费者结点的 c(u) 的总和，表示电网中消费电能的总和。本题的目的是求 C 的最大值。

输入文件包含多个测试数据。每个测试数据描述了一个电网。首先是 4 个整数 n、np、nc、m，其中，0≤n≤100，代表结点数目，0≤np≤n，代表电站数目，0≤nc≤n，代表消费者数目，0≤m≤n2，代表传输电线的数目。接下来有 m 个三元组 (u,v)z，其中，u 和 v 为结点序号(结点序号从 0 开始计起)，0≤z≤1000，代表 L_{max(u, v)} 的值。接下来有 np 个二元组 (u)z，其中 u为电站结点的序号，0≤z≤10000，代表 pmax(u) 的值。每个测试数据的最后是 nc 个二元组 (u)z，其中，u 为消费者结点的序号，0≤z≤10 000，代表 cmax(u) 的值。所有数据都是整数。除三元组 (u,v)z 和二元组(u)z 中不含空格外，输入文件中其他位置允许出现空格。测试数据一直到文件尾。

对每个测试数据所描述的电网，输出一个整数，表示电网能消费电能的最大值。