开宝箱
TimeLimit:1000ms MemoryLimit:128000KB
64-bit integer IO format:%lld
未提交 | 登录后收藏 | 已有5人收藏了本题
Problem Description
你确定我是来开宝箱不是来比赛的吗？？艾玛，这是哪，天啊，伦家竟然穿越了。
摆在眼前的是1个n*m（0< n<=100&&0< m<=100）的宝箱矩阵，而你就在这个矩阵的左上角也就是入口处。冲啊，开宝箱去，然而脚不听话啊，你的脚失去了向左走与向上走（方向是相对于整个地图，换句话说不是通过你脸的朝向来决定方向，你只能↓和→）的能力。（你：这设定真奇怪啊 。WGX大神：让你四处走还不把我的宝箱全开了）。
摆在眼前的是1个n*m（0< n<=100&&0< m<=100）的宝箱矩阵，而你就在这个矩阵的左上角也就是入口处。冲啊，开宝箱去，然而脚不听话啊，你的脚失去了向左走与向上走（方向是相对于整个地图，换句话说不是通过你脸的朝向来决定方向，你只能↓和→）的能力。（你：这设定真奇怪啊 。WGX大神：让你四处走还不把我的宝箱全开了）。
不管了开宝箱要紧。假设每个宝箱有一个数字V，如果是正数那么你获得V个金币，如果是负数，哈哈，不好意思，扣去相应个金币。（哭晕在厕所）。
那么问题来了：
那么问题来了：
如果你在已知宝箱的奖励的情况下，请选择一条路线，这条路线能让你获得最多的金币，当然所有走过的宝箱必须打开，不能说因为是负数你就选择不去打开它，并且出口（左上）和入口（右下）的那两个宝箱是必经点，也必须打开。
你的任务只是求出该路线获得的金币值就行。如下图，我们只要输出19就行。
你的任务只是求出该路线获得的金币值就行。如下图，我们只要输出19就行。
Input
第一行输入一个正整数T代表有T组数据，接下来有T组数据
对于每组数据，第一行输入两个正整数n 和m（n为行数m为列数）接下来是n行数据，每行数据有m个V，且V为整型，分别对应每个宝箱的获奖情况（-200<=V<=200）。
对于每组数据，第一行输入两个正整数n 和m（n为行数m为列数）接下来是n行数据，每行数据有m个V，且V为整型，分别对应每个宝箱的获奖情况（-200<=V<=200）。
Output
对于每组数据输出一个整数，代表所能获得的最大金币值。
SampleInput
2 4 4 1 2 -9 8 -5 5 7 3 10 1 1 2 6 5 8 -6 3 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
SampleOutput
19 7