开始 2024-04-06 14:20:00

20240406 背包问题一(maoyu)

结束 2024-04-13 00:00:00
Contest is over.
当前 2024-05-16 17:35:05

G. 最优选课

描述

有n个课程,最多有m天可以学习,每个课程花费不同的天数得到的收益不同,第i个课程花费j天来学习的收益为w[i][j],问如何安排收益最大。

输入

输入包含多组数据,每组数据第一行有两个整数n和m表示课程数和学习天数。

随后是一个矩阵数组w[i][j],(1\le i\le n\le100,1\le j\le m\le100)

n=0且m=0表示输入全部结束。

输出

每组数据输出一行,即一个整数,表示最大收益。

样例

输入

2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0

输出

3
4
6

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交