工厂购进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