Thornhill Computer Club 2023 - September Contest - Problem 10

Mr. Z is a dedicated teacher at ZSS who is always on the lookout for innovative ways to engage his students. With a passion for gaming and a deep understanding of its benefits, Mr. Z has recently made an exciting decision—to create an e-sports team at ZSS! Driven by a desire to excel and bring glory to the school, Mr. Z aspires to lead his team to victory in the local e-sports league.

However, he faces a challenge in building a formidable team. To do so, he needs to carefully assign players to ~N~ (~1 \le N \le 20~) different positions, ensuring that each position is filled by a unique player. Fortunately, fate seems to be on Mr. Z's side as there are exactly ~N~ enthusiastic players eagerly waiting to join the team. Each player, denoted as ~p~, brings a unique set of skills and abilities to the table. Additionally, they have individual playtime values, represented as ~p_i~ (~0 \le p_i \le 10^4~) for each position ~i~. Realizing the significance of optimal player-position assignments, Mr. Z seeks your assistance in maximizing the total playtime for the team. He believes that by assigning players to positions where their total playtime is the highest, the team's overall performance will improve significantly.

Now, armed with your expertise, it's time to help Mr. Z assign positions to players strategically, leading to the creation of a powerful e-sports team that can conquer the local league and bring glory to ZSS!

Input Specification

The first line of input will be an single integer ~N~ representing the total number of players and team positions.
The next ~N~ lines will consist of ~N~ integers representing the players and their respective playtimes for each position.
More specifically, the ~i~ th integer on line ~p~ will represent the playtime that player ~p~ has in position ~i~

Output Specification

On a single line, output the maximum total playtime of the team.

Subtasks

Subtask 1 [10%]:
~n \le 2~

Subtask 2 [20%]:
~n \le 5~

Subtask 3 [70%]:
No further constraints.

Sample Input 1

2
3 30
24 12

Sample Output 1

54

Explanation for Sample Output 1

The optimal team would consist of:

• Player 1 playing position 2 with 30 hours of playtime
• Player 2 playing position 1 with 24 hours of playtime

This team would have a total playtime of 54 hours, the maximum possible out of all arrangements.

Sample Input 2

3
90 180 270
680 120 12
80 300 450

Sample Output 2

1310

Explanation for Sample Output 2

The optimal team would consist of:

• Player 1 playing position 2 with 180 hours of playtime
• Player 2 playing position 1 with 680 hours of playtime
• Player 3 playing position 3 with 450 hours of playtime

This team would have a total playtime of 1310 hours, the maximum possible out of all arrangements.

Sample Input 3

20
45 29 33 81 95 75 91 53 78 70 35 69 66 51 97 28 7 5 67 1 
25 31 21 18 28 38 71 81 72 13 75 35 52 54 69 65 12 19 38 85 
64 21 58 81 26 58 8 67 48 39 20 28 13 49 33 64 31 46 79 8 
17 60 33 57 39 20 46 40 55 22 95 33 73 22 52 79 70 18 16 58 
80 55 51 63 7 5 13 24 92 51 90 65 30 20 26 33 57 5 65 58 
80 73 56 96 68 53 86 44 11 86 83 42 85 87 99 7 80 90 85 61 
86 45 48 35 72 46 86 62 55 68 34 14 72 23 87 46 73 99 48 87 
76 91 21 27 70 85 61 30 20 36 23 87 14 60 3 1 40 84 8 26 
79 61 55 82 23 15 55 81 24 21 38 45 4 42 27 29 90 49 44 4 
65 35 30 22 79 39 37 86 40 22 8 51 61 35 92 86 95 55 75 80 
27 89 71 40 39 95 69 21 65 89 71 44 99 44 48 97 16 29 74 39 
37 15 79 48 53 94 66 45 45 95 47 1 8 66 56 34 7 75 45 14 
68 94 31 93 54 39 90 98 70 99 18 13 33 35 2 89 56 62 50 68  
5 32 21 59 72 4 25 100 90 57 88 63 54 81 53 44 20 48 90 84  
51 93 62 33 41 40 26 52 90 58 29 52 80 63 77 94 33 66 55 100  
49 100 91 77 17 38 85 40 69 99 30 16 95 89 32 37 93 47 94 76  
6 16 46 42 57 3 40 19 79 39 38 40 47 88 82 19 65 25 5 43  
27 47 75 3 99 10 28 1 95 91 46 32 36 23 82 71 48 80 85 75  
65 3 60 91 50 36 40 36 25 75 46 80 6 16 73 27 43 55 3 32  
9 36 7 49 29 89 50 11 60 60 93 61 86 93 72 93 33 42 82 42

Sample Output 3

1848