超能侠面临一个设备分配的难题。他拥有 M 台设备，准备销售给 N 个公司，每个公司可能获得0~M台的设备。不同公司开出的价格不同，且随着设备台数的增加，超能侠和各个公司谈好了优惠，不同台数对应的价格由一个N*M的矩阵来表示。

问：如何分配这 M 台设备才能使超能侠得到的利润最大？求出最大利润值。

输入文件第一行为用一个空格隔开的两个整数N和M，分别代表公司数和设备台数。接下来是一个N*M的矩阵，表示给第i个公司j台设备的利润。

输出文件第一行为最大利润值，接下来N行表示第i家公司分x台。如果有最大利润相同的方案，要求答案的字典序最小。

对于40%的数据，保证N=2；

对于100%的数据，保证 2≤N≤10, 1≤M≤15，0≤矩阵中的元素≤100。

注意，矩阵中同一行的元素不保证单调递增，所以可能出现卖出更多的设备反而获利更少的情况，此时可以考虑不卖出所有M台设备。