Repovive

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

Rayan and Sarah each hike along a trail. Each trail has $N$ checkpoints numbered $1$ to $N$ . The starting point (checkpoint $0$ ) is at altitude $0$ for both trails.

Rayan's trail has altitudes $p_1, p_2, \ldots, p_N$ at each checkpoint. Sarah's trail has altitudes $q_1, q_2, \ldots, q_N$ .

The slope of a segment from checkpoint $i$ to checkpoint $j$ is: $s(i, j) = \frac{a_j - a_i}{j - i}$

They want to divide their trails into the same number of segments $k$ (but they can use different breakpoints):

Rayan's segments: $0 = u_0 < u_1 < \ldots < u_k = N$
Sarah's segments: $0 = v_0 < v_1 < \ldots < v_k = N$

For each segment pair $m$ (from $1$ to $k$ ), the following must hold: $s(P, u_{m-1}, u_m) + X \le s(Q, v_{m-1}, v_m)$

Find the maximum value of $X$ for which a valid partition exists.

Constraints

$1 \le t \le 10$
$1 \le N \le 400$
$-10^9 \le p_i, q_i \le 10^9$
The sum of $N$ over all test cases does not exceed $500$ .

Rayan and Sarah each hike along a trail. Each trail has $N$ checkpoints numbered $1$ to $N$ . The starting point (checkpoint $0$ ) is at altitude $0$ for both trails.

Rayan's trail has altitudes $p_1, p_2, \ldots, p_N$ at each checkpoint. Sarah's trail has altitudes $q_1, q_2, \ldots, q_N$ .

The slope of a segment from checkpoint $i$ to checkpoint $j$ is: $s(i, j) = \frac{a_j - a_i}{j - i}$

They want to divide their trails into the same number of segments $k$ (but they can use different breakpoints):

Rayan's segments: $0 = u_0 < u_1 < \ldots < u_k = N$
Sarah's segments: $0 = v_0 < v_1 < \ldots < v_k = N$

For each segment pair $m$ (from $1$ to $k$ ), the following must hold: $s(P, u_{m-1}, u_m) + X \le s(Q, v_{m-1}, v_m)$

Find the maximum value of $X$ for which a valid partition exists.

Constraints

$1 \le t \le 10$
$1 \le N \le 400$
$-10^9 \le p_i, q_i \le 10^9$
The sum of $N$ over all test cases does not exceed $500$ .

1E. Two Paths

Constraints

Input

Output

Samples

Constraints