2420: Swimming Duck

pcf最近沉迷于一款名为Swimming Duck的游戏。在游戏中，主角GreenDuck在一块n*n大小的正方形湖面上迷路了，玩家得帮助GreenDuck从 左上角出发，抵达右下角的目的地。在湖面上有一些味道鲜美的鱼，GreenDuck在回家时会不自觉地收集这些鱼儿。同时湖中也有阻挡道路的石头，GreenDuck不能越过它们。
pcf认为这些鱼有各自的价值，因此他想让GreenDuck最大化收集到的鱼的价值。庆幸的是，这款游戏仅仅是普及组的OIER设计的，所以GreenDuck只能向右或向下移动一格，也不能走斜线。
同时，为了向好朋友baobao证明自己没有开挂，他还要找出GreenDuck的移动路线。若GreenDuck有多条路线能得到最优解，那他会优先选择向下走。

第一行一个整数n，表示湖的大小为n*n。(n≤100)
接下来n行，每行一个整数ai，描述了湖面上鱼的价值。特别地，若ai为-1，表示这是一块石头。

4
1 2 2 1
-1 1 -1 1
-1 1 -1 1
-1 1 1 1

9
* * * *
- - - *
- - - *
- - - *

【输入样例2】
3
1 1 1
1 1 1
1 1 1
【输出样例2】
5
* - -
* - -
* * *
【解题提示】
强行二维dp.......