P3652 csh和zzy的战争

（背景~~有点~~长，你可以选择读完，也可以选择跳过。） 公元 2040 年，csh 和 zzy 在丑国蛙谷展开了关于非线性配微分方程的正确性与否的相关辩论，史称第四次数学危机。两个人近千页的非人类学术性论文，使整个世界没有其他人听得懂他们在说什么，于是，以 csh 为首的 A 派科学家和以 zzy 为首的 B 派科学家展开了在多次对抗无果之后开始使用武装革命解决，进而引发了全球性的第三次世界大战。作为战争中立派的居润国不想卷入任何一方的斗争，只想喝完手中的咖啡，然而两方元首在多次对抛出橄榄枝无果之后，对居润国提出了一个要求：解决他们在战争中的运送物资问题，当然这个问题早就在 $10^0$ s 内被他们解决，但是居润国却不知道怎么办，而且也不能报上错误的答案，于是就求助了聪明的你们。

现在有 $n$ 个货物发源地，里面是一些待运送的货物。前方有 $m$ 个中转小岛，而你的目的是将所有货物运到战争前沿的军事基地，其运送规则如下： 1. 小岛只能由特定的货物发源地发货，其中只有几个指定的小岛可以向军事基地发货。 2. 小岛与小岛之间有 $e$ 条航道，每条航道上有一个权值 $v$ 代表这条道路开通的代价，而两个小岛之间开通货运的代价 $K$ 是两个小岛之间的最短路径长度。 3. 每个小岛上同时最多不能超过 $w$ 个货物。 4. 每个小岛一次性至多对外运输 $d$ 个货物，小岛对每个目的地至多送货一次。 5. 有 $x$ 个特殊货物发源地（不包含在 $n$ 内）会运送 csh 和 zzy 两个人的一些私人的货物，这些货物会被任何一个小岛无条件接受和送出，即不受 3，4 法则的影响。 6. 整条航路的开发费用为每对小岛开通费用 $K$ 中的最大值 $V$。 请你寻找一个最小的 $V$ 使得所有货物都能按照要求运送到军事基地。

第一行 $n$，$m$，$x$，$e$，分别表示货物发源地数目，小岛中转站数目，特殊货物发源地数目和航道数目，货物发源地和特殊货物发源地依次标号为 $1$，$2$，$ \dots $，$n+x$。 第二行是 $n+x$ 个数 $a_i$，分别每个货物发源地待发送的货物数量。 第三行是 $m$ 个数，分别表示小岛的限制存货量 $w$。 第四行也是 $m$ 个数，分别表示小岛的限制出货量 $d$。 接下来 $m$ 行，每行开头是一个数 $k$ ，表示有 $k$ 个货物发源地（包括特殊货物发源地）与小岛相连，然后是 $k$ 个数，分别表示货物发源地的编号，最后一个数表示小岛是否与军事基地相连，是则为$1$，否则为$0$。 接下来 $e$ 行，每行是三个数 $u$，$v$，$p$ 表示小岛 $u$，$v$ 之间航道的权值为 $p$。

一个整数 $V$ ，表示使得所有货物都能按照要求运送到军事基地最小开通费用。

对于 $100\%$ 的数据， $n \le 3 \times 10^2$，$e \le 10^3$。 几个提示：[https://www.luogu.com.cn/discuss/47710](https://www.luogu.com.cn/discuss/47710)。