You are given 2 arrays a and b, both of size n. You can swap two elements in b at most once (or leave it as it is), and you are required to minimize the value $$$∑_{i}|a_{i}-b_{i}|.$$$

Find the minimum possible value of this sum.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ {10^9}). 

The third line contains n integers b_1, b_2, …, b_n (1 ≤ b_i ≤ {10^9}).

Output

Output the minimum value of ∑_{i}|a_{i}-b_{i}|.

Examples

Input


5
5 4 3 2 1
1 2 3 4 5


Output


4

Input


2
1 3
4 2


Output


2

Note

In the first example, we can swap the first and fifth element in array b, so that it becomes [ 5, 2, 3, 4, 1 ].

Therefore, the minimum possible value of this sum would be |5-5| + |4-2| + |3-3| + |2-4| + |1-1| = 4.

In the second example, we can swap the first and second elements. So, our answer would be 2.
#include <algorithm>    // std::sort
#include <iostream>
#include <string>		// to_string
#include <vector>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int absVal(int a) {
	if (a < 0) {
		return -a;
	}
	else {
		return a;
	}
}

void solve() {
	int n;
	cin >> n;
	int* a = new int[n];
	int* b = new int[n];

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	unordered_set<int> x;
	unordered_set<int> y;
	for (int i = 0; i < n; i++) {
		if (a[i] < b[i]) {
			x.insert(i);
		} else if (a[i] > b[i]) {
			y.insert(i);
		}
	}
	// Remove things with the same first coordinate
	unordered_map<int, unordered_set<int>> combined;
	combined.clear();
	for (unordered_set<int>::iterator itr = x.begin(); itr != x.end(); itr++) {
		if (combined.find(a[*itr]) == combined.end()) {
			unordered_set<int> temp;
			combined.insert({ a[*itr], temp });
		}
		combined.find(a[*itr])->second.insert(*itr);
	}
	int max;
	int maxVal;
	for (unordered_map<int, unordered_set<int>>::iterator itr = combined.begin(); itr != combined.end(); itr++) {
		unordered_set<int> temp = itr->second;
		max = -1;
		maxVal = -1;
		for (unordered_set<int>::iterator itr2 = temp.begin(); itr2 != temp.end(); itr2++) {
			if (b[*itr2] > maxVal) {
				maxVal = b[*itr2];
				max = *itr2;
			}
		}
		for (unordered_set<int>::iterator itr2 = temp.begin(); itr2 != temp.end(); itr2++) {
			if (*itr2 != max) {;
				x.erase(*itr2);
			}
		}
	}
	combined.clear();
	for (unordered_set<int>::iterator itr = y.begin(); itr != y.end(); itr++) {
		if (combined.find(b[*itr]) == combined.end()) {
			unordered_set<int> temp;
			combined.insert({ b[*itr], temp });
		}
		combined.find(b[*itr])->second.insert(*itr);
	}
	for (unordered_map<int, unordered_set<int>>::iterator itr = combined.begin(); itr != combined.end(); itr++) {
		unordered_set<int> temp = itr->second;
		max = -1;
		maxVal = -1;
		for (unordered_set<int>::iterator itr2 = temp.begin(); itr2 != temp.end(); itr2++) {
			if (a[*itr2] > maxVal) {
				maxVal = a[*itr2];
				max = *itr2;
			}
		}
		for (unordered_set<int>::iterator itr2 = temp.begin(); itr2 != temp.end(); itr2++) {
			if (*itr2 != max) {
				y.erase(*itr2);
			}
		}
	}
	combined.clear();
	for (unordered_set<int>::iterator itr = x.begin(); itr != x.end(); itr++) {
		if (combined.find(b[*itr]) == combined.end()) {
			unordered_set<int> temp;
			combined.insert({ b[*itr], temp });
		}
		combined.find(b[*itr])->second.insert(*itr);
	}
	int min;
	int minVal;
	for (unordered_map<int, unordered_set<int>>::iterator itr = combined.begin(); itr != combined.end(); itr++) {
		unordered_set<int> temp = itr->second;
		min = -1;
		minVal = 1000000001;
		for (unordered_set<int>::iterator itr2 = temp.begin(); itr2 != temp.end(); itr2++) {
			if (a[*itr2] < minVal) {
				minVal = a[*itr2];
				min = *itr2;
			}
		}
		for (unordered_set<int>::iterator itr2 = temp.begin(); itr2 != temp.end(); itr2++) {
			if (*itr2 != min) {
				x.erase(*itr2);
			}
		}
	}
	combined.clear();
	for (unordered_set<int>::iterator itr = y.begin(); itr != y.end(); itr++) {
		if (combined.find(a[*itr]) == combined.end()) {
			unordered_set<int> temp;
			combined.insert({ a[*itr], temp });
		}
		combined.find(a[*itr])->second.insert(*itr);
	}
	for (unordered_map<int, unordered_set<int>>::iterator itr = combined.begin(); itr != combined.end(); itr++) {
		unordered_set<int> temp = itr->second;
		min = -1;
		minVal = 1000000001;
		for (unordered_set<int>::iterator itr2 = temp.begin(); itr2 != temp.end(); itr2++) {
			if (b[*itr2] < minVal) {
				minVal = b[*itr2];
				min = *itr2;
			}
		}
		for (unordered_set<int>::iterator itr2 = temp.begin(); itr2 != temp.end(); itr2++) {
			if (*itr2 != min) {
				y.erase(*itr2);
			}
		}
	}
	
	// Now get rid of things that encompass other things in each of X and Y
	map<int, int> sortA;
	map<int, int> sortB;
	for (unordered_set<int>::iterator itr = x.begin(); itr != x.end(); itr++) {
		sortA.insert({ a[*itr], *itr });
		sortB.insert({ b[*itr], *itr });
	}
	map<int, int>::iterator itrA = sortA.begin();
	map<int, int>::iterator itrB = sortB.begin();
	unordered_set<int> removed;
	while (itrA != sortA.end()) {
		if (removed.find(itrA->second) == removed.end()) {
			while (itrA->second != itrB->second) {
				// Remove the current thing in itrB, itrA, and X
				if (removed.find(itrB->second) == removed.end()) {
					int remove = itrB->second;
					removed.insert(remove);
					x.erase(remove);
				}
				itrB++;
			}
			itrB++;
		}
		itrA++;
	}
	sortA.clear();
	sortB.clear();
	for (unordered_set<int>::iterator itr = y.begin(); itr != y.end(); itr++) {
		sortA.insert({ a[*itr], *itr });
		sortB.insert({ b[*itr], *itr });
	}
	itrA = sortA.begin();
	itrB = sortB.begin();
	removed.clear();
	while (itrB != sortB.end()) {
		if (removed.find(itrB->second) == removed.end()) {
			while (itrB->second != itrA->second) {
				// Remove the current thing in itrB, itrA, and X
				if (removed.find(itrA->second) == removed.end()) {
					int remove = itrA->second;
					removed.insert(remove);
					y.erase(remove);
				}
				itrA++;
			}
			itrA++;
		}
		itrB++;
	}
	// make a sorted vector of indices
	map<int, int> sortX;
	map<int, int> sortY;
	for (unordered_set<int>::iterator itr = x.begin(); itr != x.end(); itr++) {
		sortX.insert({ a[*itr], *itr });
	}
	for (unordered_set<int>::iterator itr = y.begin(); itr != y.end(); itr++) {
		sortY.insert({ a[*itr], *itr });
	}
	vector<int> sortedX;
	vector<int> sortedY;
	for (map<int, int>::iterator itr = sortX.begin(); itr != sortX.end(); itr++) {
		sortedX.push_back(itr->second);
	}
	for (map<int, int>::iterator itr = sortY.begin(); itr != sortY.end(); itr++) {
		sortedY.push_back(itr->second);
	}
	int Xindex = 0;
	int Yindex = 0;
	// maximum intersection
	int maxCap = 0;
	if (sortedX.size() != 0 && sortedY.size() != 0) {
		while (true) {
			// calculate maxCap
			int XPos = sortedX.at(Xindex);
			int YPos = sortedY.at(Yindex);
			int lower = std::max(a[XPos], b[YPos]);
			int upper = std::min(b[XPos], a[YPos]);
			if (upper - lower > maxCap) {
				maxCap = upper - lower;
			}
			if (b[XPos] < a[YPos] || (b[XPos] == a[YPos] && a[XPos] > b[YPos])) {
				if (Xindex == sortedX.size() - 1) {
					break;
				}
				else {
					Xindex++;
				}
			}
			else {
				if (Yindex == sortedY.size() - 1) {
					break;
				}
				else {
					Yindex++;
				}
			}
		}
	}
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		sum += absVal(a[i] - b[i]);
	}
	sum -= 2 * (maxCap);
	cout << sum;

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
}


