Speeeeedforces

时间限制：1s

空间限制：64MB

题目背景

最近，Codeforces举办了第二场 Div. 4 比赛（Round #784，上一次是两年前的 Round #640）。

显然这是十足的手速场，大佬们甚至可以在 \(12\) 分钟内写出这 \(8\) 题的完整代码。总罚时为 \(46\) 分钟（每道题的罚时是第一次 AC 与 比赛开始时刻 的时间间隔（单位为分钟），总罚时是各题的罚时之和。）

题目描述

现在假设一种情况，本场比赛恰有 \(n=8\) 题，有 \(m\) 人打算组成团队，他们共用一个账号，并通过“分工合作”的方式来加快账号的编程速度，减少比赛的 总罚时 （注意，这不符合Codeforces的比赛要求，请勿在实际比赛中尝试。）。

团队中每个人擅长的知识点不同，设 \(t_{ij}\) 是第 \(i\) 人编写第 \(j\) 题代码所需的时间。如果合理地分配任务，就能最小化罚时。请输出能达到的总罚时最小值。

输入格式

第一行一个正整数 \(n,m\)，表示比赛题目数量和团队人数。

接下来 \(m\) 行每行 \(n\) 个正整数，这 \(m\) 行中，第 \(i\) 行的第 \(j\) 个数是题目所述的 \(t_{ij}\) ，即第 \(i\) 人编写第 \(j\) 题代码所需的时间。

输出格式

输出总罚时的最小值。

样例输入1

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

样例输出1

23

样例1解释

设第一个人是\(A\)，第二个人是\(B\)，其中一种可行的方案：

\(A\)：第 \(1\) 分钟 做第一题；第 \(2\) 分钟 做第二题；第 \(3\) 分钟做第四题；第 \(4\) 分钟做第七题；

\(B\)：第 \(1\) 分钟做第三题；第 \(2\) 分钟 做第八题；第\(3\sim 4\)分钟做第五题；第\(5\sim 6\)分钟做第六题。

这样，每题的罚时是\((1,2,1,3,4,6,4,2)\)，总罚时是\(1+2+1+3+4+6+4+2=23\)分钟。

样例输入2

8 2
1 2 3 1 4 5 1 3
2 1 3 4 2 1 4 2

样例输出2

25

样例输入3

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

样例输出3

28

样例输入4

