测试数据来自 system/3057

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：300毫秒　　内存限制：256M

---

【问题描述】

　　花店前有 \(m\) 个花瓶列成一排，从左到右依次标号为 \(1..m\)；同时，花店共有 \(n\) 束花，标号为 \(1..n\)。

　　现在要把这 \(n\) 束花按标号从小到大的顺序插入到花瓶中（一个花瓶最多插入一束花），所谓的按顺序插入，就是指当 \(i < j\)时，花束 \(i\) 必须插入到花束 \(j\) 左边的花瓶中。当花瓶中插入不同的花束时，会产生不同的美学效果，即花束 \(i\) 插入到花瓶 \(j\) 的美学值为 \(f[i][j]\)（为一个 \([-50,50]\) 之间的一个整数）。

　　请编程回答，要怎样插入这 \(n\) 束花，才能使总的美学值最大？

【输入格式】

　　第一行是整数 \(n\) 和 \(m\)，\(n\) 表示花束的数量，\(m\) 表示花瓶的数量。
　　接下来的 \(n\) 行，每行 \(m\) 个空格分开的整数，其中第 \(i+1\) 行第 \(j\) 个整数表示 \(f[i][j]\)，即花束 \(i\) 插如花瓶 \(j\) 里的美学值。

【输出格式】

　　输出一个整数，表示最大美学值。

【输入输出样例】

　Input

3 5
4 20 -3 -9 13
5 18 -5 10 20
-9 5 -4 -10 17

　Output

47

【样例解释】

　　美学价值最大一种插入方案为：花束1拜访在花瓶2中，花束2拜访在花瓶4中，花束3拜访在花瓶5中，美学价值为：20 + 10 + 17 = 47。

【数据限制】

　　对于 \(80\%\) 的数据，\(1≤n≤m≤100\)，\(-50≤f[i][j]≤50\)。
　　对于 \(100\%\) 的数据，\(1≤n≤m≤1000\)，\(-50≤f[i][j]≤50\)。

【来源】

　　Mr.he