题目描述

有一座竖直矿井，共有 N 个矿室，编号为 1..N。

• 1 号矿室直接与地表相连；
• 对于每个 2 <= i <= N，矿室 i 恰好有一条从某个更靠近地表的矿室通向它的竖直通道。

因此，整座矿井构成一棵以 1 为根的有根树。

每条通道都有一个分数，可能为正，也可能为负。

现在每个矿室中有若干名矿工。我们需要为其中一部分矿工（也可以一个都不选）安排采矿路线。对每个被选中的矿工，需要给他分配一条只能向更深处延伸的路径，也就是说：

• 若矿工当前位于某个矿室，只能沿树边走向其子节点；
• 一条路径的得分定义为其经过的所有通道分数之和；
• 整体方案的得分是所有被分配路径的矿工的路径得分之和；
• 若没有任何矿工被分配路径，则总得分视为 0。

此外还有容量限制：对于每个矿室 i，最多只能有 e_i 名矿工把路径终点放在该矿室。

没有被分配路径的矿工会直接离开矿井，不计入任何限制。

请你求出一种合法方案，使总得分最大。

输入格式

第一行一个整数 N，表示矿室数。

第二行包含 N 个整数 s_1, s_2, ..., s_N，其中 s_i 表示矿室 i 初始拥有的矿工数。

第三行包含 N 个整数 e_1, e_2, ..., e_N，其中 e_i 表示最多允许多少名矿工在矿室 i 结束路径。

接下来 N-1 行描述通道。第 i 行（对应矿室 i+1）包含两个整数 p_{i+1}, w_{i+1}，表示存在一条从矿室 p_{i+1} 到矿室 i+1 的竖直通道，其分数为 w_{i+1}。

输出格式

输出一行一个整数，表示最大可能总得分。

样例 #1

输入 #1

5
5 1 0 0 0
100 1 1 2 4
1 6
1 1
2 2
2 -1

输出 #1

32

样例解释

一种最优方案如下：

1. 1 -> 2 -> 4，得分 8
2. 1 -> 2 -> 4，得分 8
3. 1 -> 2，得分 6
4. 1 -> 2 -> 5，得分 5
5. 1 -> 2 -> 5，得分 5

总得分为 8 + 8 + 6 + 5 + 5 = 32。

数据范围

• 2 <= N <= 5 * 10^5
• 0 <= s_i, e_i <= 2000
• 1 <= p_i < i（对所有 2 <= i <= N）
• |w_i| <= 2000

子任务

只有通过某个子任务中的所有测试点，才能获得该子任务的全部分数。