Problem 5572 --[动归基础]机器分配

5572: [动归基础]机器分配

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 88  Solved: 26
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][76kb]

Description


机器分配

assigned.pas/c/cpp

【问题描述】

    总公司拥有高效生产设备M台,准备分给下属的N个公司。各分公司若获得这些设备,可以为国家提供一定的盈利。

    问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M<=15,N<=10。

    分配原则:每个公司有权获得任意数目的设备,但总台数不得超过总设备数M。

【输入数据】:assigned.in

第一行两个数,第一个数是分公司数N,第二个数是设备台数M,。接下来是一个N*M的矩阵,表明了第I个公司分配J台机器的盈利。
【输出数据】:assigned.out
输出第一行为一个整数,表示盈利的最大值

以下n行,每行输出两个数据,分别表示公司编号和分配到的机器数量

【输入样例】
7 6
1 2 3 4 5 6
6 5 4 3 2 1
6 4 8 2 50 194
100 200 300 10 24 72
200 300 400 200 100 50
10 20 30 40 50 60
1 1 1 1 1 1
【输出样例】
700
1 0
2 0
3 0
4 3
5 3
6 0
7 0


Input

Output

HINT

Source

[Submit][Status]