Taco Seating Assignment

You are given n guests and m seats with a preference matrix P of size n × m. The element \(P_{i,j}\) represents the preference score for assigning seat \(j\) to guest \(i\). Your task is to assign exactly one seat to each guest (each seat can be used at most once) such that the total sum of the scores is minimized. In other words, if guest \(i\) is assigned seat \(j_i\), you need to minimize the sum

[ \sum_{i=0}^{n-1} P_{i, j_i} ]

You can assume that \(m \ge n\), so an assignment always exists. Solve this problem and output the minimal total sum.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers \(n\) and \(m\): the number of guests and the number of seats.
• The next \(n\) lines each contain \(m\) space-separated integers. The \(j^{th}\) integer in the \(i^{th}\) line represents \(P_{i,j}\), the preference score for guest \(i\) for seat \(j\).

outputFormat

Output to standard output (stdout) a single integer which is the minimum sum of the assigned preference scores.

3 3
1 2 3
3 1 2
2 3 1

3