140005 - ACboy needs your help

ACboy本学期有N门课程,他计划最多花M天学习。当然,他将从不同的课程中获得的利润取决于他在课程上花费的时间。如何安排N门课程的M天以实现利润最大化?

输入

输入由多组样例组成。每组样例第一行包含两个正整数N和M,N表示课程数,M是ACboy拥有的天数。

接下来是矩阵a[i][j],(1<=i<=N<=100,1<=j<=M<=100)。A[i][j]表示如果ACboy在第i门课上花费j天,他将获得A[i][j]的收益。

N=0且M=0结束输入。

输出

每组样例输出一行,其中包含ACboy将获得的最大收益。

样例

输入

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

来源

HDU-1712
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题