### 问题描述 小蓝很喜欢走迷宫，是因为迷宫里有宝物。 现在他来到一个 $n\times n$ 的迷宫，该迷宫只能向下或者向左走，初始位置在 $(1,1)$ 处，每一个格子有一些宝物，其中位置为 $(i,j)$ 的格子宝物数量为 $V_{i,j}$ ，如果该位置为墙则 $V_{i,j} =-1$ 。 他最近学会了一个技能： $1.$ 把下一个格子宝物数量乘以 $ave$ ，$ave$ 等于已经走过格子宝物和 $S$ ，除以已经走过的房间数 $m$（向下取整），在初始点 $ave=0$ 。 即以如下公式改变 $V_{i,j}$ ： $$ V_{i,j} = V_{i,j} \times \lfloor \dfrac{S}{M} \rfloor $$ 但是他只能使用一次这个技能。 现在给定一个迷宫，请你告诉他所能获得的最大价值是多少，题目保证有路径到达终点 $(n,n)$ 。 ### 输入格式 输入第一行，包含一个整数 $n$ ，为迷宫边长。 接下来 $n$ 行，每行输入 $n$ 个整数，第 $i$ 行第 $j$ 个数字为迷宫第 $i$ 行，第 $j$ 列位置宝物 $V_{i,j}$ ，如果该位置为墙则 $V_{i,j}=-1$ 。 ### 输出格式 输出仅一行，包含一个整数，表示答案。 ### 样例输入 ```text 4 1 4 4 4 1 1 4 1 2 1 1 1 1 5 1 3 ``` ### 样例输出 ```text 26 ``` ### 说明 在样例中，最佳路径为 $(1,1)$ ，$(1,2)$ ，$(1,3)$ ，$(2,3)$ ，$(3,3)$ ，$(4,3)$ ，$(4,4)$ ，并且在 $(2,3)$ 释放技能。 $$ s=1+4+4+4 \times \lfloor \dfrac{(1+4+4)}{3} \rfloor+1+1+3=26 $$ ### 评测数据规模 对于 $30\%$ 的评测数据，$0\leq n\leq100$ ，$V_{i,j} \neq -1$ 。 对于 $50\%$ 的评测数据，$0\leq n\leq200$ ，$V_{i,j} \neq -1$ 。 对于 $80\%$ 的评测数据，$0\leq n\leq500$ ，$-1\leq V_{i,j}\leq 10^6$ 。 对于 $100\%$ 的评测数据，$0\leq n\leq1000$ ，$-1\leq V_{i,j}\leq 10^6$ 。