「SWTR-6」Snow Mountain

**题目背景与解题无关。** **题目描述最下方有简化版题意。** 天空中飘着雪，放眼望去白茫茫一片。小 A 拿着地图，四处探寻着。 突然，只见前方有一个洞穴。出于好奇心，小 A 走了进去。 洞穴里黑漆漆一片，一眼望不到尽头。道路的两旁尽是白骨，显然，这是曾经来这里探险的人们的残骸。小 A 打了一个冷颤。 这时，小 A 留意到了地上的一张纸片。打开来一看，上面竟写着： $$\texttt{Please contact [email protected]!}$$

> 洞穴里有一些水晶，每个水晶有一个能量值 $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](https://pan.baidu.com/s/1Tk-8-UiLzCpOuPVuoCcbbQ)，提取码：b7eg。