/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 人の児童がおり、 i 番目の児童の身長は H_i です。 N は奇数です。
今から、先生であるあなたを含めた N+1 人で 2 人 1 組を \large\frac{N+1}2 ペア組みます。
あなたの目標は、それぞれのペアの身長の差の合計を最小化することです。
すなわち、 i 番目のペアの身長の組を (x_i, y_i) としたとき、 \displaystyle \sum_{i=1}^{(N+1)/2}|x_i-y_i| を最小化したいです。
あなたには M 個の変身形態があり、 i 番目の変身形態での身長は W_i です。
あなたの変身形態とペアの組み方を工夫することで、それぞれのペアの身長の差の合計が最小でいくつにできるか求めてください。
制約
- 入力はすべて整数
- 1 \leq N, M \leq 2 \times 10^5
- N は奇数
- 1 \leq H_i \leq 10^9
- 1 \leq W_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M H_1 \dots H_N W_1 \dots W_M
出力
変身形態とペアの組み方を工夫したときの、それぞれのペアの身長の差の合計の最小値を出力せよ。
入力例 1
5 3 1 2 3 4 7 1 3 8
出力例 1
3
身長 8 の変身形態を選び、身長が (1, 2), (3, 4), (7, 8) のペアを作ると最小になります。
入力例 2
7 7 31 60 84 23 16 13 32 96 80 73 76 87 57 29
出力例 2
34
入力例 3
15 10 554 525 541 814 661 279 668 360 382 175 833 783 688 793 736 496 732 455 306 189 207 976 73 567 759
出力例 3
239
Score : 500 points
Problem Statement
There are N children in a kindergarten. The height of the i-th child is H_i. Here, N is an odd number.
You, the teacher, and these children - N+1 people in total - will make \large\frac{N+1}2 pairs.
Your objective is to minimize the sum of the differences in height over those pairs. That is, you want to minimize \displaystyle \sum_{i=1}^{(N+1)/2}|x_i-y_i|, where (x_i, y_i) is the pair of heights of people in the i-th pair.
You have M forms that you can transform into. Your height in the i-th form is W_i.
Find the minimum possible sum of the differences in height over all pairs, achieved by optimally choosing your form and making pairs.
Constraints
- All values in input are integers.
- 1 \leq N, M \leq 2 \times 10^5
- N is an odd number.
- 1 \leq H_i \leq 10^9
- 1 \leq W_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N M H_1 \dots H_N W_1 \dots W_M
Output
Print the minimum possible sum of the differences in height over all pairs, achieved by optimally choosing your form and making pairs.
Sample Input 1
5 3 1 2 3 4 7 1 3 8
Sample Output 1
3
The minimum is minimized by choosing the form with the height 8 and making pairs with heights (1, 2), (3, 4), and (7, 8).
Sample Input 2
7 7 31 60 84 23 16 13 32 96 80 73 76 87 57 29
Sample Output 2
34
Sample Input 3
15 10 554 525 541 814 661 279 668 360 382 175 833 783 688 793 736 496 732 455 306 189 207 976 73 567 759
Sample Output 3
239