P8957 "CGOI-3" Witch Bubble Bouncing Game

mc is challenging the bouncing game. 

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.

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 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.

#### 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