Transformable Teacher

题目描述

幼儿园里有 $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$ 个形态下的身高是 $W_i$。 通过最优选择你的形态并进行配对，求在所有配对中身高差的最小可能总和。

输入格式

从标准输入读取，格式如下： $N$ $M$ $H_1$ $\dots$ $H_N$ $W_1$ $\dots$ $W_M$

输出格式

输出通过最优选择你的形态并进行配对所能得到的所有配对中身高差的最小可能总和。

5 3
1 2 3 4 7
1 3 8

3

7 7
31 60 84 23 16 13 32
96 80 73 76 87 57 29

34

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

239

提示

输入中的所有数值均为整数。 $1 \leq N, M \leq 2 \times 10^5$ $N$ 为奇数。 $1 \leq H_i \leq 10^9$ $1 \leq W_i \leq 10^9$最小值通过选择身高为 $8$ 的形态并进行配对 $(1, 2)$、$(3, 4)$ 和 $(7, 8)$ 达到。

标签: AtCoder|abc181E

来源

AtCoder|abc181E