M. S. I. S.

양의 정수로 이루어진 $2 \times n$ 행렬 $M$이 주어진다. $M$의 각 행에는 같은 수가 두 번 나오지 않는다. $i$번째 행 $r_i$ ($i = 1, 2$)에서 증가하는 부분 수열의 합이 최대인 값을 $s_i$라 하자. 예를 들어 아래 행렬에서 $s_1$은 $1 + 2 + 3 + 4 + 5 + 6$이고, $s_2$는 $2 + 3 + 5$이다.

$\begin{bmatrix} \color{red}{1} & \color{red}{2} & \color{red}{3} & \color{red}{4} & \color{red}{5} & \color{red}{6}\\ 6 & \color{red}{2} & \color{red}{3} & \color{red}{5} & 4 & 1 \end{bmatrix}$

$s_1 + s_2$를 MSIS(maximum sum of increasing subsequences)라고 부른다. $M$의 열을 재배열하면 MSIS가 달라질 수 있다. 아래 행렬은 열 $[c_1, c_2, c_3, c_4, c_5, c_6]$을 $[c_2, c_3, c_4, c_5, c_6, c_1]$로 재배열한 것이고, 이때 MSIS는 36이 된다.

$\begin{bmatrix} \color{red}{2} & \color{red}{3} & \color{red}{4} & \color{red}{5} & \color{red}{6} & 1\\ \color{red}{2} & \color{red}{3} & \color{red}{5} & 4 & 1 & \color{red}{6} \end{bmatrix}$

주어진 $M$에 대해, 열을 모든 순열로 재배열했을 때 얻을 수 있는 MSIS의 최댓값을 구하라.

첫 줄에 $M$의 열 개수를 나타내는 정수 $n$ ($1 \le n \le 10000$)이 주어진다. 다음 두 줄에는 각각 $M$의 1행과 2행을 이루는 정수 $n$개가 주어진다. 모든 정수는 1 이상 50000 이하이며, 각 행에는 같은 수가 두 번 나오지 않는다.

$M$의 열을 모든 순열로 재배열했을 때 얻을 수 있는 MSIS의 최댓값을 한 줄에 출력한다.