Problem Description
The badminton team has n men and women athletes. Given 2 n×n matrices P and Q. P[i][j] is the male athlete competition advantage of the male athlete i and female athlete j pairing together to form a mixed doubles; Q[i][j] is the female athlete competition advantage of the female athlete i and male athlete j. Due to various factors such as technical cooperation and psychological state, P[i][j] does not necessarily equal Q[j][i]. The male athlete i and female athlete j paired together to form a mixed doubles match between the male and female competition advantage is P[i][j]*Q[j][i].
Design aalgorithm, calculate the best pairing method for male and female athletes, so as to maximize the sum of the competition advantages of both men and women in each group.
Design an algorithm to calculate the best pairing method for male and female athletes for a given male and female athletes so that the sum of the competitive advantages of both male and female parties in each group can reach the maximum.
Input
The first line of the input data has 1 positive integer n (1≤n≤20). The next 2n rows, n numbers per row. The first n lines are p, and the last n lines are q.
Output
The maximum output of the calculated sum of the competition advantages of both men and women.
Sample Input
3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1
Sample Output
52
Hint
Source
The badminton team has n men and women athletes. Given 2 n×n matrices P and Q. P[i][j] is the male athlete competition advantage of the male athlete i and female athlete j pairing together to form a mixed doubles; Q[i][j] is the female athlete competition advantage of the female athlete i and male athlete j. Due to various factors such as technical cooperation and psychological state, P[i][j] does not necessarily equal Q[j][i]. The male athlete i and female athlete j paired together to form a mixed doubles match between the male and female competition advantage is P[i][j]*Q[j][i].
Design aalgorithm, calculate the best pairing method for male and female athletes, so as to maximize the sum of the competition advantages of both men and women in each group.
Design an algorithm to calculate the best pairing method for male and female athletes for a given male and female athletes so that the sum of the competitive advantages of both male and female parties in each group can reach the maximum.
Input
The first line of the input data has 1 positive integer n (1≤n≤20). The next 2n rows, n numbers per row. The first n lines are p, and the last n lines are q.
Output
The maximum output of the calculated sum of the competition advantages of both men and women.
Sample Input
3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1
Sample Output
52
Hint
Source