A国正遭受敌人的袭击，敌国的军队已经到达Y城市。Y城市由N*M的方格组成。城市中所有的道路都是双向的，水平、垂直或者斜线方向的。在地图左上角是（0，0）点，右下角是（N，M）点。敌国军队现在到达（0，0）点，为了攻占A国，他们必须经过Y城市到达（N，M）点，下图是一个Y城市的交通图。

每一个黑色顶点代表城市中的主要建筑群，他们之间有道路相连。在这些道路上面的数值表示炸毁该条道路所需要的TNT（炸药）。。。A国的防御部队已经无法抵御敌军的正面进攻，他们能做的就是通过炸毁道路阻止敌军通过Y城市而到达A国首都。现在作为A国国防部长，你需要决定炸毁哪些街道，使得敌军无法从（0，0）点到达（N，M）点，并且使用尽可能少的炸药。

有多组测试数据。
第一行两个正数N，M，表示地图的高和宽
接下来N+1行，每行M个整数，依次对应该图中水平的道路
接下来N行，每行M+1个整数，依次对应图中垂直的道路
接下来2N行，每行2M个整数，依次对应图中斜线的道路。


数据有多组,以EOF结束.
数据范围：
30%的数据1 <= N, M <= 50
100%的数据：
1 <= N, M <= 500
1 <= amount <= 1,000,000

输出一个整数，表示断开（0，0）点和（N，M）点所需的最少TNT数量。