People working in MDCS (Microsoft Development Center Serbia) like partying. They usually go to night clubs on Friday and Saturday.
There are people working in MDCS and there are 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 - number of employees in MDCS.
Then an matrix follows, where element in row and column is an integer number that represents how much person likes club’s Friday party.
Then another matrix follows, where element in row and column is an integer number that represents how much person likes club’s Saturday party.
Output Specification
Output should contain a single integer – maximum sum of happiness possible.
Constraints
- is even
- level of likeness
- 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: person with club ( happiness) and person with club ( happiness).
Saturday: person with club ( happiness) and person with club ( happiness)
Comments