题目描述

禾木本学期有N门课程，他计划最多花$M$天学习。当然，他将从不同的课程中获得的收益取决于他花在上面的天数。如何安排这M天，实现收益最大化？

输入格式

第一行包含两个正整数 N 和 M 的行开头，N 是课程数，M 是 禾木学习的天数。 $\\$接下来遵循矩阵 $A[i][j]$（$1<=i<=N<=100，1<=j<=M<=100$）。$A[i][j]$ 表示如果 禾木 在第 $i$ 门课程上花费 $j$ 天，他将获得价值 $A[i][j]$（$1<=A[i][j]<=10000$） 的利润。

输出格式

输出一行，其中包含 禾木 将获得的最大收益。

样例 #1

样例输入 #1

2 2
1 2
1 3

样例输出 #1

3

样例 #2

样例输入 #2

2 3
3 2 1
3 2 1

样例输出 #2

6