Maximum Non-attacking Grid Sum

You are given an (n \times n) grid of integers. Your task is to select exactly one cell from each row such that no two selected cells are in the same column. In other words, if you denote the index of the selected column in row (i) as (\pi(i)) for (0 \leq i < n), you need to maximize the sum: [ \max_{\pi}; \sum_{i=0}^{n-1} \text{grid}[i][\pi(i)] ] where (\pi) is a permutation of ({0, 1, \dots, n-1}).

This problem requires you to consider all possible cell selections (permutations) and determine the one that yields the maximum sum. It can be solved using backtracking or permutation generation techniques.

inputFormat

The input is given via standard input (stdin). The first line contains a single integer (n), the size of the grid. The next (n) lines each contain (n) space-separated integers, representing the rows of the grid.

outputFormat

Output the maximum sum achievable by selecting (n) cells, one from each row and each column, via standard output (stdout).## sample

3
1 2 3
4 5 6
7 8 9

15