No submission language available for this problem.

Background

Special for beginners, ^_^

Description

小明这学期有 n 门课程，它计划最多花 m 天学习。根据他在不同课程上花费的天数，他将获得不同的价值，求如何安排 n 门课程的 m 天可以使得价值最大化。

Format

Input

输入包含多个测试用例。

每个测试用例的第 1 行都包含两个正整数 n 和 m，分别表示课程数和天数。

接下来是矩阵 a[i][j]，1 ≤ i ≤ n ≤ 100，1 ≤ j ≤ m ≤ 100。

a[i][j] 表示在第 i 门课程上花费 j 天将获得的价值。

在 n = 0，m = 0 时结束输入。

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

Limitation

1s, 1024KiB for each test case.