UOJ Logo Zijian Online Judge

ZOJ

#16. 最佳组合

统计

Bzeroth大陆最终还是覆灭了,所以你需要为地灾军团服务了。

地灾军团军师黑袍不擅长写题面,所以你只需要看简化版的题意即可。

给定 $3$ 个长度均为 $N$ 的正整数序列 $A$、$B$、$C$,要求从三个序列中分别取出 $1$ 个数 $A_i$、$B_j$、$C_k$,使得 $|A_i - B_j|+|A_i - C_k|+|B_j - C_k|$ 最小。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数,第 $i$ 个数为 $A_i$。

第三行 $N$ 个正整数,第 $i$ 个数为 $B_i$。

第四行 $N$ 个正整数,第 $i$ 个数为 $C_i$。

输出格式

输出 $|A_i - B_j|+|A_i - C_k|+|B_j - C_k|$ 的最小值。

样例

input

3 
170 180 190  
195 185 175  
180 160 200

output

10

explanation

选择 $A_2$、$B_2$、$C_1$ 或 $A_2$、$B_3$、$C_1$ 。

限制与约定

测试数据编号$N$
1$=10$
2$=20$
3$=50$
4$=100$
5$=200$
6$=501$
7$=2501$
8$=5010$
9$=52501$
10$=152501$

对于 $100\texttt{%}$ 的数据:$1 \leq A_i、B_i、C_i \leq 10^9$。

时间限制:$1\texttt{s}$

空间限制:$128\texttt{MB}$