### 问题描述 小蓝被困在一个神奇的迷宫中：这是一个由 $0$ 和 $1$ 组成的迷宫，其中 $0$ 表示空地，$1$ 表示障碍物。 小蓝需要从迷宫左上角走到右下角的传送阵，只能往右或往下走，每到达一个位置会得到若干个金币。当他最终到达传送阵所在位置时，他获得的金币总数要为奇数才能开启传送阵离开，否则该路线不可行。 现在给出一个 $n\times n$ 的迷宫，小蓝初始位置在 $(1,1)$ 处，传送阵在 $(n,n)$ 处，每一个位置有若干个金币，其中位置为 $(i,j)$ 的位置金币数量为 $V_{i,j}$ ，请你告诉他所能获得的最大金币总数是多少。 ### 输入格式 输入第一行，包含一个整数 $n$ ，为迷宫边长。 接下来 $n$ 行，每行输入 $n$ 个整数，表示该迷宫，第 $i$ 行第 $j$ 个数字表示迷宫第 $i$ 行，第 $j$ 列的位置， $0$ 表示空地，$1$ 表示障碍物。 再接下来 $n$ 行，每行输入 $n$ 个整数，第 $i$ 行第 $j$ 个数字表示迷宫第 $i$ 行，第 $j$ 列的位置的金币数量 $V_{i,j}$ 。 ### 输出格式 输出一个整数。小蓝如果可以成功走出迷宫：输出他可以得到的最大金币总数；如果不存在一条路线到达传送阵或金币总数始终不为奇数，则输出 $-1$ 。 ### 样例输入 ```text 2 0 0 0 0 0 2 5 1 ``` ### 样例输出 ```text 3 ``` ### 说明 在样例中，最佳路径为 $(1,1) \rightarrow (1,2) \rightarrow (2,2)$ ，最后获得 $3$ 个金币。 ### 评测数据规模 对于 $30$ %的评测数据，$0\leq n\leq100$。 对于 $60$ %的评测数据，$0\leq n\leq500$ ，$0\leq V_{i,j}\leq 10^6$ 。 对于 $100$ %的评测数据，$0\leq n\leq1000$ ，$0\leq V_{i,j}\leq 10^6$ 。