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

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

题目描述

We are given a 2×n2\times n matrix MM of positive integers, and each row of MM does not contain duplicate numbers. For ii-th row rir_i of MM, i=1,2i=1,2, we find the maximum sum sis_i of increasing subsequence contained in rir_i. For example, if MM is given as the figure below, s1s_1 is 1+2+3+4+5+61 + 2 + 3 + 4 + 5 + 6 and s2s_2 is 2+3+52 + 3 + 5. We call s1+s2s_1+s_2 the maximum sum of increasing subsequences, MSIS.

Once we permute the columns of MM, MSIS can change. For example, if we permute the columns of the above matrix M=[c1,c2,c3,c4,c5,c6]M=[c_1,c_2,c_3,c_4,c_5,c_6] to M=[c2,c3,c4,c5,c6,c1]M=[c_2,c_3,c_4,c_5,c_6,c_1] as the figure below, MSIS becomes 3636.

Given a 2×n2\times n matrix MM, write a program to output the maximum of MSIS among all possible permutations of the columns of MM.

输入格式

Your program is to read from standard input. The input starts with a line containing an integer, nn (1n10,0001 \le n\le 10,000), where nn is the number of columns of the input matrix MM. In the following two lines, the ii-th line contains nn positive integers of the ii-th row of MM, for i=1,2i=1,2. The integers given as input are between 11 and 50,00050,000, and each row does not contain duplicate numbers.

输出格式

Your program is to write to standard output. Print exactly one line. The line should contain the maximum of MSIS among all possible permutations of columns of MM.

6
1 2 3 4 5 6
6 2 3 5 4 1
36
5
50 40 3 2 1
1 2 3 100 200
396