Migrated from Lutece 604 吴神的魔法冒险

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

吴神,是神,也是魔法伪娘,啊不,魔法少年.

吴神为各地人民行侠仗义,惩奸除恶，即使是月世界的魔法使也难以与之匹敌，金钱和名誉和loli他均不感兴趣，他只是一心修炼自己的魔法，坚持着属于自己的正义。

但是,一个人的力量是不能拯救世界的,即使这个人是吴神.吴神的行为使吴神成为了米迦逻的头号敌人.在绝望平原上,吴神正面对着数不尽的触手怪.吴神知道,自己是不可能完全消灭这么多长着⑨只触手的触手怪的.吴神果断选择逃跑,触手怪们当然不会让吴神就这样跑掉的,它们用魔法在吴神身后建造了$n$层魔法墙,由于触手怪们的实力参差不齐,每段墙的厚度是非均匀的.吴神很快便看出了破绽,即:如果把每一层墙看成$m$段,那么可以计算出破坏掉这段墙所需的时间$T(i,j)$.但是，就算破坏掉一段墙之后，吴神想走到下一层墙也需要满足一个条件：比如吴神想从第$i$层的第$j$段墙走到第$i+1$层的第$k$段墙，必须满足$|j-k|\leq D(i,j)+D(i+1,k)$.从一层移动到另一层的时间可以忽略不计，并且吴神只能一层一层的移动。

现在触手怪正在向吴神奔来,为了不被抓住,吴神需要尽快穿过这$n$层魔法墙.

Input

第一行为$T$,数据组数

每组数据第一行为$n,m$.魔法墙的层数和每层的段数.

接下来$n$行,每行$m$个数,第$i$行的第$j$个元素表示破坏这段墙所需的时间$T(i,j)$

接下来$n$行,每行$m$个数,第$i$行的第$j$个元素表示这段墙的魔法特征值$D(i,j)$

$2\leq N\leq 100$, $1\leq M\leq 5000$

$0\leq T,D\leq 100000$

Output

每组数据一行答案,输出吴神穿过魔法墙所需的最少时间.

Samples

1
3 5 
2 5 3 5 7 
3 2 4 4 8 
2 6 7 8 2 
0 1 0 1 2 
1 0 2 1 1 
0 2 1 0 2

7

Resources

UESTC Training for Dynamic Programming