题目描述

中秋节快到了，小洛家的月饼铺准备了许多相同规格的月饼礼盒。一天营业结束后，这些月饼礼盒被临时放在了不同的储藏间里。为了方便第二天送出中秋祝福，小洛需要按照整理清单，将它们重新分配到指定的储藏间。

店铺共有 $N$ 间储藏间，储藏间之间有 $N-1$ 条通道。任意两间储藏间之间都可以相互到达，并且路线唯一。第 $i$ 间储藏间目前有 $s_i$ 个月饼礼盒，整理完成后应当恰好有 $t_i$ 个月饼礼盒。

一次搬运时，小洛可以选择一条通道，将若干个月饼礼盒从通道的一端搬到另一端。第 $i$ 条通道连接储藏间 $u_i$ 和 $v_i$。由于不同通道的宽度和转弯空间不同，经过这条通道的一次搬运最多可以携带 $c_i$ 个月饼礼盒，也可以只携带其中的一部分。

一次搬运只能经过一条通道。如果一个月饼礼盒需要连续经过多条通道，那么每经过一条通道，都要分别进行一次搬运。整理过程中，月饼礼盒可以暂时存放在任意储藏间内。

请你计算，至少需要进行多少次搬运，才能使每间储藏间中的月饼礼盒数量都与整理清单一致。

输入格式

第一行输入一个整数 $N$，表示储藏间的数量。

第二行输入 $N$ 个整数 $s_1,s_2,\ldots,s_N$，其中 $s_i$ 表示第 $i$ 间储藏间目前的月饼礼盒数量。

第三行输入 $N$ 个整数 $t_1,t_2,\ldots,t_N$，其中 $t_i$ 表示整理完成后第 $i$ 间储藏间应有的月饼礼盒数量。

接下来输入 $N-1$ 行。第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $c_i$，表示第 $i$ 条通道连接储藏间 $u_i$ 和 $v_i$，经过这条通道的一次搬运最多可以携带 $c_i$ 个月饼礼盒。

输出格式

输出一个整数，表示完成整理所需的最少搬运次数。

样例 #1

样例输入 #1

6
3 8 1 6 0 4
5 2 4 3 5 3
1 2 3
1 3 2
2 4 4
2 5 2
3 6 3

样例输出 #1

8

提示

样例解释

将 $1$ 号储藏间看作所有通道的起点。

$4$ 号储藏间目前有 $6$ 个月饼礼盒，整理后只需要保留 $3$ 个，因此有 $3$ 个月饼礼盒需要经过通道 $(2,4)$ 搬出。这条通道一次最多搬运 $4$ 个月饼礼盒，所以只需搬运 $1$ 次。

$5$ 号储藏间目前没有月饼礼盒，但整理后需要有 $5$ 个。因此，必须经过通道 $(2,5)$ 向其中搬入 $5$ 个月饼礼盒。这条通道一次最多搬运 $2$ 个，所以至少需要搬运 $3$ 次。

将 $2$、$4$、$5$ 号储藏间看作一个整体，这片区域最终会多出 $4$ 个月饼礼盒，它们都需要经过通道 $(1,2)$ 搬出。由于这条通道一次最多搬运 $3$ 个，所以需要搬运 $2$ 次。

同理，$6$ 号储藏间多出的 $1$ 个月饼礼盒需要经过通道 $(3,6)$ 搬出，所需次数为 $1$。而 $3$、$6$ 号储藏间组成的区域一共还缺少 $2$ 个月饼礼盒，需要经过通道 $(1,3)$ 搬入，所需次数也是 $1$。

因此，最少搬运次数为 $1+3+2+1+1=8$。

数据范围

本题共有 $20$ 个测试点。

• 对于测试点 $1,2$，满足 $N\leq 10$；
• 对于测试点 $3\sim 6$，满足每条通道都与 $1$ 号储藏间直接相连；
• 对于测试点 $7\sim 10$，满足通道依次连接 $(1,2),(2,3),\ldots,(N-1,N)$；
• 对于测试点 $11\sim 14$，满足对每个 $2\le i\le N$，第 $i-1$ 条通道连接 $p_i$ 与 $i$，且 $p_i<i$；
• 对于测试点 $1\sim 16$，满足 $N\leq 3000$；

对于所有测试数据，保证 $1\le N\le 2\times 10^5$，$0\le s_i,t_i\le 10^6$，并且对于每条通道都有 $1\le c_i\le 10^9$。

所有通道构成一棵树。输入保证月饼礼盒的当前总数与目标总数相同，即 $\sum_{i=1}^{N}s_i=\sum_{i=1}^{N}t_i$。