题目背景

mc 正在挑战弹弹乐。

题目描述

弹弹乐由 $n$ 个弹力菇组成，每个弹力菇有 $a,b$ 两个属性。

对于弹力菇 $i$ 会向弹力菇 $j$ 连一条边权为 $\max(a_i,a_j)+\max(b_i,b_j)$ 的双向弹力通道。现在 mc 想知道弹力菇组成的图的最小生成树，以便他打破记录。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

第三行 $n$ 个整数，第 $i$ 个数表示 $b_i$。

输出格式

第一行输出这个最小生成树的边权和。

接下来 $n-1$ 行，每行输出两个整数表示一条树边。你可以输出任意一种合法方案。

3
1 2 1
3 2 3

9
1 2
1 3

提示

数据范围

「本题采用捆绑测试」

$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n} & \textbf{特殊性质} & \textbf{分值}\cr\hline 1 & n\le 500 & \text{无} & 20 \cr\hline 2 & n\le 5\times 10^4 & \text{无} & 20\cr\hline 3 & \text{无特殊限制} & \text{数据随机} & 20\cr\hline 4 & \text{无特殊限制} & \text{无} & 40 \cr\hline \end{array}$$

• 对于 $100\%$ 的数据，满足：$1\le n\le 10^6$，$1\le a_i,b_i\le 10^9$。