#1411. 升级完成了,来测

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Rhodoks

题目描述

空间站「黑塔」中,精密的仪器正在沉睡。为了探明「星神」的奥秘,天才俱乐部的四位会员联合发起了这个项目。以掌握的种种情报作为载体,银河以代码形式重现。

其名为——「模拟宇宙」。

只需启动它,虚拟世界便顷刻间形成,敌人、同伴……无数的数据化作虚拟形象,等待下一步行动。通过与命途的连接,虚拟的星神也将投来瞥视......

在空间站主人黑塔的办公室中蕴藏着一台神奇机器,由黑塔及她的合伙人设计打造,可以创造出一个代码构成的虚拟世界。

如图,黑塔求你测一下她全新升级的「模拟宇宙」。升级过的「模拟宇宙」的地图是一个 的矩阵 ,其左上角为 右下角为 ,矩阵上的每个点都是一个区域。宇宙碎片是衡量「模拟宇宙」效果的一大重要指标,你的起始宇宙碎片数量为

「模拟宇宙」总是存在各种各样的事件或者战斗,因此经过矩阵上的区域会导致你的宇宙碎片数量发生变化。令 代表在矩阵第 行第 列上的区域带来的宇宙碎片变化值。也就是说,每当你经过 时,你的碎片就会加上 。当然,你的宇宙碎片也可能在某个时刻被扣为负数。

另外,如果 则代表这个位置包含了传送门。当你经过一个传送门时,你可以选择前往任意其他包含传送门的区域,传送结束后,你的宇宙碎片也会受到目的区域变化值的影响。当然你也可以选择不使用某个区域的传送门(但你经过了这个区域,即使不传送也会扣除碎片)。

因为你是测试用户,黑塔让你选择第 行的任意区域作为探索的起点。你可以每次选择向左下、正下、右下移动一格,但是不能向地图外移动。更正式地,如果你当前的区域坐标为 ,你可以前往 。而你在第 行的任意区域时,你就可以选择结束探索并结算宇宙碎片(或者不结束探索,而是通过该区域的传送门前往其他区域)。

请你计算一下当你结束探索时,你最高能获得的宇宙碎片数量。如果能获得正无穷的宇宙碎片,则说明模拟宇宙出了BUG,因此输出laice

输入格式

第一行两个正整数 代表地图大小。

接下来 行,每行 个整数,代表

输出格式

一行一个整数,代表你最高能获得的宇宙碎片数量。如果能获得正无穷的宇宙碎片,则输出laice

样例

样例输入1

3 3
-1 2 -1
-2 -3 -1
-2 -3 0

样例输出1

1

样例输入2

4 3
1 1 1
-1 -2 5
-2 3 3
-1 -1 4

样例输出2

laice

样例输入3

3 6
1 -1 4 5 1 4
1 9 -1 9 1 9
8 1 0 -8 -1 0

样例输出3

29

数据范围与提示

在样例1中,可以获得最大分数的路径为 ,总共可以获得 宇宙碎片

在样例2中, 都是传送门,可以循环通过路经 获得正无穷的宇宙碎片

实际上,如果「模拟宇宙」的地图只是一个普通的有向无环图(DAG),你也可以得出正确的答案。本题的地图只是一种特殊的版本的DAG。