在进入一场信息学奥林匹克竞赛之前，有 $n$ 名参赛者排队等待入场，编号从 $1$ 到 $n$。已知每分钟会有一名参赛者按编号顺序被邀请进入赛场。第一分钟第一名参赛者进入，第二分钟第二名参赛者进入，以此类推。因此，第 $i$ 名参赛者会在入场流程开始后的 $i$ 分钟进入赛场。

每位参赛者在赛前都有一定的焦虑值。每位参赛者的焦虑值由一个整数（可能是负数）给出。在入场流程开始前，第 $i$ 名参赛者的焦虑值为 $a_i$。每过一分钟，该参赛者的焦虑值会改变 $b_i$。因此，在入场流程开始 $x$ 分钟后，第 $i$ 名参赛者的焦虑值等于 $a_i + x \cdot b_i$。

Alexander 是一位经验丰富的心理学家，他决定安抚等待入场的参赛者。为此，Alexander 会与参赛者交谈并安抚他们。他与每位参赛者交谈的次数不超过一次。与 Alexander 交谈后，参赛者的焦虑值变为 $0$，且之后不再改变。Alexander 与第 $i$ 名参赛者工作的有效性被定义为与 Alexander 交谈时刻该参赛者的焦虑值。因此，如果 Alexander 在入场流程开始 $t_i$ 分钟后与第 $i$ 名参赛者交谈，则有效性等于 $a_i + t_i \cdot b_i$。注意，如果参赛者的焦虑值为负，则有效性也为负。

Alexander 将按编号顺序与参赛者工作。然而，Alexander 不必与所有参赛者交谈，这意味着他可能不会与队列末尾的参赛者交流。注意，Alexander 与每位参赛者交谈不超过一次，且必须在参赛者进入赛场之前进行。同时，Alexander 每分钟可以与多名参赛者同时交流。更正式地说，Alexander 的工作流程描述如下：

• Alexander 总共会与队列中的前 $k$ 名参赛者交谈，其中 $k$ 由他选择。
• 对于前 $k$ 名参赛者中的每一位，我们确定一个非负整数 $t_i$ —— 与 Alexander 交谈的时间。注意 $t_i$ 可以等于 $0$，这意味着 Alexander 在第一名参赛者被允许进入赛场之前就与第 $i$ 名参赛者交谈了。
• 对于每个 $1 \le i \le k$，满足 $t_i < i$，因为 Alexander 必须在参赛者进入赛场前与他们交谈。
• 对于每个 $1 \le i \le k - 1$，满足 $t_i \le t_{i+1}$，因为 Alexander 按编号顺序与参赛者交谈。
• Alexander 与参赛者交流的总有效性由以下公式描述： $$\sum_{i=1}^{k} (a_i + t_i \cdot b_i)$$

Alexander 有一个预先确定的工作计划。工作计划由 $n$ 个整数 $p_1, p_2, \dots, p_n$ 给出。对于每个 $i$，如果 $p_i \neq -1$，则在第一批 $i$ 名参赛者被允许进入赛场时（即入场流程开始 $i$ 分钟后），Alexander 必须已经与前 $p_i$ 名参赛者交谈过，且没有与其他人交谈。在这种情况下，保证 $p_i \ge i$。如果 $p_i = -1$，则意味着在入场流程开始 $i$ 分钟后，Alexander 必须与之工作的参赛者数量没有限制。

更正式地，如果 $p_i \neq -1$，则： $p_i \ge i$； $t_{p_i} < i$； * 对于任何满足 $p_i < j \le k$ 的 $j$，满足 $t_j \ge i$。

帮助 Alexander 确定在满足所有约束条件的情况下，他工作的最大可能总有效性。保证答案总是存在的。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示等待入场的参赛者人数。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($-10^9 \le a_i \le 10^9, -10^6 \le b_i \le 10^6$)，表示第 $i$ 名参赛者的焦虑参数。

最后一行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($i \le p_i \le n$ 或 $p_i = -1$)，表示 Alexander 的工作计划描述。

保证对于任何 $1 \le i < j \le n$，若 $p_i \neq -1$ 且 $p_j \neq -1$，则 $p_i \le p_j$。

输出格式

输出一个整数，表示 Alexander 工作的最大可能总有效性。

样例

输入格式 1

4
3 -6
4 -10
-7 -3
-3 6
3 3 -1 -1

输出格式 1

15

说明

在第一个测试样例中，最优选择是 $k = 4$ 且 $t = \{0, 0, 0, 3\}$。此时总有效性为： $(3 + 0 \cdot (-6)) + (4 + 0 \cdot (-3)) + (-7 + 0 \cdot (-3)) + (-3 + 3 \cdot 6) = 15$

输入格式 2

4
-6 -1
-5 14
0 10
-30 2
2 3 -1 -1

输出格式 2

-1

说明

在第二个测试样例中，最优选择是 $k = 3$ 且 $t = \{0, 0, 1\}$。此时总有效性为： $(-6 + 0 \cdot (-1)) + (-5 + 0 \cdot 14) + (0 + 1 \cdot 10) = -1$

输入格式 3

4
-6 -1
-5 14
0 10
-30 2
-1 -1 -1 -1

输出格式 3

23

说明

在第三个测试样例中，最优选择是 $k = 3$ 且 $t = \{0, 1, 2\}$。此时总有效性为： $(-6 + 0 \cdot (-1)) + (-5 + 1 \cdot 14) + (0 + 2 \cdot 10) = 23$

评分

本题包含十四个测试组。仅当通过某组的所有测试点且通过了部分前置测试组时，才能获得该组的分数。注意，对于某些组，通过样例测试不是必要条件。离线评测意味着该组的测试结果仅在比赛结束后可见。每组的最终得分为所有提交中该组测试所获得的最高分。