P6787 「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`。**

**「样例 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