Optimizing Bita-radish Cultivation Workload

Bitaro, an avid gardener for many years, is planning to cultivate a plant called Bita-radish starting this spring. He has prepared 2N seedlings of Bita-radish, numbered from 1 to 2N in the order of planting. The size of the i-th seedling is denoted by \(A_i\) (for \(1 \le i \le 2N\)). These sizes satisfy:

• \(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}\) and additionally \(A_{2N} \ge A_1\).

In particular, seedling 1 is the smallest and seedling \(N+1\) is the largest.

Bitaro also has N red flower pots and N blue flower pots. For \(1 \le j \le N\), the size of the \(j\)-th red pot is \(B_j\), and for \(1 \le k \le N\), the size of the \(k\)-th blue pot is \(C_k\). He will plant each of the 2N seedlings into one of these pots and arrange the pots in a row in the order of seedling 1, 2, …, 2N.

For aesthetic reasons, the arrangement of these 2N pots must be "beautiful." An arrangement is called beautiful if there exists an integer \(l\) with \(1 \le l \le N+1\) such that the pots (and hence the seedlings planted in them) in positions \(l, l+1, \ldots, l+N-1\) all have the same color.

When a seedling of size \(y\) is planted in a pot of size \(x\), the difficulty of that pairing is \(|x-y|\). The overall workload is defined as the maximum difficulty over all 2N pairs. Your task is to determine the minimum possible workload achievable by choosing an arrangement of the pots (and an assignment of pots to seedlings) that is beautiful.

inputFormat

The first line contains an integer \(N\).
The second line contains \(2N\) integers \(A_1, A_2, \ldots, A_{2N}\) representing the sizes of the seedlings.
The third line contains \(N\) integers \(B_1, B_2, \ldots, B_N\) representing the sizes of the red pots.
The fourth line contains \(N\) integers \(C_1, C_2, \ldots, C_N\) representing the sizes of the blue pots.

outputFormat

Output a single integer: the minimum possible maximum planting difficulty under a beautiful pot arrangement.

sample

1
1 2
1
2

0