P6787 "SWTR-6" Snow Mountain

**The background is unrelated to solving the problem.** **A simplified statement is provided at the bottom of the Description.** Snow is drifting in the sky, and everything looks white as far as the eye can see. Little A is holding a map and exploring around. Suddenly, there is a cave ahead. Out of curiosity, Little A walks in. The cave is pitch black, and it seems to stretch endlessly. On both sides of the road are piles of bones—clearly the remains of people who once explored here. Little A shivers. At this moment, Little A notices a piece of paper on the ground. He opens it and sees that it says: $$\texttt{Please contact [email protected]!}$$

> There are some crystals in the cave. Each crystal has an energy value $a_i$. **The energy values can be large or small, but they will not be the same.** These mysterious crystals are attached with souls of evil forces. Your task now is to destroy these crystals, and make the total evil energy they release as small as possible. > > You may choose two undestroyed crystals $i,j$, destroy them, and release $\min(a_i,a_j)\times k$ evil energy, where $k$ indicates that this is the $k$-th destruction. > > However, there are some **unordered** crystal pairs $(x,y)$. If you destroy them together, a strong resonance will occur and cause the cave to collapse, burying you inside! With this piece of paper, Little A arrives at the end of the cave, and indeed finds $n$ crystals ($n$ is even). As the paper says, each crystal has an energy value $a_i$. After observing these crystals, Little A discovers a rule: for each crystal $i$, among **all crystals whose energy values are greater than it**, it will resonate with **at most one** of them; denote its index as $x_i$. Now Little A knows $a_i$ and $x_i$. Can you help him find the minimum possible total evil energy released by destroying all crystals? If it is impossible to destroy them all, output $\texttt{-1}$. Otherwise, first output the minimum value, then output a destruction plan. If there are multiple valid plans, output any one. - Note that after destruction, the crystal indices do not change. --- Simplified statement: You are given two sequences $a,x$ of length $n\ (2|n)$, where all $a_i$ are distinct, and if $x_i \neq -1$, then $a_{x_i}>a_i$. Now you need to perform $\frac{n}{2}$ delete operations. In each operation, choose two undeleted numbers $a_i,a_j$ such that $x_i\neq j$ and $x_j\neq i$, and delete these two numbers from sequence $a$ with cost $\min(a_i,a_j)\times k$ (after deletion, the indices of the remaining elements do not change), where $k$ indicates that this is the $k$-th deletion. Find the minimum total cost and a plan to delete all numbers. If there is no solution, output $\texttt{-1}$. If there are multiple solutions, output any one.

The first line contains an integer $n$, and it is guaranteed that $n$ is even. The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, and it is guaranteed that all $a_i$ are distinct. The next line contains $n$ integers $x_i$. If $x_i=-1$, it means the $i$-th crystal does not resonate with any crystal whose energy value is greater than it; otherwise it is guaranteed that $a_{x_i}>a_i$. **The input size is large; using `scanf` is recommended.**

If there is no solution, output one line $\texttt{-1}$. Otherwise, first output one line with an integer, meaning the minimum total evil energy released. Then output $\dfrac{n}{2}$ lines, each containing two integers separated by a space, representing the pair of crystals destroyed in that operation. **The output size is large; using `printf` is recommended.**

**"Sample 3 Explanation"** It is impossible to destroy all crystals, because crystal $4$ cannot be destroyed. **"Constraints and Notes"** **This problem uses bundled testdata.** - 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$ is in increasing order, i.e. $a_i