#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#define N_ 250100
using namespace std;

int n, Nxt[N_], R1[N_], L1[N_], R2[N_];
struct point {
	long long x, y;
}P[N_];
long long S[N_], w[N_], Deq[N_][2];
long long Dis(point a, point b) {
	return abs(a.x - b.x) + abs(a.y - b.y);
}

long long Dis2(int a, int b) {
	return S[b - 1] - S[a - 1];
}

bool Pos(long long L) {
	int i, pv = 1;
	for (i = 1; i <= n; i++) {
		while (pv <= n && Dis2(i, pv) <= L)pv++;
		Nxt[i] = pv;
	}

	if (Nxt[1] == n + 1)return true;
	int t1 = Nxt[1];
	for (i = t1; i <= n; i++)R1[i] = i - 1;
	pv = t1;
	for (i = t1 - 1; i >= 1; i--) {
		while (pv <= n && Dis2(t1, pv) + Dis(P[i], P[pv]) + Dis2(1, i) <= L) pv++;
		R1[i] = pv - 1;
	}
	for (i = n; i >= 1; i--)if (Dis2(i, n) > L)break;
	t1 = i;
	for (i = 1; i <= t1; i++)L1[i] = i + 1;
	pv = t1;
	for (i = t1 + 1; i <= n; i++) {
		while (pv >= 1 && Dis2(pv, t1) + Dis(P[pv], P[i]) + Dis2(i, n) <= L)pv--;
		L1[i] = pv + 1;
	}


	pv = 1;

	int pp = 1;

	int head = 1, tail = 0;
	for (i = 1; i <= n; i++) {
		if (pv < i)pv = i;
		while (pv <= n) {
			if (head <= tail && Dis2(i, pv) + Dis(P[i], P[pv]) - Deq[head][0] > L)break;
			pv++;
			if (pv > n)break;
			while (pp <= n && Nxt[pp] <= pv) {
				long long t = Dis2(pp, Nxt[pp]);
				while (head <= tail && Deq[tail][0] >= t)tail--;
				tail++;
				Deq[tail][0] = t, Deq[tail][1] = pp;
				pp++;
			}
		}
		R1[i] = min(R1[i], pv - 1);
		if (head <= tail && Deq[head][1] == i)head++;
	}
	pv = 1;
	for (i = 1; i <= n; i++) {
		R2[i] = i;
		if (pv < i)pv = i;
		while (pv <= n && Dis2(1, i) + Dis(P[i], P[pv]) + Dis2(pv, n) > L)pv++;
		R2[i] = max(R2[i], pv);
	}
	for (i = 1; i <= n; i++) {
		if (R2[i] <= R1[i]) {
			if (L1[R1[i]] <= i) {
				return true;
			}
		}
	}
	return false;
}

long long shortcut(int N, std::vector<long long> X, std::vector<long long> Y) {
	n = N;
	int i;
	for (i = 0; i < n; i++) {
		P[i + 1] = { X[i],Y[i] };
	}
	for (i = 1; i < n; i++) {
		w[i] = Dis(P[i], P[i + 1]);
		S[i] = S[i - 1] + w[i];
	}
	long long bb = 0, ee = S[n - 1], mid, res = S[n - 1];
	while (bb <= ee) {
		mid = (bb + ee) >> 1;
		if (Pos(mid)) {
			res = mid;
			ee = mid - 1;
		}
		else bb = mid + 1;
	}
	return res;
}