Background

mc is challenging the bouncing game.

Problem Description

The bouncing game consists of $n$ elastic mushrooms. Each elastic mushroom has two attributes, $a$ and $b$.

For elastic mushroom $i$ and elastic mushroom $j$, an undirected elastic channel is added between them with edge weight $\max(a_i,a_j)+\max(b_i,b_j)$. Now mc wants to know the minimum spanning tree of the graph formed by the elastic mushrooms, so that he can break the record.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers. The $i$-th number represents $a_i$.

The third line contains $n$ integers. The $i$-th number represents $b_i$.

Output Format

Output the sum of edge weights of this minimum spanning tree in the first line.

Then output $n-1$ lines. Each line outputs two integers representing an edge of the tree. You may output any valid solution.

3
1 2 1
3 2 3

9
1 2
1 3

Hint

Constraints

"This problem uses bundled testdata."

$$\def\arraystretch{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n} & \textbf{Special Properties} & \textbf{Score}\cr\hline 1 & n\le 500 & \text{None} & 20 \cr\hline 2 & n\le 5\times 10^4 & \text{None} & 20\cr\hline 3 & \text{No special limits} & \text{Random testdata} & 20\cr\hline 4 & \text{No special limits} & \text{None} & 40 \cr\hline \end{array}$$

• For $100\%$ of the testdata, it holds that: $1\le n\le 10^6$, $1\le a_i,b_i\le 10^9$.

Translated by ChatGPT 5