/*
// Sample code to perform I/O:

cin >> name;                            // Reading input from STDIN
cout << "Hi, " << name << ".\n";        // Writing output to STDOUT

// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
*/

// Write your code here
#include<bits/stdc++.h>
#define ll  long long
#define rep(i,a,b)  for(int i = a; i < b; i++)
using namespace std;

ll dp[105][10005][2];
bool vis[105][10005][2];
ll n,m,l;
pair<ll,ll> v[105][10005];

ll lowerBound(ll i,ll num) {
    ll mid, l = 0, r = m - 1;
    while(l <= r) {
        mid = (l + r) / 2;
        if(v[i][mid].first < num) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return r + 1;
}

ll fun(ll i,ll j,ll dir) {
    if(j < 0 || j >= m) {
        return -5000000000000;
    }
    ll& ans = dp[i][j][dir];
    if(vis[i][j][dir]) {
        return ans;
    }
    vis[i][j][dir] = 1;
    ans = -LLONG_MAX;
    if(i == n - 1) {
        if(dir == 0) {
            if(j != m - 1) {
                ans = max(ans, fun(i, j + 1, 0) - (v[i][j + 1].first - v[i][j].first));
            }
            if( j != 0) {
                ans = max(ans, fun(i, j - 1, 1) - (v[i][j].first - v[i][j - 1].first));
            }
            ans = max(ans, v[i][j].second - abs(v[i][j].first - l));
        } else {
            if( j != 0) {
                ans = max(ans, fun(i, j - 1, 1) - (v[i][j].first - v[i][j - 1].first));
            }
            ans = max(ans, v[i][j].second - abs(v[i][j].first - l));
        }
        return ans;
    }
    ll ps;
    ps = (lowerBound(i + 1, v[i][j].first));
    if(dir == 0) {
        if(j != m - 1)
            ans = max(ans, fun(i, j + 1, 0) - (v[i][j + 1].first - v[i][j].first));
        if(j != 0)
            ans = max(ans, fun(i, j - 1, 1) - (v[i][j].first - v[i][j - 1].first));
        if(ps <= m - 1)
            ans = max(ans, fun(i + 1, ps, 0) - abs(v[i][j].first - v[i + 1][ps].first) + v[i][j].second);
        if(ps != 0)
            ans = max(ans, fun(i + 1, ps - 1, 1) - abs(v[i][j].first - v[i + 1][ps - 1].first) + v[i][j].second);
    } else {
        if(j != 0)
            ans = max(ans, fun(i, j - 1, 1) - (v[i][j].first - v[i][j - 1].first));
        if(ps <= m - 1)
            ans = max(ans, fun(i + 1, ps, 0) - abs(v[i][j].first - v[i + 1][ps].first) + v[i][j].second);
        if(ps != 0)
            ans = max(ans, fun(i + 1, ps - 1, 1) - abs(v[i][j].first - v[i + 1][ps - 1].first) + v[i][j].second);
    }
    return ans;
}

void solve() {
    cin >> n;
    rep(i,0,n) {
        rep(j,0,m) {
            cin >> v[i][j].first;
        }
    }
    rep(i,0,n) {
        rep(j,0,m) {
            cin >> v[i][j].second;
        }
    }
    rep(i,0,n) {
        sort(v[i], v[i] + m);
    }
    rep(i,0,n + 1) {
        rep(j,0,m + 1) {
            rep(k, 0, 2) {
                vis[i][j][k] = 0;
            }
        }
    }
    cout << fun(0,0,0) - v[0][0].first << endl;
}

int main() {
    ll TESTS = 1;
    cin >> TESTS;
    while(TESTS--) {
        solve();
    }
    return 0;
}