Background

Description

要在省理论职专签署一份文件，你可能需要辗转多个部门。

当前这份文件共需要经过 $n$ 个部门的签字同意，共有 $n-1$ 条可行的道路，每条道路连接两个部门，路径中间不会路过任何部门，而且这些道路将所有部门连通。

同为想象学竞赛的同学，为了培养凝聚力，你们当然应一起行动，即同一时刻所有人只能在一个部门。你们可以选择从任何一个部门开始签字，全部签字完成后，所有人可以停留下来，让最后一个部门的主任自行沿道路将文件送回起点。

为了减少重要文件暴露在校园中的时间，防止被宇宙射线摧毁，要求文件所经过的总路程是最短的。

由于主任们看起来较不和蔼，所以可能需要很多人一起才有勇气敲响一个部门的门。同时，由于主任们喜欢邀请大家聊天，有一些人会被留下而无法继续走完后面的路程。

我们认为敲开了一个部门的门即可获得该部门主任的签字。

对于一个部门 $i$，有 $P_i$ 和 $Q_i$，表示需要 $P_i$ 个人同时敲门，并且有 $Q_i$ 个人会被留下。

当然，如果一个人参与了敲门，他可以直接留下来进行愉快的谈话，或者参与后面的过程，但是已经被留下的人不能中途逃出。

现在，你想知道，在保证总路径长度最小的情况下，至少需要花费多少同学才能完成这份文件的签字。

Constraints and Subtasks

本题采用捆绑测试。

对于所有的测试数据，保证：

• $1\leq n\leq 10^5$；
• $1\leq P_i, Q_i\leq 5\times 10^5$；
• 对于任意的 $i(1\leq i\leq n-1)$，都有 $1\leq u_i, v_i\leq n$，且构成一颗合法的树。

Subtask	分值	$n\leq$	特殊性质	子任务依赖
$1$	$15$	$10$	无	无
$2$	$15$	$10^5$	A
$3$	$15$		B
$4$	$5$		C
$5$	$50$		无	$1,2,3,4$

特殊性质 A：保证树是一个菊花图。

特殊性质 B：保证树是一条链。

特殊性质 C：保证对于任意 $i(1\leq i\leq n)$，都有 $P_i=Q_i$。

---

Input

从标准输入中读入数据。

输入格式如下：

$ \boxed{ \begin{aligned} & n \\ & P_1 {\quad} P_2 {\quad} {\dots} {\quad} P_n \\ & Q_1 {\quad} Q_2 {\quad} {\dots} {\quad} Q_n \\ & u_1 {\quad} v_1 \\ & u_2 {\quad} v_2 \\ & ~ \vdots \\ & u_{n-1} {\quad} v_{n-1} \\ \end{aligned} } $

Output

输出到标准输出中。

输出一行一个整数，表示最少需要的人数。

Sample

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

8

一种可行的方案是，文件按以下路径移动：$1\to 2\to 3\to 2\to 4\to 5\to 4\to 2\to 1$。

出题人不保证不在赛时更改测试数据。