8 87
76436 13102 76190 21982 8120 68714 25006 14203 
24988 46064 16308 45226 19492 45419 10204 40037 
19023 19213 23943 17376 29578 24079 32379 26695 
3933 9023 6169 18916 3966 17165 3 16327 
51250 24014 58705 30001 56950 51991 36881 48090 
19304 14178 17334 19405 19896 13742 6337 12961 
7186 28861 39326 13556 43675 5558 29441 13264 
44746 78723 74391 51726 13357 65084 9139 58604 
14847 16946 9321 5750 6357 5717 9224 15656 
10683 22560 12511 46493 28746 21581 40855 26409 
5109 6872 5860 19216 23962 16247 15832 5748 
22094 46445 25817 54828 16248 31340 20137 79565 
10332 20818 19115 44191 5587 54987 46854 35292 
20701 29757 24991 7139 10595 8747 31817 9258 
7955 31105 34982 22920 9390 22488 25542 29686 
59203 30344 13113 17765 60916 30071 57007 24728 
32441 59692 74720 28016 63444 79779 64271 14347 
43213 29446 6811 6822 8192 17906 16517 44779 
14271 12625 49840 50956 40034 34959 15618 32737 
16128 22757 33963 16158 10970 10628 17937 19641 
34240 32094 9148 32650 24651 45678 13448 26741 
17119 43323 21352 14584 40114 45897 50665 57767 
40032 57483 34191 25984 50119 19975 52550 23277 
27591 26522 5399 22276 30980 11884 21745 14808 
14401 25571 32421 34916 24932 17494 30556 29302 
5699 18836 855 13174 5455 7905 1674 17144 
7838 16058 10928 5136 6420 8668 12185 15707 
43847 31174 14924 49558 6507 28901 32371 12195 
42748 55385 55500 13793 21154 22917 17168 33859 
31897 26241 15288 17933 32946 32870 10443 25137 
37268 39244 46271 16600 43107 7646 22578 10870 
13554 37580 17008 30357 34005 57841 58358 29606 
36239 45820 6311 64975 23497 22103 44340 54494 
13544 49620 49989 58875 59230 62820 6916 38866 
32332 37131 48400 23087 19473 43387 6532 45109 
6504 13259 47160 62477 7877 31159 30280 31571 
56945 38487 20626 27587 14435 32971 36310 26452 
9628 14822 21528 10666 21003 21873 23025 11936 
9378 79220 36179 58631 38781 23778 27825 12079 
6408 9647 19622 18410 9986 8396 6879 14640 
7151 17471 9788 9566 18790 6104 8770 15933 
10612 13790 15154 18186 7222 17879 27464 21330 
5655 45313 6682 27658 4009 5125 4883 25977 
37024 45964 20301 36463 35893 30762 30622 28072 
13114 11054 17004 15677 15579 16554 7087 19030 
38713 19127 69606 48125 48352 78616 40342 9780 
30909 75334 5118 79597 14709 52078 53892 40829 
5803 22786 5217 31809 11411 33596 10507 36963 
525 9026 1235 10276 919 5652 5272 16770 
28843 74758 32172 47796 48832 7013 50970 38900 
5061 57600 42231 57339 5679 10613 28856 45286 
40376 57742 57976 25910 77411 18034 28922 79036 
18540 5960 16020 9987 15857 16054 34795 33833 
23142 20557 16662 30486 61588 37521 33198 71382 
17722 17679 29403 7776 5805 17950 26082 31291 
22204 22755 28065 9535 9003 6270 29285 24482 
4622 18627 563 7199 578 18249 5129 18915 
14874 23151 5439 8440 34374 21658 5310 22124 
26060 21019 9050 12546 10171 19072 6095 15977 
14885 18366 29636 17717 38513 18833 19469 26439 
5727 31829 41100 20297 30584 14885 11208 10339 
1389 18654 1424 13025 1762 6598 1446 13727 
9202 58367 23457 5894 47590 24143 27348 8186 
30270 30718 10141 32720 41600 26723 14219 63469 
25590 79260 69915 46343 76200 12684 71922 23726 
35531 11075 14519 8483 38906 48540 22138 36500 
22777 5845 11692 23371 38395 34592 53967 52717 
15027 44474 49693 16584 47222 42307 21712 24312 
69167 38904 14438 16286 42373 64047 30685 56594 
6380 5190 12764 16885 9394 27322 22782 23699 
13383 5935 17571 18029 16462 11132 14756 5601 
27934 28209 18663 17335 31622 12134 16214 29298 
19215 12739 23283 35925 14346 31370 19945 33215 
74326 11738 45113 48176 13869 65647 53495 44784 
68058 24920 53384 64846 24092 22534 39549 68300 
27888 44442 31297 8332 38407 47556 30935 26288 
44229 29463 61756 53276 14141 9576 27626 13961 
32775 22627 7560 27637 5027 10303 32204 12093 
24479 22004 16191 58203 28529 5026 33203 34089 
17908 33996 16994 10636 44796 8462 45171 30416 
33114 20626 41156 10393 39805 43947 43196 58014 
35799 12122 19316 11254 31526 14768 46724 17883 
12008 15032 13102 7626 5114 13585 19316 14820 
6328 10547 6707 14555 15330 9974 11029 18010 
25094 19531 11351 12549 20575 24213 16743 20273 
31345 26416 8729 7815 20879 15993 20713 28620 
15377 10687 8979 16525 16858 22018 31485 8157 

样例输出4

22914

数据范围

对于 50 % 的数据，\(n=8,m = 2\)

对于 100 % 的数据，\(n = 8\)，\(1\le m\le 500\)，\(1\le t_{ij}\le 10^5\)