题目背景

题目背景与解题无关。

题目描述最下方有简化版题意。

天空中飘着雪，放眼望去白茫茫一片。小 A 拿着地图，四处探寻着。

突然，只见前方有一个洞穴。出于好奇心，小 A 走了进去。

洞穴里黑漆漆一片，一眼望不到尽头。道路的两旁尽是白骨，显然，这是曾经来这里探险的人们的残骸。小 A 打了一个冷颤。

这时，小 A 留意到了地上的一张纸片。打开来一看，上面竟写着：

$$\texttt{Please contact lydsy2012@163.com!}$$

题目描述

洞穴里有一些水晶，每个水晶有一个能量值 $a_i$。能量值有大有小，但不会相同。 这些神秘的水晶上附着邪恶势力的灵魂。现在你的任务是摧毁这些水晶，并让它们释放出的邪恶能量能量尽可能小。

你可以选择两个未被摧毁的水晶 $i,j$，将它们摧毁并释放出 $\min(a_i,a_j)\times k$ 的邪恶能量。其中 $k$ 表示这是第 $k$ 次摧毁。

不过有一些无序水晶对 $(x,y)$，如果你将它们一并摧毁，就会发生强大的共振导致山洞倒塌，使你葬身其中！

带着这张纸片，小 A 来到了山洞的尽头，果然发现了 $n$ 个水晶（$n$ 为偶数）。正如纸片上所说，每个水晶都有一个能量值 $a_i$。

对这些水晶进行一番观察，小 A 发现了一个规律：每个水晶 $i$ 在所有能量值比它大的水晶中，只会和最多一个发生共振，记其编号为 $x_i$。

现在小 A 知道了 $a_i,x_i$，你能帮助他求出摧毁这些水晶释放出邪恶能量之和的最小值吗？无法摧毁输出 $\texttt{-1}$。否则先输出最小值，再输出摧毁方案。

若摧毁方案有多种，输出任意一种即可。

• 需要注意的是，摧毁后水晶编号不会发生改变。

---

简化版题意：

给定两个长为 $n\ (2|n)$ 的序列 $a,x$，满足 $a_i$ 互不相同且如果 $x_i \neq -1$，那么 $a_{x_i}>a_i$。

现在需要进行 $\frac{n}{2}$ 次删除操作：选择两个未被删除的数 $a_i,a_j$ 满足 $x_i\neq j$ 且 $x_j\neq i$，并用 $\min(a_i,a_j)\times k$ 的代价将这两个数从序列 $a$ 中删去（删除后剩余元素下标不变），其中 $k$ 表示这是第 $k$ 次删除。

求删除所有数的最小代价与方案。无解输出 $\texttt{-1}$。若方案有多种，输出任意一种即可。

输入格式

第一行一个整数 $n$，保证 $n$ 是偶数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，保证 $a_i$ 互不相同。

接下来一行 $n$ 个整数 $x_i$，如果 $x_i=-1$ 则表示第 $i$ 个水晶不与能量值比它大的水晶发生共振；否则保证 $a_{x_i}>a_i$。

题目输入量较大，建议使用 scanf。

输出格式

若题目无解，输出一行 $\texttt{-1}$。

否则首先输出一行一个整数，表示释放出邪恶能量之和的最小值。

接下来 $\dfrac{n}{2}$ 行每行两个由空格隔开的整数，表示被摧毁的水晶对。

题目输出量较大，建议使用 printf。

4
1 4 2 3
3 -1 -1 2

4
3 2
1 4

4
5 7 1 3
-1 -1 1 1

7
1 2
3 4

4
1 9 4 5
4 -1 4 2

-1

提示

「样例 3 说明」

无法摧毁所有水晶，因为水晶 $4$ 无法被摧毁。

「数据范围与约定」

本题采用捆绑测试。

• Subtask 1（5 points）：$n=2$；
• Subtask 2（20 points）：$n \leq 10$；
• Subtask 3（15 points）：$x_i=-1$；
• Subtask 4（20 points）：$n\leq 3\times 10^3$；
• Subtask 5（15 points）：$a_i$ 升序排列，即 $a_i<a_{i+1}\ (1\leq i<n)$；
• Subtask 6（24 points）：无特殊限制。
• Subtask 7（1 point）：hack 数据。

对于 $100\%$ 的数据，$2 \leq n \leq 5 \times 10^5$，$1 \leq a_i \leq 10^9$。
保证 $n$ 为偶数且 $a_i$ 互不相同。
保证答案不超过 $2^{63}-1$。

「帮助/提示」

请注意 IO 优化。

「Special Judge」

本题使用 SPJ。

请认真阅读输出格式。 输出格式有误可能导致 UKE。

若你的输出的第一行与答案的第一行不同，你将获得本测试点的 $0\%$ 分数。

若无解且第一行相同，你将获得本测试点的 $100\%$ 分数。

若有解且第一行相同，但方案有误，你将获得本测试点的 $60\%$ 分数。

若有解且第一行相同，方案正确，你将获得本测试点的 $100\%$ 分数。

另附 checker 与 testlib.h。

百度网盘链接：link，提取码：b7eg。