CF1566F.Points Movement

There are $n$ points and $m$ segments on the coordinate line. The initial coordinate of the $i$-th point is $a_i$. The endpoints of the $j$-th segment are $l_j$ and $r_j$ — left and right endpoints, respectively.

You can move the points. In one move you can move any point from its current coordinate $x$ to the coordinate $x - 1$ or the coordinate $x + 1$. The cost of this move is $1$.

You should move the points in such a way that each segment is visited by at least one point. A point visits the segment $[l, r]$ if there is a moment when its coordinate was on the segment $[l, r]$ (including endpoints).

You should find the minimal possible total cost of all moves such that all segments are visited.

在数轴上有 $n$ 个点和 $m$ 条线段。第 $i$ 个点的初始坐标为 $a_i$。第 $j$ 条线段的两个端点分别为 $l_j$ 和 $r_j$（即左端点与右端点）。

你可以移动这些点。每次操作中，可将任意一个点从当前坐标 $x$ 移动到 $x - 1$ 或 $x + 1$，该操作的代价为 $1$。

你需要移动这些点，使得每条线段都被至少一个点访问过。当某个点在某一时刻的坐标落在区间 $[l, r]$ 上（含端点）时，称该点访问了线段 $[l, r]$。

请找出满足所有线段均被访问的前提下，所有移动操作的总代价的最小可能值。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of points and segments respectively.

The next line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the initial coordinates of the points.

Each of the next $m$ lines contains two integers $l_j$, $r_j$ ($-10^9 \le l_j \le r_j \le 10^9$) — the left and the right endpoints of the $j$-th segment.

It's guaranteed that the sum of $n$ and the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case print a single integer — the minimal total cost of all moves such that all segments are visited.

对于每个测试用例，输出一个整数——使得所有线段均被访问的全部移动的最小总代价。

In the first test case the points can be moved as follows:

• Move the second point from the coordinate $6$ to the coordinate $5$.
• Move the third point from the coordinate $14$ to the coordinate $13$.
• Move the fourth point from the coordinate $18$ to the coordinate $17$.
• Move the third point from the coordinate $13$ to the coordinate $12$.
• Move the fourth point from the coordinate $17$ to the coordinate $16$.

The total cost of moves is $5$. It is easy to see, that all segments are visited by these movements. For example, the tenth segment ($[7, 13]$) is visited after the second move by the third point.

Here is the image that describes the first test case:

在第一个测试用例中，各点可以按如下方式移动：

• 将第二个点从坐标 $6$ 移动到坐标 $5$；
• 将第三个点从坐标 $14$ 移动到坐标 $13$；
• 将第四个点从坐标 $18$ 移动到坐标 $17$；
• 将第三个点从坐标 $13$ 移动到坐标 $12$；
• 将第四个点从坐标 $17$ 移动到坐标 $16$。

移动的总代价为 $5$。容易看出，所有线段均被这些移动所覆盖。例如，第十个线段（$[7, 13]$）在第二次移动后即被第三个点覆盖。

下图描述了第一个测试用例：