Alice 想要在公园里找到她丢失的猫。

公园是一个由 $n$ 个顶点组成的有根树。顶点编号从 $1$ 到 $n$，根节点为 $1$。

Alice 现在位于顶点 $1$。她知道猫已经从顶点 $1$ 跑到了树的某个叶子节点，且没有经过重复的顶点。叶子节点是指没有子节点的顶点。

每个顶点上都有一个监视器。顶点 $i$ 上的监视器可以观察到猫是否经过了顶点 $i$，以及猫接下来去了哪个顶点（如果顶点 $i$ 不是叶子节点）。Alice 查看第 $i$ 个监视器的数据需要 $a_i$ 秒。

Alice 也可以亲自搜索一些叶子节点。搜索 $i$ 个叶子节点需要 $t_i$ 秒。注意这里的 $i$ 是指顶点的数量，而不是顶点的编号。

请帮助 Alice 确定应该检查哪些监视器以及应该搜索哪些叶子节点，以便能够唯一确定猫的位置，并使总耗时最小。注意，需要检查的监视器和需要搜索的叶子节点应在开始时决定，之后不能更改。

求最小时间。

输入格式

每个测试包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。接下来是 $T$ 个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示树的大小。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。 第三行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 10^9, t_i \le t_{i+1}$)。 接下来 $n-1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \neq y$)，表示连接顶点 $x$ 和 $y$ 的边。保证这些边构成一棵树。

输出格式

对于每个测试用例，输出一行一个整数，表示确定猫的位置所需的最短时间。

样例

输入 1

2
8
4 2 5 2 4 2 3 2
5 5 6 7 8 9 10 13
1 2
2 3
1 4
1 5
4 6
3 7
5 8
8
4 2 3 3 2 4 4 3
4 6 8 8 9 9 14 17
1 2
2 3
3 4
3 5
4 6
3 7
3 8

输出 1

4
3