Warehouse Consolidation Problem

The company has n warehouses and n types of goods. Initially, due to poor categorization, many warehouses store multiple types of goods. The task is to reorganize the goods so that each warehouse stores only one type of good, i.e. each good is consolidated into a unique warehouse.

Whenever a good is moved from one warehouse to another, the cost incurred equals the weight of that good. The overall cost is the sum of the weights of all goods that are moved.

Let \(a_{ij}\) denote the weight of good \(j\) in warehouse \(i\). The total weight is \(\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}\). After reorganization, if we assign warehouse \(i\) to store good \(\pi(i)\), then we save a cost of \(a_{i,\pi(i)}\) because these goods remain in their original warehouse. Therefore, the cost for an assignment \(\pi\) is:

[ Cost = \sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij} - \sum_{i=1}^{n}a_{i,\pi(i)} ]

The problem requires you to choose a permutation \(\pi\) (i.e. assign each warehouse exactly one good type) so that the overall moving cost is minimized.

inputFormat

The first line contains an integer n (the number of warehouses/goods).
Each of the next n lines contains n non-negative integers. The j-th integer on the i-th line represents \(a_{ij}\), the weight (or quantity) of good \(j\) in warehouse \(i\).

Constraints: You can assume that \(n\) is small (for example, \(n \leq 17\)).

outputFormat

Output a single integer representing the minimum total cost required to reorganize the goods so that each warehouse contains only one type of good. (That is, output \(TotalW - M\), where \(TotalW = \sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}\) and \(M\) is the maximum sum obtainable from selecting exactly one element from each row with distinct columns.)

sample

2
1 2
3 4

5