792. 机器分配
SPJ
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 总公司拥有$M$台 **相同** 的高效设备，准备分给下属的 $N$ 个分公司。 各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。 问：如何分配这 $M$ 台设备才能使国家得到的盈利最大？ 求出最大盈利值。 分配原则：**每个公司有权获得任意数目的设备，但总台数不超过设备数 $M$**。 ## 输入格式 第一行有两个数，第一个数是分公司数 $N$，第二个数是设备台数 $M$； 接下来是一个 $N \times M$ 的矩阵，矩阵中的第$ i $行第 $j $列的整数表示第 $i$ 个公司分配$ j $台机器时的盈利。 ## 输出格式 第一行输出最大盈利值； 接下 $N$ 行，每行有 $2$个数，即分公司编号和该分公司获得设备台数。 **答案不唯一，输出任意合法方案即可**。 ## 数据范围 $1\leN\le10$, $1\leM\le15$ ## 输入 ```in1 3 3 30 40 50 20 30 50 20 25 30 ``` ## 输出 ```out1 70 1 1 2 1 3 1 ``` ## 提示 样例1解释， 第一行表示第1号分公司分配1台盈利30，分配到2台盈利40，分配到3台盈利50， 第一行表示第2号分公司分配1台盈利20，分配到2台盈利30，分配到3台盈利50， 第一行表示第3号分公司分配1台盈利20，分配到2台盈利25，分配到3台盈利50。