坐标线上有$$$n$$$个点和$$$m$$$段。第 $$$i$$$ 个点的初始坐标是 $$$a_i$$$。第 $$$j$$$ 段的端点分别是 $$$l_j$$$ 和 $$$r_j$$$ — 左端点和右端点。
您可以移动点。在一次移动中,您可以将任意点从当前坐标 $$$x$$$ 移动到坐标 $$$x - 1$$$ 或坐标 $$$x + 1$$$。此移动的成本为 $$$1$$$。
您应该以这样的方式移动点,使得每个线段至少被一个点访问。如果某个点的坐标某个时刻位于线段 $$$[l, r]$$$(包括端点)上,则该点会访问线段 $$$[l, r]$$$。
您应该找到所有移动的最小可能总成本,以便访问所有段。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - 分别是点和线段的数量。
下一行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) - 点的初始坐标。
接下来的 $$$m$$$ 行包含两个整数 $$$l_j$$$、$$$r_j$$$ ($$$-10^9 \le l_j \le r_j \le 10^9$$$) — 第 $$$j$$$ 段的左端点和右端点。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 访问所有段的所有移动的最小总成本。
示例
输入 #1
2 4 11 2 6 14 18 0 3 4 5 11 15 3 5 10 13 16 16 1 4 8 12 17 19 7 13 14 19 4 12 -9 -16 12 3 -20 -18 -14 -13 -10 -7 -3 -1 0 4 6 11 7 9 8 10 13 15 14 18 16 17 18 19
输出 #1
5 22
注意
在第一个测试用例中,可以按如下方式移动点:
- 将第二个点从坐标 $$$6$$$ 移动到坐标 $$$5$$$。
- 将第三个点从坐标 $$$14$$$ 移动到坐标 $$$13$$$。
- 将第四个点从坐标 $$$18$$$ 移动到坐标 $$$17$$$。
- 将第三个点从坐标 $$$13$$$ 移动到坐标 $$$12$$$。
- 将第四个点从坐标 $$$17$$$ 移动到坐标 $$$16$$$。
移动的总成本为 $$$5$$$。很容易看出,所有段都被这些运动访问。例如,在第二次移动之后由第三个点访问第十段 ($$$[7, 13]$$$)。
这是描述第一个测试用例的图像: