{"problem":{"name":"「CGOI-3」巫泡弹弹乐","description":{"content":"弹弹乐由 $n$ 个弹力菇组成，每个弹力菇有 $a,b$ 两个属性。 对于弹力菇 $i$ 会向弹力菇 $j$ 连一条边权为 $\\max(a_i,a_j)+\\max(b_i,b_j)$ 的双向弹力通道。现在 mc 想知道弹力菇组成的图的最小生成树，以便他打破记录。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8957"},"statements":[{"statement_type":"Markdown","content":"弹弹乐由 $n$ 个弹力菇组成，每个弹力菇有 $a,b$ 两个属性。\n\n对于弹力菇 $i$ 会向弹力菇 $j$ 连一条边权为 $\\max(a_i,a_j)+\\max(b_i,b_j)$ 的双向弹力通道。现在 mc 想知道弹力菇组成的图的最小生成树，以便他打破记录。\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。\n\n第三行 $n$ 个整数，第 $i$ 个数表示 $b_i$。\n\n## Output\n\n第一行输出这个最小生成树的边权和。\n\n接下来 $n-1$ 行，每行输出两个整数表示一条树边。你可以输出任意一种合法方案。\n\n[samples]\n\n## Background\n\nmc 正在挑战弹弹乐。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/yaye0cgu.png)\n\n## Note\n\n#### 数据范围\n\n**「本题采用捆绑测试」**\n\n$$\\def\\arraystretch{1.5}\\begin{array}{|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\bm{n} & \\textbf{特殊性质} & \\textbf{分值}\\cr\\hline\n1 & n\\le 500 & \\text{无} & 20 \\cr\\hline\n2 & n\\le 5\\times 10^4 & \\text{无} & 20\\cr\\hline\n3 & \\text{无特殊限制} & \\text{数据随机} & 20\\cr\\hline\n4 & \\text{无特殊限制} & \\text{无} & 40 \\cr\\hline\n\\end{array}$$\n\n- 对于 $100\\%$ 的数据，满足：$1\\le n\\le 10^6$，$1\\le a_i,b_i\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8957","tags":["洛谷原创","Special Judge","O2优化","构造","Ad-hoc"],"sample_group":[["3\n1 2 1\n3 2 3","9\n1 2\n1 3"]],"created_at":"2026-03-03 11:09:25"}}