Comet OJ输入的第一行是一个正整数 $n(5 \le n \le 100000)$，表示城镇数目。城镇以 $1$ 到 $n$ 的数命名。小 T 的家乡命名为 $1$。
第二行和第三行都包含以空格隔开的 $n-1$ 个整数，第二行的第 $i$ 个数表示在城镇 $i+1$ 停留的净收益。
第三行的第 $i$ 个数表示城镇 $i+1$ 规定的最大停留次数。所有的最大停留次数都不小于 $2$。
接下来的 $n-1$ 行每行两个 $1$ 到 $n$ 的正整数 $x,y$，之间以一个空格隔开，表示 $x,y$ 之间有一条不经过其它城镇的双向道路。
输入数据保证所有城镇是连通的。