You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

潜入

题目描述

给定一个 $R\times C$ 的矩阵，左上角为 $(1,1)$，右下角为 $(R,C)$。若你位于 $(i,j)$，你每次可以进行如下方式的移动：

• 移动到 $(i,j+1)$，花费为 $A_{i,j}$。需要保证 $j<C$。
• 移动到 $(i,j-1)$，花费为 $A_{i,j-1}$。需要保证 $j\ge 2$。
• 移动到 $(i+1,j)$，花费为 $B_{i,j}$。需要保证 $i<R$。
• 选择一个整数 $k$ 满足 $1\le k<i$，移动到 $(i-k,j)$，花费为 $(1+k)$。

求从 $(1,1)$ 移动到 $(R,C)$ 的最小花费。

输入格式

输入格式如下。第一行两个整数 $R,C$，接下来 $R$ 行，每行 $C-1$ 个数表示矩阵 $A$，再接下来 $R-1$ 行，每行 $C$ 个数表示矩阵 $B$。

$R$ $C$ $A_{1,1}$ $\cdots$ $A_{1,C-1}$ $\vdots$ $A_{R,1}$ $\cdots$ $A_{R,C-1}$ $B_{1,1}$ $\cdots$ $B_{1,C}$ $\vdots$ $B_{R-1,1}$ $\cdots$ $B_{R-1,C}$

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

3 3
10 1
10 10
1 10
1 10 1
1 10 1

样例输出 #1

9

数据范围

• $2\ <\ =\ R,\ C\ <\ =\ 500$
• $0\ <\ =\ A_{i,j}\ <\ 10^3$
• $0\ <\ =\ B_{i,j}\ <\ 10^3$

Sample Explanation 1

路线如下：

• $(1,\ 1)$ → $(2,\ 1)$ ，代价 $1$ 。
• $(2,\ 1)$ → $(3,\ 1)$ ，代价 $1$ 。
• $(3,\ 1)$ → $(3,\ 2)$ ，代价 $1$ 。
• $(3,\ 2)$ → $(1,\ 2)$ ，代价 $3$ 。
• $(1,\ 2)$ → $(1,\ 3)$ ，代价 $1$ 。
• $(1,\ 3)$ → $(2,\ 3)$ ，代价 $1$ 。
• $(2,\ 3)$ → $(3,\ 3)$ ，代价 $1$ 。