总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。 
 
问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。 
 
分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。

第一行有两个数，第一个数是分公司数N，第二个数是设备台数M。

 接下来是一个N*M的矩阵，表明了第I个公司分配J台机器的盈利。

一个数，表示最大盈利值。
 
接下来若干行，表示分配给各公司的机器数，即使某公司分配的机器数是0也要输出。

注意，因为可能存在多种分配方案，所以输出字典序最小的答案。比如这个样例：

2 3
30 40 50
20 30 50 
 
  方案一：第一个公司分得1台、第二个公司分得2台，盈利30+30=60；方案二：第一个公司分得2台、第二个公司分得1台，盈利40+20=60。两个方案的盈利都是60，但是机器的分配方案是不同的，应该选方案一。

 因为方案一的机器分配序列“12”比方案二的序列“21”字典序小，即字符串12比字符串21小。