P1130 Red Card

To obtain long-term residency, temporary residents must apply for a red card. The process consists of $N$ steps. Each step is handled by a government staff member who checks whether your submitted materials meet the requirements. To accelerate the process, at each step the government assigns $M$ staff members to check materials. Unfortunately, not every staff member is efficient. Nevertheless, to embody the policy of “open government,” the department publicly releases the number of days each staff member takes to handle one application. To prevent all applicants from flocking to the most efficient staff, these $M \times N$ staff members are divided into $M$ groups. Each group has exactly one staff member at each step. An applicant may choose any one group and may also switch groups. However, switching is strictly limited: it must occur between two adjacent steps, not during a step that has already started but not yet finished; moreover, you can only switch from your current group $I$ to group $I+1$, and from group $M$ you may switch to group $1$. There is no limit on the number of switches. For example, here are $3$ groups, with working days for $4$ steps per group: - Group $1$: $2, 6 ,1 ,8$; - Group $2$: $3,6, 2, 6$; - Group $3$: $ 4, 2 ,3 ,6$. In this example, you can choose group $1$ for the entire process, which takes $2+6+1+8=17$ days. Alternatively, you may start with group $2$ for step one, then switch to group $3$ for step two, to group $1$ for step three, and to group $2$ for step four, for a total of $3+2+1+6=12$ days. You can see that no choice is more efficient than this. Your task is to find the minimum number of days needed to complete the application.

The first line contains two positive integers $N$ and $M$, the number of steps and the number of groups. Then there are $M$ lines, each containing $N$ non-negative integers. On the $i$-th of these lines $(1 \le i \le M)$, the $j$-th number denotes the number of days group $i$ needs to complete step $j$. All day counts do not exceed $1000000$.

Output a single positive integer, the minimum number of days required to complete all steps.

Constraints: For $100\%$ of the testdata, $1 \le N,M \le 2000$. Translated by ChatGPT 5