Description

There are $n$ cargo origins, each with some goods to be shipped. Ahead are $m$ transfer islands, and your goal is to deliver all goods to the front-line military base. The shipping rules are as follows:

1. Each island can accept goods only from specific cargo origins, and only certain designated islands can ship to the military base.
2. There are $e$ sea lanes between islands. Each sea lane has a weight $p$ representing the cost to open that lane. For any two islands, the cost $K$ to enable cargo shipping between them equals the length of the shortest path between them (sum of edge weights).
3. At any time, the number of goods simultaneously stored on an island must not exceed its storage limit $w_i$.
4. Each island can ship out at most $d_i$ goods in total, and to each destination it can deliver at most once.
5. There are $x$ special cargo origins (not included in $n$) that carry some private goods of csh and zzy. These goods will be unconditionally accepted and forwarded by any island, i.e., they are not subject to rules 3 and 4.
6. The development cost of the entire route equals $V$, the maximum $K$ among all pairs of islands for which shipping is enabled.

Find the minimal $V$ such that all goods can be delivered to the military base in accordance with the above rules.

Input Format

• The first line contains $n$, $m$, $x$, $e$, denoting the number of cargo origins, the number of transfer islands, the number of special cargo origins, and the number of sea lanes, respectively. The cargo origins and special cargo origins are indexed $1, 2, \dots, n + x$ in order.
• The second line contains $n + x$ integers $a_i$, the amount of goods pending shipment at each cargo origin.
• The third line contains $m$ integers, the storage limits $w_i$ of the islands.
• The fourth line contains $m$ integers, the outbound shipping limits $d_i$ of the islands.
• The next $m$ lines describe the connections from origins to islands. Each line starts with an integer $k$, the number of cargo origins (including special ones) connected to this island, followed by $k$ integers listing the indices of those origins, and finally one integer indicating whether this island is connected to the military base (1 for yes, 0 for no).
• The next $e$ lines each contain three integers $u$, $v$, $p$, indicating there is a sea lane between islands $u$ and $v$ with weight $p$.

Output Format

Output a single integer $V$, the minimal development cost that allows all goods to be delivered to the military base while satisfying the rules.

2 3 1 1
2 2 2
4 4 4
2 1 1
1 1 1
1 2 1
1 3 1
2 3 4

4

Hint

Constraints: For $100\%$ of the testdata, $n \le 3 \times 10^2$, $e \le 10^3$.

Several tips: https://www.luogu.com.cn/discuss/47710.

Translated by ChatGPT 5