Bubble Cup V8 C Party

View as PDF

Submit solution


Points: 20
Time limit: 1.5s
Memory limit: 6M

Problem type

People working in MDCS (Microsoft Development Center Serbia) like partying. They usually go to night clubs on Friday and Saturday.

There are N people working in MDCS and there are N clubs in the city. Unfortunately, if there is more than one Microsoft employee in night club, level of coolness goes infinitely high and party is over, so club owners will never let more than one Microsoft employee enter their club in the same week (just to be sure).

You are organizing night life for Microsoft employees and you have statistics about how much every employee likes Friday and Saturday parties for all clubs.

You need to match people with clubs maximizing overall sum of their happiness (they are happy as much as they like the club), while half of people should go clubbing on Friday and the other half on Saturday.

Input Specification

The first line contains integer N - number of employees in MDCS.

Then an N\times N matrix follows, where element in i^{th} row and j^{th} column is an integer number that represents how much i^{th} person likes j^{th} club’s Friday party.

Then another N\times N matrix follows, where element in i^{th} row and j^{th} column is an integer number that represents how much i^{th} person likes j^{th} club’s Saturday party.

Output Specification

Output should contain a single integer – maximum sum of happiness possible.

Constraints

  • 2 \le N \le 20
  • N is even
  • 0 \le level of likeness \le 10^6
  • All values are integers

Note: This problem has low memory limit!

Example Input

4
1 2 3 4 
2 3 4 1
3 4 1 2 
4 1 2 3 
5 8 7 1 
6 9 81 3
55 78 1 6
1 1 1 1

Example Output

167

Explanation

Here is how we matched people with clubs:

Friday: 1^{st} person with 4^{th} club (4 happiness) and 4^{th} person with 1^{st} club (4 happiness).

Saturday: 2^{nd} person with 3^{rd} club (81 happiness) and 3^{rd} person with 2^{nd} club (78 happiness)

4+4+81+78 = 167


Comments

There are no comments at the moment.