F. 咖啡即生命AI (CI翻译)（GLM 5.3 Flash）
题目描述
On his voyage to hunt the elusive white whale, Captain Ahab is swamped with tasks to do during day-to-day life on his ship. The good news is that he has the life-sustaining power of coffee on his side. The bad news is that there is a limited amount of coffee in his ship's hold. There are $n$ days, each with some amount of work $w_i$ to do. Each unit of work costs 1 energy, and every day starts with 0 energy.
在追捕难以捉摸的白鲸的航程中，亚哈船长在船上的日常生活里被各种任务压得喘不过气。好消息是他有维系生命的咖啡之力相助。坏消息是船上货舱里的咖啡数量有限。一共有 $n$ 天，每天都有一定量的工作 $w_i$ 要做。每单位工作消耗 1 点能量，且每天开始时能量为 0。AI (CI翻译)（GLM 5.3 Flash）
There are $m$ cups of coffee that can be drunk on any day. The first coffee drunk on any day gives $k$ energy, the second gives $k-1$ energy, and so on, until the $k^{th}$ coffee gives $1$ energy; any coffee drunk afterward gives no energy.
有 $m$ 杯咖啡，可以在任意一天饮用。在任意一天喝的第一杯咖啡提供 $k$ 点能量，第二杯提供 $k-1$ 点能量，以此类推，直到第 $k^{th}$ 杯咖啡提供 $1$ 点能量；此后喝的咖啡不提供能量。AI (CI翻译)（GLM 5.3 Flash）
Ahab needs your help to ration his coffee to complete as much work as possible.
Ahab 需要你的帮助来ration他的咖啡，以完成尽可能多的工作。AI (CI翻译)（GLM 5.3 Flash）
输入格式
The first line of input contains $n$, $m$, and $k$ ($1 \le n \le 10^5, 1 \le m, k \le 10^9$), the number of days, cups of coffee, and initial energy from coffee, respectively.
输入第一行包含 $n$、$m$ 和 $k$($1 \le n \le 10^5, 1 \le m, k \le 10^9$)，分别表示天数、咖啡杯数以及从咖啡中获得的初始能量。AI (CI翻译)（GLM 5.3 Flash）
The second line contains $n$ integers, $w_1, w_2, ..., w_n$ ($1 \le w_i \le 10^{18}$), the amount of work to be done each day.
第二行包含 $n$ 个整数，$w_1, w_2, ..., w_n$ ($1 \le w_i \le 10^{18}$)，表示每天需要完成的工作量。AI (CI翻译)（GLM 5.3 Flash）
输出格式
The output should be one line containing the maximum possible amount of work that can be done.
输出应为一行，包含可以完成的最大可能工作量。AI (CI翻译)（GLM 5.3 Flash）
备注
It is optimal for Ahab to drink two coffees on the first day, one on the second day, and one on the third day for $5+2+3 = 10$ units of work total.
Ahab 最优的做法是在第一天喝两杯咖啡，第二天喝一杯，第三天喝一杯，总共完成 $5+2+3 = 10$ 单位的工作。AI (CI翻译)（GLM 5.3 Flash）
样例
样例 1
4 4 3
10 2 4 110F2. 远征（困难版本）AI (CI翻译)（GLM 5.3 Flash）
题目描述
This is the hard version of the problem. The difference between the versions is that in this version, the path may end in any cave.
这是本题的困难版本。两个版本的区别在于，在这个版本中，路径可以终止于任意洞穴。AI (CI翻译)（GLM 5.3 Flash）
Henry went on an expedition into a network of caves in search of ancient artifacts. The entrance to the caves is at vertex $1$, and the corridors between caves form a tree.
亨利进入一个洞穴网络探险，以寻找远古遗物。洞穴入口位于顶点 $1$，洞穴之间的通道构成一棵树。AI (CI翻译)（GLM 5.3 Flash）
Henry lights his way with a magic lamp. To pass through the $i$-th corridor, the lamp spends $w_i$ units of charge each time it is traversed.
Henry 用一盏魔法灯照亮前路。每次穿过第 $i$ 条走廊时，灯会消耗 $w_i$ 单位电量。AI (CI翻译)（GLM 5.3 Flash）
However, the cave corridors are extremely unstable. After two traversals of the same corridor, its vault becomes too fragile, and it is impossible to use this corridor a third time. Therefore, Henry may traverse each corridor at most twice, regardless of the direction of movement.
然而，洞穴的通道极其不稳定。同一条通道在被经过两次后，其拱顶就会变得过于脆弱，无法第三次使用这条通道。因此，无论移动方向如何，Henry 最多只能经过每条通道两次。AI (CI翻译)（GLM 5.3 Flash）
There is an artifact in every cave. On the first visit to vertex $v$, the artifact changes the lamp charge by $a_v$ units: some artifacts restore charge (those with $a_v \gt 0$), while others are cursed and instead take it away ($a_v \lt 0$). Visiting the cave again has no effect on the lamp charge.
每个洞穴中都有一个神器。首次访问顶点 $v$ 时，神器会使提灯电量变化 $a_v$ 单位：有些神器会恢复电量(那些具有 $a_v \gt 0$ 的)，而另一些则受到诅咒，反而会扣除电量($a_v \lt 0$)。再次访问该洞穴不会对提灯电量产生任何影响。AI (CI翻译)（GLM 5.3 Flash）
At the beginning of the expedition, Henry is in cave $1$ and immediately activates the artifact there. The lamp charge must never become negative at any moment.
探险开始时，Henry 位于洞穴 $1$ 中，并立即激活了那里的神器。灯的电量在任何时刻都绝不能变为负数。AI (CI翻译)（GLM 5.3 Flash）
Henry must visit all caves and collect all artifacts. After that, he can activate a portal in any cave and leave the dungeon, so he does not need to return to the entrance.
Henry必须访问所有洞穴并收集所有神器。之后，他可以在任意洞穴中激活传送门并离开地牢，因此他无需返回入口。AI (CI翻译)（GLM 5.3 Flash）
Determine the minimum initial lamp charge with which Henry can complete the expedition.
求出 Henry 完成探险所需的最小初始提灯电量。AI (CI翻译)（GLM 5.3 Flash）
输入格式
The first line contains one integer $n$ $(1 \le n \le 2 \cdot 10^5)$ — the number of caves.
第一行包含一个整数 $n$ $(1 \le n \le 2 \cdot 10^5)$ —— 洞穴的数量。AI (CI翻译)（GLM 5.3 Flash）
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(-10^9 \le a_i \le 10^9)$ — the changes in lamp charge after the first visit to the corresponding caves. Note that each corridor can be traversed at most twice, regardless of direction.
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^9 \le a_i \le 10^9)$ —— 首次访问对应洞穴后灯的能量变化。注意，每条走廊无论方向最多只能经过两次。AI (CI翻译)（GLM 5.3 Flash）
The next $n - 1$ lines contain three integers each: $u_i$, $v_i$, and $w_i$ $(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$ — the endpoints of the $i$-th corridor and the amount of charge required to traverse it.
接下来 $n - 1$ 行每行包含三个整数：$u_i$、$v_i$ 和 $w_i$ $(1 \le u_i, v_i \le n,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$ —— 第 $i$ 条走廊的两端点以及通过它所需的电量。AI (CI翻译)（GLM 5.3 Flash）
It is guaranteed that the corridors form a tree.
保证走廊构成一棵树。AI (CI翻译)（GLM 5.3 Flash）
输出格式
Print one integer — the minimum initial lamp charge with which Henry can visit all caves without the lamp charge ever becoming negative.
输出一个整数——亨利能够访问所有洞穴且灯的电量始终不会变为负数所需的最小初始电量。AI (CI翻译)（GLM 5.3 Flash）
样例
样例 1
5
1 10 -2 6 7
1 2 10
1 3 2
3 4 1
3 5 716样例 2
4
2 -90 15 30
1 2 4
2 3 5
1 4 1087