CF1566F Points Movement

在数轴上有 $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 \times 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 \times 10^5$。

对于每组测试数据，输出一个整数，表示使所有线段都被访问的最小总代价。

在第一个测试用例中，可以按如下方式移动点： - 将第二个点从坐标 $6$ 移动到坐标 $5$。 - 将第三个点从坐标 $14$ 移动到坐标 $13$。 - 将第四个点从坐标 $18$ 移动到坐标 $17$。 - 将第三个点从坐标 $13$ 移动到坐标 $12$。 - 将第四个点从坐标 $17$ 移动到坐标 $16$。 移动的总代价为 $5$。可以看出，所有线段都被这些移动访问。例如，第十条线段（$[7, 13]$）在第二次移动后被第三个点访问。 下图描述了第一个测试用例的情况：  由 ChatGPT 4.1 翻译