채소 재배는 즐거워 5

여러 해 동안 원예를 즐겨 온 비타로는 올봄부터 비타라디시라는 식물을 키울 계획이다. 비타로는 1번부터 2N번까지 번호가 붙은 비타라디시 묘목 2N개를 준비했다. 그는 이 번호 순서대로 묘목을 늘어놓고 재배하려고 한다. 묘목 $i$($1 \le i \le 2N$)의 크기는 $A_i$이다. 모든 묘목이 충분한 햇빛을 받도록 묘목의 크기는 다음 조건을 만족해야 한다.

$A_1 \le A_2 \le \cdots \le A_N \le A_{N+1}$

$A_{N+1} \ge A_{N+2} \ge \cdots \ge A_{2N-1} \ge A_{2N} \ge A_1$

묘목 1번이 가장 작고 묘목 $N+1$번이 가장 크다.

비타로에게는 빨간 화분 $N$개와 파란 화분 $N$개가 있으며, 각 화분에는 정해진 크기가 있다. $j$번째 빨간 화분($1 \le j \le N$)의 크기는 $B_j$이고, $k$번째 파란 화분($1 \le k \le N$)의 크기는 $C_k$이다. 비타로는 2N개의 화분에 묘목을 하나씩 심고, 묘목 $1, 2, \dots, 2N$이 이 순서대로 놓이도록 화분을 일렬로 배치한다.

화분은 아름다운 순서로 배치되어야 한다. $1 \le l \le N+1$을 만족하는 정수 $l$이 존재하여, 묘목 $l, l+1, \dots, l+N-1$이 심긴 화분의 색이 모두 같으면 아름다운 순서이다.

크기 $x$인 화분에 크기 $y$인 묘목을 심으면 그 쌍의 어려움은 $|x-y|$이다. 비타로의 작업량은 2N개 쌍의 어려움 가운데 최댓값이다. 화분이 아름다운 순서가 되도록 묘목을 심을 때, 작업량의 최솟값을 구하라.

입력은 표준 입력으로 다음 형식으로 주어진다.

N
A_1 A_2 ... A_{2N}
B_1 B_2 ... B_N
C_1 C_2 ... C_N

화분을 아름다운 순서로 배치할 때의 작업량 최솟값을 한 줄에 출력한다.

• $1 \le N \le 300\,000$
• $1 \le A_i \le 10^9$ ($1 \le i \le 2N$)
• $1 \le B_j \le 10^9$ ($1 \le j \le N$)
• $1 \le C_k \le 10^9$ ($1 \le k \le N$)
• $A_1 \le A_2 \le \cdots \le A_N \le A_{N+1}$
• $A_{N+1} \ge A_{N+2} \ge \cdots \ge A_{2N-1} \ge A_{2N} \ge A_1$
• 모든 입력값은 정수이다.
• 시간 제한은 5000 ms, 메모리 제한은 1024 MB이다.