题目描述

曾经发明了零件组装机的发明家 SHTSC 又公开了他的新发明：聚变反应炉——一种可以产生大量清洁能量的神秘装置。

众所周知，利用核聚变产生的能量有两个难点：一是控制核聚变反应的反应强度，二是使用较少的能量激发聚变反应。而 SHTSC 已经完美解决了第一个问题。一个聚变反应炉由若干个相连的聚变块组成，为了能够使得聚变反应可控，SHTSC 保证任意两个聚能块都可以通过相互之间的链接到达，并且没有一个聚能块可以不重复经过一个链接回到它自己。

但是第二个问题 SHTSC 还没有完全解决。在他设计的聚变反应炉当中，每个聚变块都需要一定的初始能量 $d_i$ 来进行激发，不过 SHTSC 不需要手动激发所有聚变块，这是因为一旦一个聚变块被激发，则会向与其直接相连的所有还未被激发的聚变块传送 $c_i$ 个单位的能量。这样后被触发的聚变块可以以更低的初始能量来激发，甚至可能不需要额外的外界能量就可自行激发，从而降低了总激发能量的消耗。现在给出了一个聚变反应炉，求至少要多少能量才能激发所有聚变块。

输入格式

第一行一个整数 $n$，表示共有 $n$ 个聚能块，由 $1$ 至 $n$ 编号。

第二行 $n$ 个整数，依次表示 $d_i$。

第三行 $n$ 个整数，依次表示 $c_i$。

以下 $n - 1$ 行每行两个整数 $u, v$，表示编号为 $u$ 和 $v$ 的聚能块是相连的。

输出格式

一行一个整数，表示至少需要多少个单位的能量才能激发所有聚变块。

5
1 1 1 1 1
1 1 1 1 1
1 2
2 3
3 4
4 5

1

提示

对于所有数据，保证 $1 \le d_i, \sum d_i \le {10}^9$。