Party
Description
Note the unusual memory limit for the problem.
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.
The first line contains integer N — number of employees in MDCS.
Then an N × 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 × 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.
- 2 ≤ N ≤ 20
- N is even
- 0 ≤ level of likeness ≤ 106
- All values are integers
Output should contain a single integer — maximum sum of happiness possible.
Input
The first line contains integer N — number of employees in MDCS.
Then an N × 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 × 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.
- 2 ≤ N ≤ 20
- N is even
- 0 ≤ level of likeness ≤ 106
- All values are integers
Output
Output should contain a single integer — maximum sum of happiness possible.
Samples
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
167
Note
Here is how we matched people with clubs:
Friday: 1st person with 4th club (4 happiness) and 4th person with 1st club (4 happiness).
Saturday: 2nd person with 3rd club (81 happiness) and 3rd person with 2nd club (78 happiness).
4+4+81+78 = 167