题目描述

LQ 公司是世界著名的石油公司，为世界供应优质石油。

最近，LQ 公司又在森林里发现了一大片区域的油田，可以在这个油田中开采 $n$ 个油井。

LQ 公司在这 $n$ 个油井之间修建了 $n-1$ 条道路，每条道路连接两个油井，路径中间不会路过任何油井，而且这些道路将所有油井连通。

建立油井的时候需要使用一台大型设备，运输起来非常麻烦，LQ 公司准备在其中的一个油井位置建立一个空运站，先将设备空运到空运站，之后每次经过他们建立的道路来运输这个大型设备以建立不同的油井，当油井建立完毕后再从空运站将大型设备运走。

为了减少运输的麻烦，公司要求大型设备在道路上运输的总路程是最短的。

在建立油井和采油的过程中需要花费一些人力，第 $i$ 个油井需要花费 $B_i$ 个人，而一旦油井建成，就需要 $S_i$ 个人一直坚守在油井上进行维护。

当然，如果一个人参与了油井的建设，他可以直接留下来维护油井，或者参与下一个油井的建设，但是在维护油井的人不能再参加后续油井的建设了。

现在 LQ 公司想知道，大型设备运输的总路径长度最短是多少？在保证总路径长度最短的情况下，LQ 公司至少需要花费多少人力才能完成所有油井的建立与维护。

输入格式

输入的第一行包含一个整数 $n$，表示油井的数量。油井由 $1$ 到 $n$ 依次标号。

第二行包含 $n$ 个整数，依次表示 $B_1,B_2,\cdots,B_n$，相邻的整数之间用一个空格分隔。

第三行包含 $n$ 个整数，依次表示 $S_1,S_2,\cdots,S_n$，相邻的整数之间用一个空格分隔。

接下来 $n-1$ 行描述油井之间的道路，其中的第 $i$ 行包含两个整数 $a$，$b$，用一个空格分隔，表示一条道路的起点为 $i+1$ 、终点为 $a$，长度为 $b$，道路是双向的，设备可以从任意一端运送到另一端，每条道路都可以经过任意多次。数据保证任意两个油井之间都可以通过道路连接。

输出格式

输出包含两个整数，用一个空格分隔，表示最优情况下大型设备需要运输的总路程，以及在总路程最短的情况下最少需要花费的人力数量。

6
3 10 20 7 15 9
2 6 10 4 8 7
1 9
1 2
2 5
3 4
3 7

54 38

提示

【样例解释】

有两种方案达到最优。

方案一：在油井 $2$ 建立空运站，先建立油井 $2$，再将大型设备运输到油井 $1$ 建立油井 $1$，最后将大型设备运回油井 $2$。

方案二：在油井 $1$ 建立空运站，先将大型设备运输到油井 $2$ 建立油井 $2$，再将大型设备运送到油井 $1$ 建立油井 $1$。

【数据范围】

对于 $20\%$ 的数据：$n$ 不超过 $10$；

另外 $20\%$ 的数据：每个油井最多和两个油井之间有道路直接连接；

另外 $10\%$ 的数据：有 $n-1$ 个油井只有一条道路与其他油井连接；

对于 $100\%$ 的数据：$1\le n\le10^5$，$B$、$S$、$c$ 均为不超过 $10000$ 的正整数。

时限 1 秒, 256M。蓝桥杯 2018 年第九届国赛