/*
    题意：n行m列 n<=100 , m<=5000
              每一个位置有值T[i][j] , F[i][j]
              现要在每一行都找一个点来建站，其需要花费的时间为T[i][j]
              有一个要求：
               if we build a tower in cell (i,j) and another tower in cell (i+1,k), then we shall have |j-k|≤f(i,j)+f(i+1,k). 
   求最少时间
    
    dp[i,j] = min{dp[i+1,k]} +T[i,j]
   O(nm^2)是不行的
   |j-k| ≤ f(i,j)+f(i+1,k) 等价于
   j-f(i,j) <= k + f(i+1,k)  且 j+f(i,j) >= k - f(i+1,k)
   对于行i可先按照j+f(i,j)排序，然后检查每个j，把所有满足j+f(i,j) >= k - f(i+1,k)的k都加进去
   对这些k找出满足 j-f(i,j) <= k + f(i+1,k)的最小的dp[i+1,k]即可
   找最小，用线段树（需要离散化）
   对于一行，每个k只会加进去一次
   总的复杂度是O(nmlogm)
*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int INF = 1000000000;
const int MAX = 5000;

//#define G(i,x) ((x)-F[i][x])
//#define H(i,x) ((x)+F[i][x])

int T[100][5000],F[100][5000];
int dp[2][5000];
int G[5000] , H[5000] , index1[5000] ,  index2[5000];
int N , M;

bool cmpG(const int &a , const int &b)
{
    return G[a] < G[b];
}
bool cmpH(const int &a , const int &b)
{
    return H[a] < H[b];
}

int Min[MAX*4];

void insert(int p , int left , int right , int pos , int val)
{
    if(Min[p] > val)Min[p] = val;
    if(left == right)return;
    int mid = (left+right)>>1;
    if(pos <= mid)insert(2*p , left , mid , pos , val);
    else insert(2*p+1 , mid+1 , right , pos , val);
}

int query(int p , int left , int right , int l  , int r)
{
    if(l <= left && right <= r)return Min[p];
    int mid = (left+right)>>1;
    if(r <= mid)return query(2*p , left , mid , l , r);
    if( l > mid )return query(2*p+1 , mid+1 , right , l , r);
    return min(query(2*p , left , mid , l , mid) , query(2*p+1, mid+1 , right , mid+1 , r));
}

#define getPos(x) (lower_bound(compress,compress+num,(x))-compress) 

int main()
{
    while(scanf("%d%d",&N,&M),N||M)    
    {
        for(int i = 0 ; i < N ; i++)
            for(int j = 0 ; j < M ; j ++)
            {
                scanf("%d",&T[i][j]);
            }
        for(int i = 0 ; i < N ; i++)
            for(int j = 0 ; j < M ; j ++)
            {
                scanf("%d",&F[i][j]);
            }

        int pre = 0 , now = 1;
        for(int j = 0 ; j < M ;  j++)
        {
            dp[pre][j] = T[N-1][j];
        }
        for(int i = N - 2 ; i >= 0 ; i --)
        {
            for(int j = 0 ; j < M ; j ++)
            {
                H[j] = j + F[i][j];
                index1[j] = j;
            }
            sort(index1 , index1 + M , cmpH);

            for(int k = 0 ; k < M ; k ++)
            {
                G[k] = k - F[i+1][k];
                index2[k] = k;
            }
            sort(index2 , index2 + M , cmpG);
            
            //离散化
            static int compress[5000];
            for(int k = 0 ; k < M ; k ++)
                compress[k] = k + F[i+1][k];
            sort(compress,compress+M);
            int num = unique(compress , compress+M) - compress;

            fill(Min,Min+num*4 , INF);

            for(int jj = 0 , kk = 0; jj <M ; jj++)
            {
                int j = index1[jj] , k;    
                // j + F[i,j] >= k - F[i+1][k]
                while(kk < M && G[k=index2[kk]] <= H[j] )
                {
                    kk++;
                    insert(1 ,0 , num , getPos(k+F[i+1][k]) , dp[pre][k] );
                }
                //j-F[i,j] <= k+F[i+1,k]
                dp[now][j] = query(1 , 0 , num , getPos(max(0,j-F[i][j])) , num) + T[i][j];
            }
            swap(pre,now);
        }
        printf("%d\n",*min_element(dp[pre],dp[pre]+M));
    }
    return 0;
}