P14092 [ICPC 2023 Seoul R] M. S. I. S.

给定一个 $2\times n$ 的正整数矩阵 $M$，且 $M$ 的每一行都不包含重复的数字。对于 $M$ 的第 $i$ 行 $r_i$，$i=1,2$，我们寻找 $r_i$ 中递增子序列的最大和 $s_i$。例如，下图是一个矩阵 $M$，此时 $s_1=1+2+3+4+5+6$，$s_2=2+3+5$。我们称 $s_1+s_2$ 为 *最大递增子序列和*，记为 *MSIS*。  对于 $M$ 的列进行任意排列后，MSIS 可能会改变。例如，将上图中的矩阵 $M=[c_1,c_2,c_3,c_4,c_5,c_6]$ 按列重排列为 $M=[c_2,c_3,c_4,c_5,c_6,c_1]$，如下图所示，新的 MSIS 变为 $36$。  现给定一个 $2\times n$ 的矩阵 $M$，请编写程序输出经过所有可能的列排列后可以得到的最大的 MSIS。

你的程序需要从标准输入读取数据。输入的第一行为一个整数 $n$，表示矩阵 $M$ 的列数，$1 \leq n \leq 10,000$。接下来的两行中，每行包含 $n$ 个正整数，分别表示矩阵 $M$ 的第 $i$ 行的元素（$i=1,2$）。输入的每个整数在 $1$ 到 $50,000$ 之间，并且每一行没有重复数字。

你的程序需要向标准输出打印一行，输出经过所有可能的列排列后可以得到的最大 MSIS。

由 ChatGPT 5 翻译