机器分配
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
总公司拥有高效设备 台，准备分给下属的 个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这 台设备才能使国家得到的盈利最大？求出最大盈利值及分配方案。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 。
若最大盈利值有多种分配方案，要求编号小的公司分得的设备尽可能少。
输入格式
第一行包含两个整数 和 ，分别表示分公司数和设备台数。
接下来是一个 的矩阵，第 行第 列的整数表示第 个公司分配 台机器时的盈利。
输出格式
第一行输出一个整数，表示最大盈利值。
接下来 行，每行输出两个整数 和 ，表示第 个公司分得 台设备。
3 3
30 40 50
20 30 50
20 25 30
70
1 1
2 1
3 1
数据范围与提示
- 矩阵中的盈利值均为非负整数。