机器分配
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
总公司拥有高效设备 台，准备分给下属的 个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这 台设备才能使国家得到的盈利最大？求出最大盈利值。其中 ，。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 。
输入格式
第一行有两个数，第一个数是分公司数 ，第二个数是设备台数 。
接下来是一个 的矩阵，表明了第 个公司分配 台机器的盈利。
最大盈利值相同时，要求编号小的公司分得设备尽可能少。
输出格式
第一行为最大盈利值。
接下来 行为第 分公司分 台。
3 3
30 40 50
20 30 50
20 25 30
70
1 1
2 1
3 1