U427556 风与苹果

躺在风起地苍天树下，耳边是吟游诗人的轻唱，微风拂过，塞西莉亚和苹果酿的香气交织，萦绕在你身边。 “旅行者，那里结了个苹果欸” 你循声望去，绿叶遮掩中，真的有一抹鲜红，这几千年的橡树竟然突然结了个苹果。 “把它摘给我呗，可以吗可以吗可以吗”

你需要摘下这颗苹果。 苍天树是一棵 $n$ 个节点的树，**保证节点 $1$ 为根结点**。经过每一条边都需要消耗 $e_{i}$ 的体力，**除根节点外每个节点都**有 $p_{i}$ 个「风种子」，在这棵树上还有 $m$ 对特殊节点，我们称之为「风场」，「风场」是成对出现的，并且只可以从一端传到另一端，**保证不存在一个点上有多个「风场」**。 你每移动一次都会消耗对应边的体力值，收集到达节点的「风种子」，**每个点上的「风种子」只能收集一次**，当你持有的「风种子」值大于 $k$ 时就可以使用「风场」从一端到达另一端，期间不消耗体力，持有「风种子」减少 $k$ 。 你需要找到消耗体力值最小的路线，并输出消耗体力值。

第一行四个整数，分别为 $n、$$m、$ $k$ 和苹果所在节点编号。 接下来一行 $n$ 个整数，代表 $p_{i}$ 。 接下来 $n-1$ 行，每一行分别为一条边的起点、终点和 $e_{i}$ 。 接下来 $m$ 行，表示「风场」的起点和终点。

一行，一个整数，表示最小体力消耗。

对于$50$%的数据，保证 $1 \leqslant n\leqslant 20$ 对于$100$%的数据，保证 $1 \leqslant n\leqslant 10^{3}$，$0 \leqslant m\leqslant 20$，$1 \leqslant k\leqslant 100$ , $1 \leqslant e_{i}、p_{i}\leqslant 20$ 。 样例一解释：$1$ $->$ $2$ $->$ $3$ $->$ $6$ $->$ $9$ 。 样例二解释：$1$ $->$ $2$ $->$ $7$ $->$ $2$ $->$ $3$ $->$ $5$ $->$ $6$ 。 --- Created by [Hf_Poem](https://www.luogu.com.cn/user/750476).