#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0};

int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin>>T; while(T--){ int n,m; cin>>n>>m; vector<vector> t(n,vector(m)); for(int i=0;i<n;++i){ for(int j=0;j<m;++j){ cin>>t[i][j]; } } vector<vector> d(n,vector(m)); for(int i=0;i<n;++i){ for(int j=0;j<m;++j){ cin>>d[i][j]; } } vector<vector<vector>>dp(n,vector<vector>(m,vector(4,INF))); priority_queue<pair<ll,pair<pair<int,int>,int>>,vector<pair<ll,pair<pair<int,int>,int>>>,greater<pair<ll,pair<pair<int,int>,int>>>>pq; dp[0][0][0]=t[0][0]; pq.push({dp[0][0][0],{{0,0},0}}); dp[0][0][1]=t[0][0]+d[0][0]; pq.push({dp[0][0][1],{{0,0},1}}); while(!pq.empty()){ auto top=pq.top(); pq.pop(); ll cost=top.first; int i=top.second.first.first; int j=top.second.first.second; int dir=top.second.second; if(cost>dp[i][j][dir]){ continue; } int ni=i+dx[dir]; int nj=j+dy[dir]; if(ni>=0&&ni<n&&nj>=0&&nj<m){ for(int ndir=0;ndir<4;++ndir){ ll new_cost=cost+t[ni][nj]; if(dir!=ndir){ new_cost+=d[ni][nj]; } if(new_cost<dp[ni][nj][ndir]){ dp[ni][nj][ndir]=new_cost; pq.push({new_cost,{{ni, nj},ndir}}); } } } } cout<<dp[n-1][m-1][1]<<'\n'; } return 0; }