题目描述

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

每名参赛者在赛前都有一定的焦虑程度，用一个整数表示（可以为负数）。在入场流程开始前，第 $i$ 名参赛者的焦虑程度为 $a_i$。每一分钟，该参赛者的焦虑程度会变化 $b_i$。因此，在入场流程开始 $x$ 分钟后，第 $i$ 名参赛者的焦虑程度将等于 $a_i + x \cdot b_i$。

Alexander 是一位经验丰富的心理学家，他决定安抚正在等待入场的参赛者。为此，Alexander 与参赛者交谈并平复他们的情绪。他最多可以与每名参赛者交谈一次。与 Alexander 交谈后，该参赛者的焦虑程度将变为 $0$，并且之后不再变化。Alexander 对第 $i$ 名参赛者工作的 效果 被认为是他与该参赛者交谈瞬间该参赛者的焦虑程度。因此，如果 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$ 可以等于零，这表示 Alexander 在第一名参赛者被允许进入竞赛大厅之前就与他交谈了。
• 对于每个 $i$ 从 $1$ 到 $k$，均有 $t_i < i$，因为 Alexander 必须在参赛者进入竞赛大厅之前与他们交谈。
• 对于每个 $i$ 从 $1$ 到 $k - 1$，均有 $t_i \le t_{i + 1}$，因为 Alexander 按参赛者的编号顺序与他们交谈。
• Alexander 与参赛者交流的 总效果 将由以下公式给出：

$$\sum_{i = 1}^k \left(a_i + t_i \cdot b_i\right)$$

Alexander 有一份预先确定的工作计划，该计划由一个长度为 $n$ 的序列 $p_1, p_2, \ldots, p_n$ 给出。对于每个 $i$，若 $p_i \neq -1$，那么当第 $1$ 至 $i$ 名参赛者被允许进入竞赛大厅时（即入场流程开始 $i$ 分钟后），Alexander 必须已经恰好与第 $1$ 至 $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, \ldots, p_n$（$i \le p_i \le n$ 或 $p_i = -1$）—— Alexander 工作计划的描述。

保证对于任意一对 $1 \le i < j \le n$，如果 $p_i \ne -1$ 且 $p_j \ne -1$，则有 $p_i \le p_j$。

输出格式

输出一个整数 —— Alexander 工作所能达到的最大 总效果。

可以证明，Alexander 总是能够在遵守所有额外约束以及工作计划的前提下完成他的工作。

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

15

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

-1

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

23

提示

样例解释

在第一个测试样例中，最优选择是 $k=4$ 且 $t = \{0, 0, 0, 3\}$。此时 总效果 为：

$$\left(3 + t_0 \cdot (-6)\right) + \left(4 + t_1 \cdot (-3)\right) + \left(-7 + t_2 \cdot (-3) \right) + \left(-3 + t_4 \cdot 6\right) =$$$$= \left(3 + 0 \cdot (-6)\right) + \left(4 + 0 \cdot (-3)\right) + \left(-7 + 0 \cdot (-3) \right) + \left(-3 + 3 \cdot 6\right) = 15$$

在第二个测试样例中，最优选择是 $k=3$ 且 $t = \{0, 0, 1\}$。此时 总效果 为：

$$\left(-6 + t_0 \cdot (-1)\right) + \left(-5 + t_1 \cdot 14\right) + \left(0 + t_2 \cdot 10\right) = \left(-6 + 0 \cdot (-1)\right) + \left(-5 + 0 \cdot 14\right) + \left(0 + 1 \cdot 10\right) = -1$$

在第三个测试样例中，最优选择是 $k=3$ 且 $t = \{0, 1, 2\}$。此时 总效果 为：

$$\left(-6 + t_0 \cdot (-1)\right) + \left(-5 + t_1 \cdot 14\right) + \left(0 + t_2 \cdot 10\right) = \left(-6 + 0 \cdot (-1)\right) + \left(-5 + 1 \cdot 14\right) + \left(0 + 2 \cdot 10\right) = 23$$

计分

本题的测试数据分为 14 组。每组仅在通过该组内全部测试以及此前某些组的全部测试后，才能获得分数。注意，某些组不要求通过样例测试。离线测试 表示你提交的解答在该组上的测试结果将仅在比赛结束后公布。每组的最终得分等于你所有提交的解答中在该组测试上获得的最高分。

子任务编号	分数	额外限制	<		必过组别	备注
		$n$	$b_i$	$p_i$
$0$		--	--	--	--	题面样例。
$1$	$6$	$n \le 100$		$p_i=-1$
$2$		^		--	$0$ -- $1$	^
$3$	$7$	$n \le 5000$	--	$p_i=-1$	$1$
$4$	$6$	^		--	$0$ -- $3$	^
$5$	$7$	--	$b_i \le 0$	$p_i=-1$	--
$6$	$5$	^		--	$5$	^
$7$		--	$b_i \ge 0$	$p_i=-1$	--
$8$	$5$	^		--	$7$	^
$9$		--	$b_i \le b_{i+1}$	$p_i=-1$	--
$10$	$8$	^		--	$9$	^
$11$	$10$	$n \le 100\,000$	--	$p_i=-1$	--	$b_i > 0$ 的个数不超过 10
$12$	$7$	^		--	$11$	^
$13$	$9$	--		$p_i=-1$	$1$, $3$, $5$, $7$, $9$, $11$	离线测试
$14$	$8$	^		--	$0$ -- $13$	^

翻译由 DeepSeek V4 Pro 完成