Description

“卖书了，卖书了！

亏本大甩卖啊！”

大书商小明非常想把手上的M本书卖给旗下N家加盟店。已知这些店收购这些书会给小明带来一定的利润，请你设计一个算法，帮助大书商小明获得最大盈利。

已知1≤M≤15，1≤N≤10，小明可以任意数量的书卖给任意加盟店，但总数不超过小明持有的数M。

Input Format

第一行有两个数，第一个数是小明持有的书本数N，第二个数是加盟店店数M。

接下来是一个N*M的矩阵，表明了第I个加盟店卖得J台书本的盈利。

Output Format

第1行为最大盈利值

第2到第n行为第x个加盟店分y本所产生的利润

并使输出的答案字典序最小

3 3
50 60 30
30 20 80
60 80 50​

140
1 1
2 1
3 1​

Hint

背包问题经典解法

Source

动态规划