← 返回题目列表

AtCoder · abc181_e

E. 变形老师

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 幼儿园里的孩子们。的高度 i第一个孩子是 H_i。在这里, N 是奇数。

你、老师和这些孩子 - N+1 人总数 - 将使 \large\frac{N+1}2 对。

您的目标是最小化这些对的身高差异之和。 也就是说,你想最小化 \displaystyle \sum_{i=1}^{(N+1)/2}|x_i-y_i|,其中 (x_i, y_i) 是人的身高对 i第对。 您可以转换成的

你有 M 形式。你的身高在 i-th 形式是 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