题目背景

HD 矿业公司在一片林区勘探到了连成片的矿脉，可以修建 $n$ 座钻井台。

题目描述

HD 公司在这 $n$ 座钻井台之间修了 $n-1$ 条便道，每条便道连接两座钻井台，中途不经过其他钻井台，并且这些便道把所有钻井台连成了一片。

修建钻井台要用一台大型设备，转运非常麻烦。HD 公司准备在某一座钻井台的位置建一个直升机坪：先把设备空运过来，之后沿便道转运这台设备去修建各座钻井台，全部完工后再把设备从机坪运走。

为了省钱，公司要求设备在便道上运输的总路程最短。

建井与维护都要耗费人力：第 $i$ 座钻井台需要 $B_i$ 个人参与修建；而一旦建成，就需要 $S_i$ 个人一直驻守维护。一个参与修建的人可以直接留下来维护这座钻井台，也可以转去修建下一座；但已经驻守维护的人不能再参加后续的修建。

HD 公司想知道：设备运输的总路程最短是多少？在总路程最短的前提下，至少需要投入多少人力才能完成所有钻井台的修建与维护。

输入格式

输入的第一行包含一个整数 $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
10 20
15 15
1 8

16 30

提示

【样例解释 2】

有两种方案达到最优。

方案一：在钻井台 $2$ 建机坪，先修建钻井台 $2$，再把设备运到钻井台 $1$ 修建，最后把设备运回钻井台 $2$。

方案二：在钻井台 $1$ 建机坪，先把设备运到钻井台 $2$ 修建钻井台 $2$，再运回钻井台 $1$ 修建钻井台 $1$。

【数据范围】

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

另外 $20\%$ 的数据：每座钻井台最多和两座钻井台之间有便道直接相连；

另外 $10\%$ 的数据：有 $n-1$ 座钻井台只有一条便道与其他钻井台相连；

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