题目描述

一名临时居民申请红牌需要依次完成 $N$ 个办理步骤。办事大厅共有 $M$ 个工作组，每个组在每个步骤都有一名工作人员，处理所需天数可能不同。申请人可以任选一个工作组开始；完成一个步骤后，可以留在当前组，也可以转到编号的下一个组，且第 $M$ 组的下一个组是第 $1$ 组。办理某一步的过程中不能换组。请计算完成全部步骤最少需要多少天。

输入格式

第一行输入两个整数 $N,M$，分别表示步骤数和工作组数。

接下来 $M$ 行，每行 $N$ 个非负整数；第 $i$ 行第 $j$ 个数表示第 $i$ 组办理第 $j$ 步所需天数。

输出格式

输出一个整数，表示完成全部步骤的最少天数。

数据范围与约定

$1\le N,M\le2000$，每个办理时间不超过 $10^6$。

可见测试数据

输入数据 1

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

输出数据 1

12

输入数据 2

4 3
5 7 10 7
7 9 6 7
7 8 5 4

输出数据 2

22

输入数据 3

5 4
8 2 7 5 9
6 4 3 8 2
7 5 6 1 4
9 3 5 2 6

输出数据 3

18