#P14092. [ICPC 2023 Seoul R] M. S. I. S.
[ICPC 2023 Seoul R] M. S. I. S.
题目描述
We are given a matrix of positive integers, and each row of does not contain duplicate numbers. For -th row of , , we find the maximum sum of increasing subsequence contained in . For example, if is given as the figure below, is and is . We call the maximum sum of increasing subsequences, MSIS.
Once we permute the columns of , MSIS can change. For example, if we permute the columns of the above matrix to as the figure below, MSIS becomes .
Given a matrix , write a program to output the maximum of MSIS among all possible permutations of the columns of .
输入格式
Your program is to read from standard input. The input starts with a line containing an integer, (), where is the number of columns of the input matrix . In the following two lines, the -th line contains positive integers of the -th row of , for . The integers given as input are between and , 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 .
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