当前没有测试数据。

题目描述

小红经营着一家花店。为了迎接节日，她需要重新布置橱窗。

橱窗中有 F 个花瓶排成一排，编号从1到F。小红有 K 种不同的花，每种花只有一盆。她想将所有的花都放入花瓶中，每个花瓶最多放一盆花。

为了美观，小红制定了以下规则：

1. 第 i 种花必须放在第 i 种花之前的花瓶之后（花瓶编号要递增）
2. 不同种类的花放入不同的花瓶

每种花放在不同的花瓶中有不同的美观值。小红希望找到一种布置方案，使得总美观值最大。

输入格式

第一行两个整数 F 和 K，分别表示花瓶数量和花的种类数。

接下来 K 行，每行 F 个整数，第 i 行第 j 个数表示第 i 种花放在第 j 个花瓶中的美观值。如果该位置不能放这种花，则美观值为-1。

输出格式

一个整数，表示最大总美观值。如果无法完成布置，输出-1。

样例输入

5 3
-1 7 8 9 10
5 6 7 -1 -1
3 4 5 6 7

样例输出

23

样例解释

花瓶1-5编号，花种类1-3。

最优方案：

• 第1种花放在花瓶3：美观值8
• 第2种花放在花瓶2：美观值6
• 第3种花放在花瓶5：美观值7

但这样不满足花瓶编号递增规则！第2种花应该在第1种花之后。

正确的方案：

• 第1种花放在花瓶2：美观值7
• 第2种花放在花瓶3：美观值7
• 第3种花放在花瓶5：美观值7

总美观值：7+7+7=21

或者：

• 第1种花放在花瓶3：美观值8
• 第2种花放在花瓶4：但第2种花不能放花瓶4

重新分析：

• 第1种花放在花瓶2：美观值7，剩余花瓶3,4,5
• 第2种花放在花瓶3：美观值7，剩余花瓶4,5
• 第3种花放在花瓶5：美观值7 总美观值21

或者：

• 第1种花放在花瓶3：美观值8，剩余花瓶4,5
• 第2种花不能放花瓶4和5（都是-1）

所以最优解是21。

数据范围

对于 30% 的数据：F, K ≤ 20 对于 60% 的数据：F, K ≤ 100 对于 100% 的数据：F, K ≤ 500，美观值范围 [-1, 1000]