点的移动

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

数轴上有 $n$ 个点和 $m$ 条闭区间。第 $i$ 个点的初始坐标为 $a_i$，第 $j$ 个区间为 $[l_j,r_j]$。

一次操作可以选择一个点，把它从坐标 $x$ 移动到 $x-1$ 或 $x+1$，代价为 $1$。如果某一时刻一个点的坐标属于区间 $[l,r]$，就称这个点访问了该区间。

求让每个区间都至少被一个点访问所需的最小总代价。

输入格式

第一行包含测试数据组数 $t$。

每组测试数据的第一行包含两个整数 $n,m$。

第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，每行包含两个整数 $l_j,r_j$。

输出格式

对每组测试数据输出一行一个整数，表示最小总代价。

样例输入

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

样例输出

5
22

样例说明

第一组数据中，可以把坐标 $6$ 的点移动到 $5$，把坐标 $14$ 的点依次移动到 $13,12$，把坐标 $18$ 的点依次移动到 $17,16$，总代价为 $5$。

数据范围

对于所有测试数据，$1\le t\le 10^4$，$1\le n,m\le2\times10^5$，$-10^9\le a_i,l_j,r_j\le10^9$，$l_j\le r_j$，且同一组数据中的 $a_i$ 两两不同。所有测试数据中 $n$ 的总和与 $m$ 的总和分别不超过 $2\times10^5$。