#2565. 价值最大化

价值最大化

Description

小明这学期有nn 门课程,他计划最多花mm 天学习。

根据他在不同课程上花费的天数,他将获得不同的价值,求如何安排nn 门课程的mm 天可使价值最大化。

Format

Input

输入包含多个测试用例。

每个测试用例的第11行都包含两个正整数nnmm ,分别表示课程数和天数。

接下来是矩阵aa [[ii ][][jj ]]11ii nn 11000011jj mm 110000aa[ [ii ][][jj ]]表示在第ii 门课程上花 费jj 天将获得的价值。

nn =00mm =00时结束输入。

Output

对每个测试用例,都单行输出获得的最大价值。

Samples

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

来源

HDU1712