Minimizing Overall Disharmony

In this problem, you are given \(N\) paintings and \(N\) frames. For the pairing of the \(i\)-th painting with the \(j\)-th frame, two ratings are provided: the ordinariness \(A_{i, j}\) and the discord \(B_{i, j}\). If a pairing (or matching) is denoted by a permutation \(P\) where the \(i\)-th painting is paired with frame \(P_i\), then the overall disharmony is defined as:

[ \text{disharmony} = \left(\sum_{i=1}^{N} A_{i, P_i}\right) \times \left(\sum_{i=1}^{N} B_{i, P_i}\right)]

Your task is to determine the minimum possible disharmony that can be achieved by selecting an appropriate pairing of paintings and frames.

Note: It is guaranteed that \(N\) is small enough so that a solution based on complete enumeration (backtracking) will pass all test cases.

inputFormat

The input begins with a single integer \(N\) (\(1 \le N \le 10\)), representing the number of paintings (and frames). Following this, there are \(N\) lines, each containing \(N\) space-separated integers, representing the matrix \(A\) (the ordinariness ratings). After that, there are another \(N\) lines, each containing \(N\) space-separated integers, representing the matrix \(B\) (the discord ratings).

For example:

3
1 2 3
4 5 6
7 8 9
9 8 7
6 5 4
3 2 1

outputFormat

Output a single integer, which is the minimum possible overall disharmony.

The disharmony is computed as:

[ \left(\sum_{i=1}^{N} A_{i, P_i}\right) \times \left(\sum_{i=1}^{N} B_{i, P_i}\right) ]

sample

1
5
7

35