题目描述

有一对大盗获得了 $n$ 个宝物，$2$ 人准备进行分赃。

随着行情的波动，每个宝物的价格不是固定的，会有一个范围，即第 $i$ 个宝物的价值在 $[l_i, r_i]$ 之间。

为了公平起见，他们想要分出的两组宝物的最大价值差要尽可能地小。如两组分别为 $A,B$，该两组各自的最低和最高价格和为 $L(A/B), H(A/B)$，所求则为最小化 $max(|H(A)-L(B)|,|H(B)-L(A)|)$

输入格式

第一行，一个正整数 $n$，表示宝物数量

第二行 $n$ 个正整数 $l_i$，表示每个宝物的最低价值

第三行 $n$ 个正整数 $r_i$，表示每个宝物的最高价值

输出格式

一个整数，表示题目所求最后分赃的两组最小差距

输入输出样例

4
3 4 4 7
3 4 4 7

2

样例 $\tt \#1$说明

• 将 $1,4$ 号分为一组， $2,3$ 号分为一组，此时两组差距最小为 $(3+7)-(4+4)=2$

5
1 3 5 4 5
2 5 6 8 7

5

样例 $\tt \#2$说明

• 将 $3,4$ 号分为一组， $1,2,5$ 号分为一组，此时两组差距最小为 $(6+8)-(1+3+5)=5$

32
2907 949 1674 6092 8608 5186 2630 970 1050 2415 1923 2697 5571 6941 8065 4710 716 756 5185 1341 993 5092 248 1895 4223 1783 3844 3531 2431 1755 2837 4015
7296 6954 4407 9724 8645 8065 9323 8433 1352 9618 6487 7309 9297 8999 9960 5653 4721 7623 6017 7320 3513 6642 6359 3145 7233 5077 6457 3605 2911 4679 5381 6574

52873

数据范围

• 对于 $30\%$ 的数据，$n\le 10$
• 对于 $100\%$ 的数据，$2\le n\le50, 1\le l_i\le r_i\le 10000$