P17492 [EPXLQ 2026] 水果贸易

::::info[为了完成此题，你不需要阅读此题目背景] It was when the sun cast its first glow on Yaoguang Shoal that Ningguang started her trudge from there. The bitter chill hung over Liyue Harbor in the morning. Soil ground undulating under her bare feet, she managed to keep a balance and hold a heavy bundle of fruits, when cold air was flooding into her thin dress. Shivering in the cold, she gathered her breath and called out, hoping to catch attention from people residing nearby. The fruits in her hand became fewer and fewer, and the mora in her worn pocket gradually accumulated. Each of her cautious step seemingly drew her closer to her dream – a life of stability and dignity; and thinking of this, her eyes glittering with unwavering hope though her face numb and reddish in the freezing air. But reality was unkind. A simple calculation revealed a harsh truth in front of her: her income could barely cover her cost at the end of the year. She chose the wrong path where insufficient people were interested in the fruits she sold. Ningguang had dropped out of school due to poverty, after her family’s venture collapsed, which ruined everything that she had envisioned. When the new year came, she wanted to go back. Or she had to go back. Local people did not see the young fruit-seller again until 13 years later, when she topped the list in Liyue’s National Civil Servant Selection Exam. But in a harbor defined by commerce and ambition, such an achievement drew little attention. Another 13 years later, when Ningguang first appeared in the public as new minister, few people could recognize that this dignified figure was once exactly the girl selling fruits along the streets on cold mornings more than two decades ago. One day, Ningguang received a report that Liyue’s national fruit delivery network was faltering. And Ningguang, remembering the weight of the bundle and the cold of the dawn, resolved to act. ::::

璃月的水果贸易网络可以抽象为一棵 $n$ 个节点的树。凝光初始时位于节点 $1$，带着 $c$ 个水果和**足够的钱**（也就是说，条件允许的情况下她可以任意买入水果）。她可以进行下面三种操作无数次： - 在某个节点以 $a_i$ 的单价买入水果（如果可以在该节点买入）。 - 在某个节点以 $b_i$ 的单价卖出水果。 - 将一定量的水果沿树上的边从一个节点移动到另一个节点（如果满足限制）。 此外，由于运输能力限制，连接 $u_j$ 与 $v_j$ 的边**在所有操作中**最多只能通过**总共** $w_j$ 个水果。 在满足上述条件的情况下，凝光希望你求出她能获得的最大利润（售卖水果的总收入减去购买水果的总花费）。

输入第一行为两个整数 $n,c$，表示节点的个数与凝光当前拥有的水果数量。 第二行为 $n$ 个整数 $a_i$，表示在节点 $i$ 购买一个水果的价格。特别地，如果 $a_i = -1$，表示不能在该节点购买水果。保证 $a_1 = -1$。 第三行为 $n$ 个整数 $b_i$，表示在节点 $i$ 卖出一个水果的价格。 以下 $n-1$ 行，每行三个整数 $u_j,v_j,w_j$，表示一条最多通过 $w_j$ 个水果的边。

输出一行一个整数表示答案。 - 如果凝光的利润可以无限大，输出 $-1$。 - 否则，输出一个整数表示凝光的最大利润。

### 数据规模与约定 **本题采用捆绑测试。** | $\text{Subtask}$ | $n \le$ | $c \le$ | $w_i \le$ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | :-: | :-: | | $0$ | $5$ | $5$ | $5$ | | $5$ | | $1$ | $18$ | $18$ | $18$ | | $10$ | | $2$ | $100$ | $10^3$ | $10^3$ | | $11$ | | $3$ | $100$ | $10^6$ | $10^6$ | A | $10$ | | $4$ | $10^3$ | $10^6$ | $10^6$ | B | $11$ | | $5$ | $10^5$ | $10^6$ | $10^6$ | A | $11$ | | $6$ | $10^5$ | $10^6$ | $10^6$ | B | $10$ | | $7$ | $10^5$ | $10^6$ | $10^6$ | C | $10$ | | $8$ | $3 \times 10^5$ | $10^6$ | $10^6$ | D | $8$ | | $9$ | $3 \times 10^5$ | $10^6$ | $10^6$ | | $14$ | 特殊性质 A：若 $i \ne 1$，则 $a_i = b_i$。 特殊性质 B：$a_i = -1$。 特殊性质 C：保证节点 $1$ 与其它点均有边相连。 特殊性质 D：保证节点 $i$ 和节点 $i+1$ 相连。 对于所有数据，保证 $1 \le n \le 3 \times 10^5, 0 \le c,w_j \le 10^6, -1 \le a_i \le 10^6, 0 \le b_i \le 10^6$。 ::::info[AI 使用说明] 本题的【题目背景】经过 DeepSeek 润色，其余部分无 AI 参与。 ::::