HZNUOJ

新手教练

Tags:
Time Limit:  2 s      Memory Limit:   256 MB
Submission:71     AC:21     Score:100.00

Description

        众所周知,在一场足球比赛中每队的上场队员最多不超过$11$人,最少不少于$7$人,每个人又有自己不同的职位,只有各司其职相互配合,才能赢得比赛。

        一场特殊足球比赛迫在眉睫,这场比赛共有$M$个站位可供选择,足球队的队员都想作为球员上场,而你作为足球队的新手教练也希望第一次指挥比赛能够做出正确的选择,因此你必须仔细斟酌,从所有队员中选出$M$个并适当安排使得整个球队能发挥出最大的实力。

Input

第一行两个数字$N$,$M$表示足球队共有$N$个队员,这场比赛总共有$M$个位置每个位置$1$个名额可供选择。

接下去$N$行每行$M$个整数$a_{ij}$表示第$i$个队员上场并且在站位$j$时预计能为球队做出$a_{ij}$的贡献值。

Output

一个数字$X$,表示经过适当的安排后本场比赛能够得到的最大贡献值。

Samples

input
4 3 1 2 3 2 3 1 3 2 1 2 2 2
output
9

Hint

$1\le M\le 11\\
M\le N\le 1000\\
0\le a_{ij}\le 1000
$

对于样例,显然让球员1作为位置3,球员2作为位置2,球员3作为位置1能够得到最大的预期贡献值。

Author

BAO, Min