P3652 The War of csh and zzy

(The background is a bit long. You may read it through or skip it.) In A.D. 2040, csh and zzy held a debate in the Frog Valley of the Ugly Country about the correctness of nonlinear partial differential equations, later known as the Fourth Crisis in Mathematics. Their nearly thousand-page, inhumanly academic papers left everyone else unable to understand what they were saying. Consequently, scientists of faction A led by csh and faction B led by zzy, after many fruitless confrontations, turned to armed revolution, triggering the global Third World War. The neutral country Jurun, not wishing to be dragged into the struggle, only wanted to finish its coffee. However, after repeatedly extending an olive branch in vain, the two leaders提出了一个要求: to resolve their logistics problem during the war. Of course, they solved this problem within $10^0$ s, but Jurun did not know what to do and could not submit a wrong answer, so they turned to you smart people for help.

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.

- 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 a single integer $V$, the minimal development cost that allows all goods to be delivered to the military base while satisfying the rules.

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