題目描述

某地臨時居民想獲得長期居住權就必須申請拿到紅牌。獲得紅牌的過程是相當復雜 ，一共包括N個步驟。每一步驟都由政府的某個工作人員負責檢查你所提交的材料是否符合條件。為了加快進程，每一步政府都派了M個工作人員來檢查材料。不幸的是，并不是每一個工作人員效率都很高。盡管如此，為了體現“公開政府”的政策，政府部門把每一個工作人員的處理一個申請所花天數都對外界公開。

為了防止所有申請人都到效率高的工作人員去申請。這M*N個工作人員被分成M個小組。每一組在每一步都有一個工作人員。申請人可以選擇任意一個小組也可以更換小組。但是更換小組是很嚴格的，一定要相鄰兩個步驟之間來更換，而不能在某一步驟已經開始但還沒結束的時候提出更換，并且也只能從原來的小組I更換到小組I+1,當然從小組M可以更換到小組1。對更換小組的次數沒有限制。

例如：下面是3個小組，每個小組4個步驟工作天數：

小組1 2 6 1 8

小組2 3 6 2 6

小組3 4 2 3 6

例子中，可以選擇小組1來完成整個過程一共花了2+6+1+8=17天，也可以從小組2開始第一步，然后第二步更換到小組3，第三步到小組1，第四步再到小組2，這樣一共花了3+2+1+6=12天。你可以發現沒有比這樣效率更高的選擇。

你的任務是求出完成申請所花最少天數。

思路

用f[j][i]表示當前最小值 f[j][i]+=min(f[j][i-1],f[j-1][i-1]) O(nm)