Maximum Sum of Non-Adjacent Columns

You are given a matrix of integers with n rows and m columns. Your task is to pick exactly one integer from each row such that no two selected integers are from the same column. The objective is to maximize the sum of the selected integers.

Note: If it is not possible to select one integer from each row without reusing a column (i.e. when n > m), the answer is 0.

The solution should utilize an exhaustive search (e.g. backtracking or permutation generation) since the matrix dimensions are expected to be small.

Example:

Input:
3 3
1 2 3
4 5 6
7 8 9
Output:
15

</p>

inputFormat

The first line contains two space-separated integers n and m representing the number of rows and columns of the matrix, respectively. Each of the next n lines contains m space-separated integers, representing the values in the matrix.

outputFormat

Output a single integer which is the maximum sum obtained by selecting one number from each row (with no two numbers from the same column). If a valid selection is not possible, output 0.

## sample

3 3
1 2 3
4 5 6
7 8 9

15