Maximum Mixed Doubles Advantage

In a badminton team, there are n male athletes and n female athletes. You are given two n × n matrices \(P\) and \(Q\). Here, \(P_{i,j}\) denotes the competitive advantage of the male athlete i when paired with the female athlete j in a mixed doubles match, while \(Q_{i,j}\) denotes the advantage of the female athlete i when paired with the male athlete j. Note that due to factors like technical coordination and mental state, it is not necessarily true that \(P_{i,j} = Q_{j,i}\). The overall competitive advantage for a pairing of male athlete i and female athlete j is defined as
\[ P_{i,j} \times Q_{j,i} \] Design an algorithm to find the optimal pairing between male and female athletes such that the sum of the advantages over all pairs is maximized.

inputFormat

The first line contains an integer n, representing the number of male (and female) athletes. The next n lines each contain n integers, representing the matrix P. This is followed by n lines each with n integers, representing the matrix Q. The value in the i-th row and j-th column of Q corresponds to (Q_{i,j}). Note that in the computation, the pairing of male athlete i with female athlete j uses the value (Q_{j,i}).

outputFormat

Output a single integer — the maximum total competitive advantage for mixed doubles pairing, calculated as (\sum_{i=1}^{n} \left(P_{i,\sigma(i)} \times Q_{\sigma(i),i}\right)), where (\sigma) is a permutation of ({1,2,\dots,n}) representing the pairing.

sample

2
1 2
3 4
1 6
5 2

28