P5616. 旧街爆破预算

场次：2026年10月10日-非AI方向 · 来源：CodeFun2000 P5616

题目描述

云小核领下一份清拆委托，要做的事是把这条老街重新修起来，所以沿街还留着的旧房得一间不剩地清完。他手上有一张坐标图，每间旧房落在哪个刻度，图上都标了出来。爆破弹也备了很多，不过落点只能挑在某一间旧房里面，而且每一枚都带着自己的覆盖半径；弹种不一样，覆盖半径也不一样，点响其中一枚所付出的资源数目，正好等于这一枚自己的覆盖半径。只要某间旧房到落点的间距没有超过该覆盖半径，这间旧房就会跟着被清掉。经费并不宽裕，请算出把全部旧房清完，最少要付出多少资源数目。

拿下面这份数据来看，最少付出的资源数目是 $20$。

输入格式

第 $1$ 行给出两个整数 $P$ 和 $Q$。其中 $1 \le P \le 100$，写的是旧房一共有多少间；$1 \le Q \le 10$，写的是爆破弹一共有多少种规格。

第 $2$ 行给出 $P$ 个两两不同的整数 $x_1,x_2,\ldots,x_P$。其中 $0 \le x_i \le 1000000000$，写的是各间旧房所在的坐标。

第 $3$ 行给出 $Q$ 个两两不同的整数 $r_1,r_2,\ldots,r_Q$。其中 $1 \le r_i \le 1000000000$，写的是每一种规格对应的覆盖半径。

输出格式

输出一行，里面只有一个整数，也就是把全部旧房清完时最少要付出的资源数目。

示例

示例 1

输入：

3 3
0 12 40
8 12 30

输出：

20

说明：

在坐标 $0$ 投放覆盖半径为 $12$ 的爆破弹，坐标 $0$ 与 $12$ 这两间旧房都会被清掉；再在坐标 $40$ 投放覆盖半径为 $8$ 的爆破弹。两边相加是 $12 + 8 = 20$。若改在坐标 $12$ 投放半径 $30$ 的弹，三间可以一次清完，但要付出 $30$。每间单独用半径 $8$，则要付出 $24$。

示例 2

输入：

8 3
0 3 6 50 54 58 100 130
3 4 10

输出：

13

说明：

在坐标 $3$ 投放半径 $3$ 的爆破弹，坐标 $0$、$3$、$6$ 三间都会被清掉。在坐标 $54$ 投放半径 $4$ 的爆破弹，坐标 $50$、$54$、$58$ 三间都会被清掉。坐标 $100$ 与 $130$ 相距 $30$，现有规格里没有哪一种能同时罩住这两间，于是各投放一枚半径 $3$ 的爆破弹。四枚加在一起是 $3 + 4 + 3 + 3 = 13$。