Problem Description

Inside the cave, there are some crystals, each with an energy value \(a_i\). The energy values vary but are never the same. These mysterious crystals are inhabited by the souls of evil forces. Your task is to destroy these crystals while minimizing the evil energy they release.

You can choose two undestroyed crystals \(i, j\) and destroy them, releasing \(\min(a_i, a_j) \times k\) evil energy, where \(k\) represents the \(k\)-th destruction.

However, there are some unordered pairs of crystals \((x, y)\) that, if destroyed together, will cause a powerful resonance leading to the cave's collapse and your demise!

With this note, A arrives at the end of the cave and indeed finds \(n\) crystals (\(n\) is even). As the note stated, each crystal has an energy value \(a_i\).

After observing these crystals, A discovers a pattern: Each crystal \(i\) will resonate with at most one crystal among those with higher energy values, denoted by its index \(x_i\).

Now that A knows \(a_i\) and \(x_i\), can you help him find the minimum sum of evil energy released by destroying these crystals? If it's impossible to destroy all the crystals, output \(\texttt{-1}\). Otherwise, output the minimum sum followed by the destruction plan.

If there are multiple valid plans, output any one of them.

• Note that the indices of the crystals do not change after destruction.

Simplified Problem Statement:

Given two sequences \(a\) and \(x\) of length \(n\) (\(2|n\)), where \(a_i\) are distinct and if \(x_i \neq -1\), then \(a_{x_i} > a_i\).

You need to perform \(\frac{n}{2}\) deletion operations: choose two undeleted numbers \(a_i, a_j\) such that \(x_i \neq j\) and \(x_j \neq i\), and delete them from sequence \(a\) with a cost of \(\min(a_i, a_j) \times k\) (the indices of the remaining elements do not change), where \(k\) is the \(k\)-th deletion.

Find the minimum cost to delete all numbers and the plan. If it's impossible, output \(\texttt{-1}\). If there are multiple plans, output any one of them.

Input Format

The first line contains an integer \(n\), ensuring \(n\) is even.

The second line contains \(n\) integers \(a_1, a_2, \cdots, a_n\), ensuring \(a_i\) are distinct.

The next line contains \(n\) integers \(x_i\), where \(x_i = -1\) means the \(i\)-th crystal does not resonate with any crystal with higher energy; otherwise, \(a_{x_i} > a_i\).

The input is large, it is recommended to use scanf.

Output Format

If the problem has no solution, output one line \(\texttt{-1}\).

Otherwise, first output one line containing an integer, the minimum sum of evil energy released.

Next, output \(\frac{n}{2}\) lines, each containing two integers separated by a space, representing the pairs of destroyed crystals.

The output is large, it is recommended to use printf.

Sample Input and Output

Input Sample #1

4
1 4 2 3
3 -1 -1 2

Output Sample #1

4
3 2
1 4

Input Sample #2

4
5 7 1 3
-1 -1 1 1

Output Sample #2

7
1 2
3 4

Input Sample #3

4
1 9 4 5
4 -1 4 2

Output Sample #3

-1

Notes/Hints

Sample 3 Explanation:

It's impossible to destroy all the crystals because crystal 4 cannot be destroyed.

Data Range and Constraints:

This problem uses batched testing.

• 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 sorted in ascending order, i.e., \(a_i < a_{i+1}\) (\(1 \leq i < n\));
• Subtask 6 (24 points): No additional constraints.
• Subtask 7 (1 point): Hack data.

For \(100\%\) of the data, \(2 \leq n \leq 5 \times 10^5\), \(1 \leq a_i \leq 10^9\).

Ensure \(n\) is even and \(a_i\) are distinct.

The answer is guaranteed to be less than \(2^{63} - 1\).

Help/Hints:

Please optimize IO operations.

Special Judge:

This problem uses a special judge.

Please read the output format carefully. Incorrect output format may lead to UKE.

If the first line of your output differs from the answer, you will receive \(0\%\) of the points for that test case.

If there is no solution and the first line matches, you will receive \(100\%\) of the points for that test case.

If there is a solution and the first line matches but the plan is incorrect, you will receive \(60\%\) of the points for that test case.

If there is a solution and both the first line and the plan are correct, you will receive \(100\%\) of the points for that test case.

Additional checker and testlib.h are provided.

Baidu Netdisk link: link, extraction code: b7eg.

见题面 Input 部分

见题面 Output 部分