#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    set<pair<int, int>> st;
    multiset<int> mst;
    for (int i = 0; i < w; i++) {
        st.emplace(i, i);
        mst.emplace(0);
    }
    st.emplace(w, w);
    int inf = 1e9;
    mst.emplace(inf);
    for (int i = 0; i < h; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        vector<pair<int, int>> v;
        int c = -1;
        for (auto it = st.lower_bound({a, -1}); it != st.end(); it++) {
            pair<int, int> p = *it;
            if (a <= p.first && p.first <= b) {
                c = max(c, p.second);
                v.emplace_back(p);
            } else {
                break;
            }
        }
        for (auto p : v) {
            st.erase(p);
            mst.erase(mst.find((p.first == w ? inf : p.first - p.second)));
        }
        if (c != -1) {
            st.emplace(b, c);
            if (b == w) {
                b = inf;
                c = 0;
            }
            mst.emplace(b - c);
        }
        int res = *mst.begin();
        if (res >= 1e8) {
            cout << -1 << '\n';
        } else {
            cout << res + i + 1 << '\n';
        }
    }
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

int H, W;
bitset<160 * 160 + 1> dp[81][81];
int cost[81][81];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> H >> W;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> cost[i][j];
        }
    }
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            int tmp;
            cin >> tmp;
            cost[i][j] -= tmp;
        }
    }

    int s = H + W - 1;
    dp[0][0][80 + cost[0][0]] = true;
    dp[0][0][80 - cost[0][0]] = true;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            dp[i + 1][j] |= dp[i][j] << (80 + cost[i + 1][j]);
            dp[i + 1][j] |= dp[i][j] << (80 - cost[i + 1][j]);
            dp[i][j + 1] |= dp[i][j] << (80 + cost[i][j + 1]);
            dp[i][j + 1] |= dp[i][j] << (80 - cost[i][j + 1]);
        }
    }

    int ans = inf;
    for(int i = 0; i <= s * 160; i++){
        if(!dp[H - 1][W - 1][i]) continue;
        chmin(ans, abs(i - s * 80));
    }
    cout << ans << endl;
    return 0;
}