3926: P1130 红牌

某地临时居民想获得长期居住权就必须申请拿到红牌。获得红牌的过程是相当复杂，一共包括 N 个步骤。 每一步居委会都派了 M 个工作人员来检查材料。这 M×N 个工作人员被分成 M 个小组，每一组在每一步都有一个工作人员。 申请人可以选择任意一个小组也可以更换小组。但是更换小组是很严格的： - 一定要在相邻两个步骤之间来更换 - 只能从原来的小组 I 更换到小组 I+1（从小组 M 可以更换到小组 1） - 对更换小组的次数没有限制 求完成申请所花最少天数。

第一行：两个正整数 N 和 M，表示步数和小组数 (1 ≤ N, M ≤ 2000) 接下来 M 行：每行 N 个非负整数，第 i+1 行的第 j 个数表示小组 i 完成第 j 步所花的天数 (不超过 100000)

一个正整数，为完成所有步所需最少天数

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

12