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$ 种形态下的身高为 $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$

输出

打印最优选择你的形态和进行分组后的所有对的身高差值和的最小值。

5 3
1 2 3 4 7
1 3 8

3

通过选择身高为 $8$ 的形态，并且分组为身高对 $(1, 2)$、$(3, 4)$ 和 $(7, 8)$，可以使得这个和最小。

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