风与苹果

题目背景

躺在风起地苍天树下，耳边是吟游诗人的轻唱，微风拂过，塞西莉亚和苹果酿的香气交织，萦绕在你身边。

“旅行者，那里结了个苹果欸”

你循声望去，绿叶遮掩中，真的有一抹鲜红，这几千年的橡树竟然突然结了个苹果。

“把它摘给我呗，可以吗可以吗可以吗”

题目描述

你需要摘下这颗苹果。

苍天树是一棵 $n$ 个节点的树，保证节点 $1$ 为根结点。经过每一条边都需要消耗 $e_{i}$ 的体力，除根节点外每个节点都有 $p_{i}$ 个「风种子」，在这棵树上还有 $m$ 对特殊节点，我们称之为「风场」，「风场」是成对出现的，并且只可以从一端传到另一端，保证不存在一个点上有多个「风场」。

你每移动一次都会消耗对应边的体力值，收集到达节点的「风种子」，每个点上的「风种子」只能收集一次，当你持有的「风种子」值大于 $k$ 时就可以使用「风场」从一端到达另一端，期间不消耗体力，持有「风种子」减少 $k$ 。

你需要找到消耗体力值最小的路线，并输出消耗体力值。

输入格式

第一行四个整数，分别为 $n、$$m、$ $k$ 和苹果所在节点编号。

接下来一行 $n$ 个整数，代表 $p_{i}$ 。

接下来 $n-1$ 行，每一行分别为一条边的起点、终点和 $e_{i}$ 。

接下来 $m$ 行，表示「风场」的起点和终点。

输出格式

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

样例 #1

样例输入 #1

9 1 20 9
0 15 15 2 7 6 5 10 11
1 2 3
2 3 6
1 4 2
4 5 2
4 6 10
4 7 3
6 8 5
6 9 2
3 6

样例输出 #1

11

样例 #2

样例输入 #2

7 1 10 6
0 1 1 1 1 1 10
1 2 2
2 7 1
2 3 2
1 4 5
4 5 4
5 6 1
3 5

样例输出 #2

7

提示

对于$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$ 。