题意简述
Ali 和 Bahamin 决定在美丽的伊朗南部海岸度过暑假。
他们还商定在旅行期间进行一些购物——但他们没有设定固定的预算，而是决定通过玩一个游戏来决定他们要花多少钱。
游戏在两个数组 $a$ 和 $b$ 上进行，每个数组包含 $n$ 个整数。
游戏将持续 $k$ 轮。在一轮中：
首先，Ali 选择两个索引 $i$ 和 $j$ ($1 \le i < j \le n$)；
然后，Bahamin 任意重新排列四个整数 $a_i, a_j, b_i$ 和 $b_j$。
请注意，Bahamin 可以在两个数组之间交换数字。他也可以保持两个数组不变。
所有 $k$ 轮结束后，游戏的价值被定义为 $v = \sum\limits_{i=1}^n |a_i - b_i|$。
Ali 和 Bahamin 在旅行中将花费恰好 $v$ 个硬币。
然而，他们的目标大相径庭：
Ali 希望花费尽可能少，即最小化 $v$； Bahamin 希望花费尽可能多，即最大化 $v$。
你需要找到如果 Ali 和 Bahamin 都以最优策略进行游戏，他们最终将花费的硬币数量。
思路分析
首先，由于 Ali 和 Bahamin 一个负责选择一个负责交换，且他们的目标不同。
所以 Ali 选的时候就要保证交换能得到的最大值最小。
又由于可以重复选择，所以不需要选择 $k$ 次，重复 $k$ 次选择同一组下标即可保证后续 $k-1$ 次操作一定不会使 $v$ 升高。
并且，由于 Bahamin 可以选择不交换，那么最后得到的 $v$ 一定大于等于最开始的 $v$。
且由于 $v = \sum\limits_{i=1}^n |a_i - b_i|$，$a_i$ 和 $b_i$ 的大小关系不重要，所以我们可以假定 $a_i \leq b_i$.
取四个数 $a \leq b \leq c \leq d$。
这四个数在 $(a_i,b_i),(a_j,b_j)$ 的分布有四种情况：
- $(a,b)$ 和 $(c,d)$：$v_1=(b-a)+(d-c)$
- $(a,c)$ 和 $(b, d)$：$v_2=(c-a)+(d-b)$
- $(a.d)$ 和 $(b,c)$：$v_3=(d-a)+(c-b)$
容易发现$v_3=v_2=v_1+2(c-b)$。
也就是说，只有 $v_1 \to v_2,v_3$ 这种情况可以加大最后的 $v$。
那么 Ali 只要选择满足 $v_2$ 或 $v_3$ 这两种情况之一的任一对 $i,j$ 即可使最后 $v$ 不增。
如果没有任何满足上述两种情况的，就选择一组使 $c-b$ 最小的 $i,j$ 即可。
实际上这有点类似线段覆盖问题。
把上面这些都看成线段，情况一就是线段两两不相交，另两种都是线段相交的。