Description

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

。众所周知，利用核聚变产生的能量有两个难点：一是控制核聚变反应的反应强度，二是使用较少的能量激发聚变

反应。而SHTSC已经完美解决了第一个问题。一个聚变反应炉由若干个相连的聚变块组成，为了能够使得聚变反应

可控，SHTSC保证任意两个聚能块都可以通过相互之间的链接到达，并且没有一个聚能块可以不重复经过一个链接

回到它自己。但是第二个问题SHTSC还没有完全解决。在他设计的聚变反应炉当中，每个聚变块都需要一定的初始

能量di来进行激发，不过SHTSC不需要手动激发所有聚变块，这是因为一旦一个聚变块被激发，则会向与其直接相

连的所有还未被激发的聚变块传送ci个单位的能量。这样后被触发的聚变块可以以更低的初始能量来激发，甚至可

能不需要额外的外界能量就可自行激发，从而降低了总激发能量的消耗。现在给出了一个聚变反应炉，求至少要多

少能量才能激发所有聚变块。

Format

Input

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

第二行n个整数，表示di。

第三行n个整数，表示ci。

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

输入保证符合题目描述。

Type A ：ci <= 1,有 n<=100000。

Type B ：ci <= 5,有n<=2000。

对于所有的数据，1<=di, Sum(di)<=10^9。输入保证符合题目描述。

Output

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

Samples

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

1
//样例1：只需要触发任意一个聚变块即可激活整个聚变反应装置。