308001 - 机器分配

工厂购进M台机器用于生产零件,准备分给N个小组。各小组若获得这些机器,可以生产一定量的零件。每个小组有权获得任意数量的机器,但总数不得超过总机器数M。问:如何分配这M台机器使生产的零件数最多?试求出所有小组能生产的最多零件数和。

输入

第一行有两个数,第一个数是小组数N(N\le15),第二个数是机器数M(M\le15)。接下来是一个N×M的矩阵,表明了第i个小组分配j台机器能生产的零件。

输出

输出所有小组能生产的最多零件数和。

样例

输入

3 3
30 40 50
20 30 50
20 25 30

输出

70
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题