Description

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.

Input Format

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.

Output Format

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.

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

Hint

"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<a_{i+1}\ (1\leq i<n)$.
• Subtask 6 (24 points): no special restrictions.
• Subtask 7 (1 point): hack testdata.

For $100\%$ of the testdata, $2 \leq n \leq 5 \times 10^5$, $1 \leq a_i \leq 10^9$.
It is guaranteed that $n$ is even and all $a_i$ are distinct.
It is guaranteed that the answer does not exceed $2^{63}-1$.

"Help / Tips"

Please pay attention to I/O optimization.

"Special Judge"

This problem uses SPJ.

Please read the output format carefully. Incorrect output format may cause UKE.

If the first line of your output is different from the first line of the official answer, you will get $0\%$ for this test point.

If there is no solution and the first line is the same, you will get $100\%$ for this test point.

If there is a solution and the first line is the same, but the plan is incorrect, you will get $60\%$ for this test point.

If there is a solution and the first line is the same, and the plan is correct, you will get $100\%$ for this test point.

A checker and testlib.h are also provided.

Baidu Netdisk link: link, extraction code: b7eg.

Translated by ChatGPT 5