Crystal Destruction

You are given n crystals (where n is an even integer). Each crystal i has a unique energy value \(a_i\). Some crystals are paired with a forbidden resonance partner: for each crystal i, you are given an integer \(x_i\) such that if \(x_i \neq -1\) then \(a_{x_i} > a_i\). If you destroy crystals i and j at the same time and \(x_i = j\) or \(x_j = i\), a deadly resonance is triggered which must be avoided.

You must remove all the crystals by performing exactly \(\frac{n}{2}\) deletion operations. In each operation, you select two as-yet undestroyed crystals \(i\) and \(j\) (with \(i < j\) for convenience) provided that \(x_i \neq j\) and \(x_j \neq i\). Suppose that the current operation is the \(k\)-th deletion (1-indexed); then the cost incurred is

[ \text{cost} = k \times \min(a_i, a_j). ]

After an operation, the indices of the remaining crystals do not change. You are allowed to choose the order in which you perform the deletion operations. In particular, after you decide on the pairing of the crystals, you may reorder the operations arbitrarily. Hence, for a given pairing, the optimal strategy is to perform the deletion operations in such an order that pairs with larger \(\min(a_i,a_j)\) get a lower multiplier \(k\) (i.e. are deleted earlier), thereby minimizing the total cost.

Your task is to find a valid deletion scheme (i.e. a valid partition of the crystals into \(\frac{n}{2}\) pairs, with an order of deletion) that minimizes the total cost. If it is impossible to delete all crystals without triggering resonance, output -1. Otherwise, first output the minimum total cost, followed by \(\frac{n}{2}\) lines each containing two integers representing a pair of crystals (use the original 1-indexed numbering) in the order in which they are deleted. If there are multiple solutions, output any one of them.

Input Format

The input consists of three lines:

• The first line contains an even integer \(n\) (\(2 \mid n\)).
• The second line contains \(n\) space-separated integers, \(a_1, a_2, \dots, a_n\), representing the energy values. All \(a_i\) are distinct.
• The third line contains \(n\) space-separated integers, \(x_1, x_2, \dots, x_n\). If \(x_i = -1\), then crystal i has no forbidden resonance partner; otherwise, \(x_i\) (given in 1-indexed form) denotes the crystal that i resonates with. Note that if \(x_i \neq -1\), then \(a_{x_i} > a_i\).

Output Format

If it is impossible to remove all the crystals without triggering a resonance, output a single line containing -1. Otherwise, output the minimum total cost on the first line. Then, output \(\frac{n}{2}\) lines, each containing two space-separated integers representing the indices of the two crystals to be destroyed in that deletion operation (the order of the operations is the order in which they are performed).

Example

Input:

2
3 5
-1 -1

Output:

3
1 2

Explanation

There is only one possible deletion: destroying crystals 1 and 2 together with cost \(1 \times \min(3, 5)=3\).

inputFormat

The first line contains the even integer \(n\). The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\). The third line contains \(n\) space-separated integers \(x_1, x_2, \dots, x_n\), where each \(x_i = -1\) or a number in the range \([1, n]\) with the property that if \(x_i \neq -1\) then \(a_{x_i} > a_i\).

outputFormat

If no valid deletion scheme exists, output a single line containing -1. Otherwise, on the first line output the minimum total cost. Then output exactly \(\frac{n}{2}\) lines; each line should contain two integers (1-indexed) representing a pair of crystals to be destroyed in that deletion operation. The order of the output lines represents the order in which the deletion operations are performed, and this order should minimize the total cost as specified.

sample

2
3 5
-1 -1

3
1 2

</p>