老师在求学期间，除了修炼魔法课，还开发了一种能创造虚拟的魔幻地图的技能。在不同的地图中，大家可以进行不同的闯关游戏，深受大家的喜爱。这天，经历了一整天疲惫的学习之后，魔幻之旅又开始了。

首先，老师将将游玩者移送至图中的出发点。地图可以看成是一个 N \times N 的网格。从上到下，从左到右，编号都为1...N。其中：

• 位于最左上角的网格 (1,1)，就是游玩者的出发点。
• 位于最右下角的网格 (N,N)，就是游玩者的结束点。

在魔幻地图中，游玩者会被赋予魔法能力，但是使用魔法需要消耗元气值。初始时，游玩者的元气值为 0。游玩者的目标是尽早地到达结束点。

游玩者在位置 (i,j) 时，每一秒，他都有三种选择：

• 停留在原地，则恢复元气值a_{i,j};
• 使用魔法，消耗b_{i,j} 元气值，则可以移动到(i,j+1);
• 使用魔法，消耗 c_{i,j} 元气值，则可以移动到(i+1,j);

老师还规定，任何时刻，在魔幻地图内游玩者的元气值不能低于 0。老师需要大家来帮忙计算出从出发点到结束点所需的最少时间，第一个计算出的同学可以优先进入魔幻地图体验。

第一行，一个整数 N。

接下来 N 行 N 列的数组，其中 a_{i,j} 表示在地图的 (i,j) 处每秒钟能恢复的元气值：

a_{1,1}, a_{1,2}...a_{1,N}

a_{2,1}, a_{2,2}...a_{2,N}

...

a_{N,1}, a_{N,2}...a_{N,N}

接下来 N 行 N-1 列的数组，其中 b_{i,j} 表示从 (i,j) 移动到 (i,j+1) 需要消耗的元气值：

b_{1,1}, b_{1,2}...b_{1,N-1}

b_{2,1}, b_{2,2}...b_{2,N-1}

...

b_{N,1}, b_{N,2}...b_{N,N-1}

接下来 N-1 行 N 列的数组，其中 c_{i,j} 表示从 (i,j) 移动到 (i+1,j) 需要消耗的元气值：

c_{1,1}, c_{1,2}...c_{1,N}

c_{2,1}, c_{2,2}...c_{2,N}

...

c_{N-1,1}, c_{N-1,2}...c_{N-1,N}

计算游玩者到达结束点所需的最少时间。

【样例 1 解释】

• 停留在(1,1)处1秒，当前元气值为1;

• 消耗1点元气值，移至(2,1), 当前总用时2秒，当前剩余元气值为0;

• 停留在(2,1)处3秒，当前总用时5秒，当前元气值为9;

• 消耗4点元气值，移至(2,2), 当前总用时6秒，当前剩余元气值为5;

• 消耗3点元气值，移至(3,2), 当前总用时7秒，当前剩余元气值为2;

• 消耗2点元气值，移至(3,3), 当前总用时8秒，当前剩余元气值为0;

可能存在其他的移动方案，但是可以证明用时 8 秒是最少需要的时间。

【数据范围】

对于 10\% 的数据，数组 a，数组 b，数组 c 的数值均相等。

对于 100\% 的数据，数组 a，数组 b，数组 c 的数值范围为：[1,10^9 ]。

对于 100\% 的数据，2≤N≤80。

市赛动态规划