牛的舞技非常差。不过 Farmer John 发现,优雅的牛往往产更多奶,因此给全牛群报了交谊舞课。第一次上课,要把 $N$ 头公牛($1\le N\le1{,}000$)和 $N$ 头母牛配成舞伴。身高相近,即身高差较小的牛是好搭档。给定所有牛的身高,找出使所有舞伴身高差之和最小的配对。
输入格式
- 第 1 行:整数 $N$。
- 第 $2..N+1$ 行:每行一个整数,表示一头公牛身高。
- 第 $N+2..2N+1$ 行:每行一个整数,表示一头母牛身高。
输出格式
- 第 1 行:一个整数,最优配对的身高差之和。
样例
输入格式 1
4
2
8
5
5
1
4
10
7
输出格式 1
6
说明
输入格式
4 头公牛身高为 2、8、5、5,4 头母牛身高为 1、4、10、7。
说明 — 输出格式
按身高,最佳配对为 2-1、8-10、5-4、5-7,总身高差之和为 6。
题目作者:Brian Dean,2004