#P14064. [PO Final 2022] 卡牌 / Kortlek

[PO Final 2022] 卡牌 / Kortlek

题目描述

Nicole 和 Simon 玩一个由 NN 轮组成的纸牌游戏。在第 ii 轮,Nicole 打出一张写有数值 aia_i 的牌。Simon 需要从自己的手牌中打出一张牌作为应对。若 Simon 打出的牌值为 bib_i,则 Nicole 得到 aibi|a_i - b_i| 分。因此,Simon 希望打出尽可能接近 Nicole 所出牌值的牌。

给定 Nicole 将要打出的牌以及 Simon 起始手牌中的 MM 张牌,若 Simon 最优游戏,Nicole 能得到的最小总分是多少?MM 始终等于 NNN+1N+1

输入格式

第一行包含两个整数:1N21051 \le N \le 2 \cdot 10^5NMN+1N \le M \le N+1

第二行包含 NN 个整数,第 ii 个数 aia_i0ai1090 \le a_i \le 10^9)表示第 ii 轮 Nicole 打出的牌的数值。

第三行包含 MM 个整数,第 ii 个数 bib_i0bi1090 \le b_i \le 10^9)表示 Simon 起始手牌中第 ii 张牌的数值。

输出格式

输出一个整数——在 Simon 最优游戏时,Nicole 所获得的最小总分。

2 3
1 10
2 0 1

8
3 3
4 8 1
5 1 2

5
4 5
6 10 6 2
1 4 0 6 3

10
5 5
0 0 0 0 0
1000000000 1000000000 1000000000 1000000000 1000000000

5000000000

提示

样例解释

在样例 1 中,Simon 在第一轮打出数值 1 的牌,在第二轮打出数值 2 的牌。此时 Nicole 的得分为 11+102=8|1 - 1| + |10 - 2| = 8

在样例 2 中,Simon 按顺序打出数值 2、5、1 的牌。

在样例 3 中,Simon 按顺序打出数值 4、6、3、1 的牌。

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | 11 | 1515 | N8N \le 8 | | 22 | 2525 | N2000N \le 2000 | | 33 | 2020 | M=NM = N | | 44 | 4040 | 无额外限制 |