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.


-----Input-----

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$.


-----Output-----

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


-----Examples-----

Input
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
Output
5
22


-----Note-----

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:

Difficulty: VERY_HARD
Tags: Sorting

Implementation

Greedy algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
from bisect import bisect_left, bisect_right
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	alst = sorted(list(map(int, input().split())))
	lr = []
	for _ in range(m):
		(l, r) = map(int, input().split())
		if bisect_left(alst, l) == bisect_right(alst, r):
			lr.append((l, r))
	alst = [-10 ** 20] + alst + [10 ** 20]
	inf = 10 ** 20
	dp = [[inf, inf] for _ in range(n + 2)]
	dp[0] = [0, 0]
	p = 0
	lr.sort()
	l = len(lr)
	for (i, a) in enumerate(alst[1:], 1):
		lst = []
		while p < l and lr[p][0] < a:
			lst.append(lr[p])
			p += 1
		if not lst:
			dp[i][0] = min(dp[i - 1])
			dp[i][1] = min(dp[i - 1])
			continue
		min_ = [alst[i]]
		for (_, r) in lst[::-1]:
			min_.append(min(min_[-1], r))
		min_ = min_[::-1]
		l_s = [alst[i - 1]] + [ll for (ll, _) in lst]
		a0 = alst[i - 1]
		a1 = alst[i]
		for (ll, m) in zip(l_s, min_):
			dp[i][0] = min(dp[i][0], dp[i - 1][0] + ll - a0 + (a1 - m) * 2, dp[i - 1][1] + (ll - a0) * 2 + (a1 - m) * 2)
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + ll - a0 + a1 - m, dp[i - 1][1] + (ll - a0) * 2 + a1 - m)
	print(min(dp[-1]))


import sys
input = sys.stdin.readline
dp1 = [0] * 200001
dp2 = [0] * 200001
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	points = sorted(list(map(int, input().split())))
	segments = []
	for _ in range(m):
		segments.append(tuple(map(int, input().split())))
	segments.sort()
	stack = []
	j = 0
	for i in range(0, n + 1):
		while j < m and (i == n or segments[j][0] <= points[i]):
			if i == n or segments[j][1] < points[i]:
				stack.append(segments[j])
			j = j + 1
		if i == 0:
			dp1[i] = points[i] - min((stack[k][1] for k in range(len(stack)))) if stack else 0
			dp2[i] = 2 * dp1[i]
			stack = []
		elif i == n:
			toGo = stack[-1][0] - points[i - 1] if stack else 0
			dp1[i] = min(dp1[i - 1] + toGo * 2, dp2[i - 1] + toGo)
		else:
			stack.insert(0, (points[i - 1], 0))
			minRight = points[i]
			dp1[i] = dp2[i] = 0
			while stack:
				segment = stack.pop()
				left = segment[0]
				right = segment[1]
				x = left - points[i - 1]
				y = points[i] - minRight
				temp = min(dp1[i - 1] + 2 * x, dp2[i - 1] + x)
				dp1[i] = temp + y if dp1[i] == 0 else min(dp1[i], temp + y)
				dp2[i] = temp + 2 * y if dp2[i] == 0 else min(dp2[i], temp + 2 * y)
				minRight = min(minRight, right)
	print(dp1[n])


import itertools
int_inputs = lambda : tuple(map(int, input().rstrip().split()))
contains = lambda t1, t2: t1[0] <= t2[0] and t1[1] >= t2[1]

def process(b1, b2, left, right, group):
	if not group:
		gen = iter([(0, 0)])
	elif right is None:
		gen = iter([(group[-1][0] - left, 0)])
	elif left is None:
		gen = iter([(0, right - group[0][1])])
	else:
		gen = zip(itertools.chain([0], [current[0] - left for current in group]), itertools.chain([right - current[1] for current in group], [0]))
	(dl, dr) = next(gen)
	v = min(b1 + 2 * dl, b2 + dl)
	(b1n, b2n) = (v + dr, v + dr * 2)
	for (dl, dr) in gen:
		v = min(b1 + 2 * dl, b2 + dl)
		(b1n, b2n) = (min(b1n, v + dr), min(b2n, v + dr * 2))
	return (b1n, b2n)
for t in range(int(input())):
	(n, m) = int_inputs()
	P = sorted(int_inputs())
	S0 = sorted([int_inputs() for i in range(m)])
	S1 = []
	for current in S0:
		if S1 and contains(current, S1[-1]):
			continue
		while S1 and contains(S1[-1], current):
			S1.pop()
		S1.append(current)
	areas = zip([None] + P, P + [None])
	S = [list(next(areas)) + [[]]]
	for current in S1:
		(left, right, group) = S[-1]
		while right is not None and current[0] > right:
			S.append(list(next(areas)) + [[]])
			(left, right, group) = S[-1]
		if right is not None and current[1] >= right:
			continue
		group.append(current)
	for area in areas:
		S.append(list(area) + [[]])
	b1 = b2 = 0
	for (left, right, group) in S:
		(b1, b2) = process(b1, b2, left, right, group)
	print(min(b1, b2))