Minimum Days for Long-term Residency Application

In a certain region, temporary residents must obtain a red card in order to secure long-term residency. The process to obtain a red card consists of \(N\) sequential steps. For each step, the government has \(M\) workers (grouped into \(M\) groups, where each group has one worker per step) who verify the submitted documents. Each worker takes a specific number of days to process an application and these times are publicly available.

An applicant can choose any group for the first step and then, at the boundary between consecutive steps, may decide either to continue with the same group or to switch to a different group. However, switching groups is strictly controlled: it can only be made between two consecutive steps and only from group \(i\) to group \(i+1\) (with group \(M\) being allowed to switch to group \(1\)) . There is no limit on the number of switches.

For example, consider \(3\) groups and \(4\) steps with the following processing days:

• Group 1: 2, 6, 1, 8
• Group 2: 3, 6, 2, 6
• Group 3: 4, 2, 3, 6

You can either complete all steps with Group 1, taking a total of \(2+6+1+8=17\) days, or use a switching strategy: for instance, choose Group 2 for step 1, switch to Group 3 for step 2, switch to Group 1 for step 3, and finally switch to Group 2 for step 4, which takes \(3+2+1+6=12\) days. No strategy can achieve a total time less than 12 days.

Your task is to determine the minimum total number of days required to complete the application process.

inputFormat

The input begins with two integers \(M\) and \(N\) where \(M\) is the number of groups and \(N\) is the number of steps. Each of the following \(M\) lines contains \(N\) integers, where the \(j\)-th integer in the \(i\)-th line indicates the number of days that the worker from group \(i\) takes to process step \(j\).

outputFormat

Output the minimum total number of days required to finish all \(N\) steps.

sample

3 4
2 6 1 8
3 6 2 6
4 2 3 6

12