fastfood.cpp

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define pb push_back
#define fr first
#define sc second
#define mp make_pair
//#define int long long

const int maxn = 3e5+10;

int n;
pair<int,int> pt[maxn];

int val(int i, int mask) {
    int sum = 0;

    if(mask&1) sum+= pt[i].fr;
    else sum-= pt[i].fr;
    if(mask&2) sum+= pt[i].sc;
    else sum-= pt[i].sc;

    return sum;
}

int p[3][4], mygrp[maxn];
vector<pair<int,int>> listmsk[4];

pair<int,int> maxdist(int i, int j) {
    if(p[i][0] == -1 or p[j][0] == -1) return mp(-1,-1);
    pair<int,int> mx = mp(-1,-1);

    for(int msk = 0; msk < 4; msk++) {
        if(msk == 0) mx = mp(listmsk[msk][p[i][msk]].fr+listmsk[3-msk][p[j][3-msk]].fr,listmsk[3-msk][p[j][3-msk]].sc);
        else mx = max(mx, mp(listmsk[msk][p[i][msk]].fr+listmsk[3-msk][p[j][3-msk]].fr,listmsk[3-msk][p[j][3-msk]].sc));
    }
    return mx;
}

bool check(int d) {

    for(int i = 1; i <= n; i++) {
        mygrp[i] = 0;
    }

    for(int msk = 0; msk < 4; msk++) {
        p[0][msk] = n-1;
        p[1][msk] = -1;
        p[2][msk] = -1;
    }


    while(p[0][0] != -1) {
        auto mx1 = maxdist(1,0);
        if(mx1.sc != -1 and mx1.fr > d) {
            int id = mx1.sc;

            if(p[2][0] != -1) {
                for(int msk = 0; msk < 4; msk++) {
                    if(val(id,msk)+listmsk[3-msk][p[2][3-msk]].fr > d) {
                        return false;
                    }
                }
            }

            mygrp[id] = 2;
            for(int msk = 0; msk < 4; msk++) {
                while(p[0][msk] != -1 && mygrp[listmsk[msk][p[0][msk]].sc] != 0) p[0][msk]--;

                if(p[2][msk] == -1 or val(id,msk) > listmsk[msk][p[2][msk]].fr) {
                    while(p[2][msk] == -1 or listmsk[msk][p[2][msk]].sc != id) p[2][msk]++;
                }
            }
            continue;
        }
        auto mx2 = maxdist(2,0);
        if(mx2.sc != -1 and mx2.fr > d) {
            int id = mx2.sc;

            if(p[1][0] != -1) {
                for(int msk = 0; msk < 4; msk++) {
                    if(val(id,msk)+listmsk[3-msk][p[1][3-msk]].fr > d) {
                        return false;
                    }
                }
            }

            mygrp[id] = 1;
            for(int msk = 0; msk < 4; msk++) {
                while(p[0][msk] != -1 && mygrp[listmsk[msk][p[0][msk]].sc] != 0) p[0][msk]--;

                if(p[1][msk] == -1 or val(id,msk) > listmsk[msk][p[1][msk]].fr) {
                    while(p[1][msk] == -1 or listmsk[msk][p[1][msk]].sc != id) p[1][msk]++;
                }
            }
            continue;
        }

        int id = listmsk[0][p[0][0]].sc;
        mygrp[id] = 1;
        for(int msk = 0; msk < 4; msk++) {
            while(p[0][msk] != -1 && mygrp[listmsk[msk][p[0][msk]].sc] != 0) p[0][msk]--;

            if(p[1][msk] == -1 or val(id,msk) > listmsk[msk][p[1][msk]].fr) {
                while(p[1][msk] == -1 or listmsk[msk][p[1][msk]].sc != id) p[1][msk]++;
            }
        }
    }

    return true;
}



void solve() {
    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> pt[i].fr;
    }
    for(int i = 1; i <= n; i++) {
        cin >> pt[i].sc;
    }

    for(int i = 1; i <= n; i++) {
        for(int msk = 0; msk < 4; msk++) {
            listmsk[msk].pb(mp(val(i,msk),i));
        }
    }

    for(int msk = 0; msk < 4; msk++) {
        sort(all(listmsk[msk]));
    }

    int l = 0;
    int r = (int) 1e9;
    int ans = -1;

    while(l <= r) {
        int mid = (l+r)/2;

        if(check(mid)) {
            ans = mid;
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }

    cout << ans << endl;

}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    // freopen("in.in","r",stdin);

    solve();
}