Pak Chanek has $n$ two-dimensional slices of cheese. The $i$-th slice of cheese can be represented as a rectangle of dimensions $a_i \times b_i$. We want to arrange them on the two-dimensional plane such that:

Each edge of each cheese is parallel to either the x-axis or the y-axis.

The bottom edge of each cheese is a segment of the x-axis.

No two slices of cheese overlap, but their sides can touch.

They form one connected shape.

Note that we can arrange them in any order (the leftmost slice of cheese is not necessarily the first slice of cheese). Also note that we can rotate each slice of cheese in any way as long as all conditions still hold.

Find the minimum possible perimeter of the constructed shape.


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of slices of cheese Pak Chanek has.

The $i$-th of the next $n$ lines of each test case contains two integers $a_i$ and $b_i$ ($1 \leq a_i,b_i \leq 10^9$) — the dimensions of the $i$-th slice of cheese.

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


-----Output-----

For each test case, output a line containing an integer representing the minimum possible perimeter of the constructed shape.


-----Examples-----

Input
3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65
Output
26
24
134


-----Note-----

In the first test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.

We can calculate that the perimeter of the constructed shape is $2+5+1+1+1+1+3+1+5+1+2+3=26$. It can be shown that we cannot get a smaller perimeter.

Consider the following invalid arrangement.

Even though the perimeter of the shape above is $24$, it does not satisfy all conditions of the problem. The bottom edge of the $1 \times 1$ slice of cheese is not a segment of the x-axis.

In the second test case, a way of getting the minimum possible perimeter is to arrange the slices of cheese as follows.

We can calculate that the perimeter of the constructed shape is $2+2+2+3+2+3+2+2+2+4=24$. It can be shown that we cannot get a smaller perimeter.

Source: codeforces | Difficulty: EASY
Tags: Geometry

Sorting

Greedy algorithms


Solutions:
import sys
num_of_cases = int(sys.stdin.readline().rstrip())
for _ in range(num_of_cases):
	number_of_pieces = eval(sys.stdin.readline().rstrip())
	pieces = []
	(x, y) = (0, 0)
	for _ in range(number_of_pieces):
		(first, second) = [int(i) for i in sys.stdin.readline().rstrip().split()]
		if first > second:
			x += second
			if first > y:
				y = first
		else:
			x += first
			if second > y:
				y = second
	print(x * 2 + y * 2)


import sys

def read():
	return [int(x) for x in sys.stdin.readline().split(' ')]
[t] = read()
for _ in range(t):
	[n] = read()
	x = 0
	y = 0
	for _ in range(n):
		[a, b] = read()
		if a > b:
			(a, b) = (b, a)
		x += a
		if y < b:
			y = b
	print(2 * (y + x))


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		para = 0
		maximum = 0
		for j in range(n):
			(temp1, temp2) = input().split(' ')
			temp1 = int(temp1)
			temp2 = int(temp2)
			if temp1 < temp2:
				maxi = temp2
				mini = temp1
			else:
				maxi = temp1
				mini = temp2
			if maximum < maxi:
				maximum = maxi
			para += mini * 2
		para += maximum * 2
		print(para)
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	m = 0
	c = 0
	for zz in range(n):
		x = list(map(int, input().split()))
		x.sort()
		c += x[0]
		m = max(m, x[1])
	print((c + m) * 2)


def cheeseadd():
	t = int(input())
	for i in range(t):
		n = int(input())
		(h, l) = (0, 0)
		for j in range(n):
			para = input().split(' ')
			(a, b) = (int(para[0]), int(para[1]))
			if a > b:
				h = max(h, a)
				l += b
			else:
				h = max(h, b)
				l += a
		res = (h + l) * 2
		print(res)
cheeseadd()


from re import M
from sys import stdin

def readint():
	return int(stdin.readline())

def readarray(typ):
	return list(map(typ, stdin.readline().split()))

def readmatrix(n):
	M = []
	for _ in range(n):
		row = readarray(int)
		assert len(row) == n
		M.append(row)
	return M

def mult(M, v):
	n = len(M)
	return [sum((M[i][j] * v[j] for j in range(n))) for i in range(n)]
t = readint()
for _ in range(t):
	n = readint()
	ans = 0
	maxx = []
	for _ in range(n):
		arr = readarray(int)
		if arr[0] >= arr[1]:
			ans += arr[1]
			maxx.append(arr[0])
		else:
			ans += arr[0]
			maxx.append(arr[1])
	print(ans * 2 + max(maxx) * 2)


for _ in range(int(input())):
	res = 0
	m = 0
	for i in range(int(input())):
		(a, b) = [int(j) for j in input().split()]
		if a < b:
			res += a
			if m < b:
				m = b
		else:
			res += b
			if m < a:
				m = a
	print((res + m) * 2)


import collections
import math
import sys
from queue import PriorityQueue

def main(testnumber):
	n = int(input())
	sum = 0
	mx = -10
	for i in range(n):
		(a, b) = map(int, input().split())
		if a > b:
			(a, b) = (b, a)
		sum += a
		mx = max(mx, b)
	print((sum + mx) * 2)
t = int(input())
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


for t in range(int(input())):
	n = int(input())
	p = 0
	max_b = 0
	for n in range(n):
		(a, b) = [int(a) for a in input().split()]
		if a > b:
			p += b
			if a > max_b:
				max_b = a
		else:
			p += a
			if b > max_b:
				max_b = b
	p += max_b
	p *= 2
	print(p)


t = int(input())
for _ in range(t):
	n = int(input())
	length = 0
	breadth = 0
	for __ in range(n):
		(x, y) = map(int, input().split())
		if x < y:
			(x, y) = (y, x)
		if x > length:
			length = x
		breadth = breadth + y
	print(2 * (length + breadth))


T = int(input())
for _ in range(T):
	n = int(input())
	m1 = 0
	s = 0
	for i in range(n):
		(x, y) = map(int, input().split())
		if x >= y:
			s += y
			if x > m1:
				m1 = x
		else:
			s += x
			if y > m1:
				m1 = y
	print(m1 * 2 + s * 2)


def Jumbo_Extra_Cheese():
	t = int(input())
	for i in range(t):
		slices = int(input())
		array_x = []
		array_y = []
		for j in range(slices):
			(n, m) = map(int, input().split())
			if n < m:
				(n, m) = (m, n)
			array_x.append(m)
			array_y.append(n)
		print(max(array_y) * 2 + sum(array_x) * 2)

def main():
	Jumbo_Extra_Cheese()
main()


def cheese():
	x = int(input())
	widht = []
	height = []
	for i in range(x):
		(y, z) = map(int, input().split())
		if y > z:
			(y, z) = (z, y)
		widht.append(y)
		height.append(z)
	print(sum(widht) * 2 + max(height) * 2)

def main():
	test_cases = int(input())
	for i in range(test_cases):
		cheese()
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = 0
	max = 0
	for i in range(n):
		(p, q) = map(int, input().split())
		if p < q:
			s = s + p
			if q > max:
				max = q
		else:
			s = s + q
			if p > max:
				max = p
	s = 2 * s
	print(s + 2 * max)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	h = 0
	l = 0
	for _ in range(n):
		(x, y) = map(int, sys.stdin.readline().split())
		(x, y) = (max(x, y), min(x, y))
		h += y
		l = max(x, l)
	print((h + l) * 2)


def main():
	n = int(input())
	for i in range(n):
		m = int(input())
		s = 0
		b = 0
		for j in range(m):
			k = input()
			a = list(map(int, k.split()))
			if a[0] < a[1]:
				s += a[0]
				if b < a[1]:
					b = a[1]
			else:
				s += a[1]
				if b < a[0]:
					b = a[0]
		print(2 * s + 2 * b)
main()


t = int(input())
for tst in range(t):
	n = int(input())
	p = 0
	h = 0
	for i in range(n):
		(a, b) = [int(w) for w in input().split()]
		if a < b:
			p += a
			if h < b:
				h = b
		else:
			p += b
			if h < a:
				h = a
	p += h
	p *= 2
	print(p)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ans = 0
	a = [0]
	for i in range(n):
		(x, y) = map(int, input().split())
		if x > y:
			(x, y) = (y, x)
		ans += 2 * x
		a.append(y)
	a.sort()
	a.append(0)
	for i in range(1, n + 2):
		ans += abs(a[i] - a[i - 1])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	per = 0
	max = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		if a > b:
			per += b * 2
			if a > max:
				max = a
			continue
		per += a * 2
		if b > max:
			max = b
	per += max * 2
	print(per)


t = int(input())
for t1 in range(t):
	n = int(input())
	peri = 0
	max = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		if a < b:
			(a, b) = (b, a)
		peri += 2 * b
		if a > max:
			max = a
	peri += 2 * max
	print(peri)


import sys
import math
from math import gcd, sqrt, log2, ceil, floor
import heapq as hq
from bisect import bisect_right, bisect_left, bisect
import itertools
from sys import stdin, stdout, setrecursionlimit
MOD = int(1000000000.0) + 7
alp = 'abcdefghijklmnopqrstuvwxyz'
T = 1
T = int(stdin.readline())
for _ in range(T):
	n = int(stdin.readline())
	A = []
	B = []
	for i in range(n):
		k = list(map(int, stdin.readline().rstrip().split()))
		a = min(k)
		b = max(k)
		A.append(a)
		B.append(b)
	print(2 * (sum(A) + max(B)))


t = int(input())
for _ in range(t):
	n = int(input())
	S = 0
	M = 0
	for i in range(n):
		(a, b) = list(map(int, input().split()))
		if a >= b:
			S += b
			if a > M:
				M = a
		else:
			S += a
			if b > M:
				M = b
	answer = 2 * S + 2 * M
	print(answer)


for _ in range(int(input())):
	n = int(input())
	s = []
	m = []
	for _ in range(n):
		(a, b) = map(int, input().split())
		if a > b:
			s.append(b)
			m.append(a)
		else:
			s.append(a)
			m.append(b)
	print(2 * sum(s) + 2 * max(m))


t = int(input())
for i in range(1, t + 1):
	n = int(input())
	j = 0
	L = []
	for i in range(1, n + 1):
		(a, b) = [int(a) for a in input().split()]
		if a >= b:
			j = j + b
			L.append(a)
		else:
			j = j + a
			L.append(b)
	ma = max(L)
	print(2 * j + 2 * ma)


def test_case():
	n = int(input())
	top = 0
	side = 0
	for _ in range(n):
		(x, y) = map(int, input().split())
		top += min(x, y)
		side = max(side, x, y)
	print(2 * (top + side))

def main():
	for _ in range(int(input())):
		test_case()
main()


for i in range(int(input())):
	ss = 0
	sb = 0
	woof = []
	for j in range(int(input())):
		(a, b) = input().split()
		a = int(a)
		b = int(b)
		woof.append(a)
		woof.append(b)
		sb += min(a, b)
	print(max(woof) * 2 + sb * 2)


t = int(input())
for i in range(t):
	n = int(input())
	ma = 0
	su = 0
	for j in range(n):
		max_b = 0
		l = list(map(int, input().split()))
		a = l[0]
		b = l[1]
		if a > b:
			max_b = a
			su += b
		else:
			max_b = b
			su += a
		if ma < max_b:
			ma = max_b
	print(2 * (ma + su))


import sys

def solve_problem():
	t = int(sys.stdin.readline())
	for _ in range(t):
		n = int(sys.stdin.readline())
		sum = 0
		arr = []
		for i in range(n):
			(a, b) = map(int, sys.stdin.readline().split())
			sum += 2 * min(a, b)
			arr.append(max(a, b))
		arr.sort()
		sum += arr[0] + arr[-1]
		for i in range(1, len(arr)):
			sum += arr[i] - arr[i - 1]
		print(sum)
solve_problem()


for _ in range(int(input())):
	n = int(input())
	(ans, mx) = (0, 0)
	for i in range(n):
		(x, y) = map(int, input().split())
		if x > y:
			(x, y) = (y, x)
		mx = max(mx, y)
		ans += x
	ans += mx
	ans *= 2
	print(ans)


for _ in range(int(input())):
	a = -1
	ans = 0
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
		if x > y:
			ans += 2 * y
			a = max(a, x)
		else:
			ans += 2 * x
			a = max(a, y)
	ans += a * 2
	print(ans)


for _ in range(int(input())):
	ma = 0
	s = 0
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		ma = max(x, y, ma)
		s += min(x, y)
	print(ma * 2 + s * 2)


n = int(input())
for i in range(n):
	m = int(input())
	(x1, x2) = ([], [])
	for j in range(m):
		t = [int(k) for k in input().split()]
		if t[0] > t[1]:
			x1.append(t[0])
			x2.append(t[1])
		else:
			x1.append(t[1])
			x2.append(t[0])
	t2 = sum(x2) + max(x1)
	print(t2 * 2)


for _ in range(int(input())):
	n = int(input())
	l = []
	for _ in range(n):
		(ai, bi) = map(int, input().split())
		if ai > bi:
			l.append((ai, bi))
		else:
			l.append((bi, ai))
	p = 2 * sum([c[1] for c in l]) + 2 * max([c[0] for c in l])
	print(p)


for _ in range(int(input())):
	n = int(input())
	x = 0
	m = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		x += min(a, b)
		m = max(m, a, b)
	print(2 * (m + x))


def solution(ln: list, length: int):
	max_height = 0
	total_width = 0
	for item in ln:
		if item[1] > item[0]:
			item = (item[1], item[0])
		if item[0] > max_height:
			max_height = item[0]
		total_width += item[1]
	return 2 * (max_height + total_width)
t = int(input())
for _ in range(t):
	n = int(input())
	ln = [tuple(map(int, input().split())) for x in range(n)]
	print(solution(ln, n))


t = int(input())
for _ in range(t):
	n = int(input())
	m = 0
	s = 0
	for i in range(n):
		(x, y) = map(int, input().split())
		if x > y:
			m = max(m, x)
			s += y
		else:
			m = max(m, y)
			s += x
	print(2 * (m + s))


for _ in range(int(input())):
	n = int(input())
	ans = 0
	maxi = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		ans += min(a, b)
		maxi = max(maxi, a, b)
	print((ans + maxi) * 2)


t = int(input())
for a1 in range(t):
	x = int(input())
	l1 = []
	l2 = []
	for c in range(x):
		(a, b) = tuple([int(a) for a in input().split()])
		if a > b:
			l1.append(a)
			l2.append(b)
		else:
			l1.append(b)
			l2.append(a)
	minsum = sum(l2)
	print(2 * (max(l1) + minsum))


def alg(mass):
	for arr_ms in mass:
		arr = arr_ms['mass']
		x_arr = arr_ms['x']
		sm = arr[len(arr) - 1]
		a = arr[0]
		for index in range(0, len(arr) - 1):
			v = arr[index + 1] - a
			a = arr[index + 1]
			arr[index + 1] = v
		print(sm + sum(arr) + x_arr)

def parsing():
	n = int(input())
	mass = []
	while n > 0:
		k = int(input())
		sm_val = 0
		res = []
		while k > 0:
			st = input().split(' ')
			(a, b) = (int(st[0]), int(st[1]))
			if a > b:
				(a, b) = (b, a)
			sm_val += a
			k -= 1
			res.append(b)
		res.sort()
		mass.append({'mass': res, 'x': 2 * sm_val})
		n -= 1
	return mass
res = parsing()
alg(res)


from os import TMP_MAX
t = int(input())
while t >= 1:
	n = int(input())
	mx = 0
	res = 0
	for i in range(0, n):
		(a, b) = map(int, input().split(' '))
		if b > a:
			tmp = a
			a = b
			b = tmp
		mx = max(mx, a)
		res = res + b
	print((res + mx) * 2)
	t = t - 1


for _ in range(int(input())):
	x = []
	y = []
	for i in range(int(input())):
		n = list(map(int, input().split()))
		if n[0] < n[1]:
			(n[0], n[1]) = (n[1], n[0])
		x.append(n[1])
		y.append(n[0])
	print(max(y) * 2 + sum(x) * 2)


t = int(input())
for i in range(t):
	n = int(input())
	cnt = 0
	mx = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		if b < a:
			cnt += 2 * b
			mx = max(mx, a)
		else:
			cnt += 2 * a
			mx = max(mx, b)
	cnt += 2 * mx
	print(cnt)


I = lambda : int(input())
Is = lambda : map(int, input().split())
Li = lambda : list(map(int, input().split()))

def solve():
	n = I()
	max_val = 0
	ans = 0
	for _ in range(n):
		(a, b) = Is()
		max_val = max(max_val, a, b)
		ans += min(a, b)
	ans += max_val
	print(ans * 2)
	return 1
t = I()
while t:
	solve()
	t -= 1


n = int(input())
for i in range(0, n):
	peri = 0
	maxi = 0
	p = int(input())
	for i in range(0, p):
		List = input().split()
		(a, b) = (int(List[0]), int(List[1]))
		peri += min(a, b)
		if maxi < max(a, b):
			maxi = max(a, b)
		else:
			pass
	print(2 * (peri + maxi))


for _ in range(int(input())):
	(mn, mx) = (0, 0)
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		mn += min(a, b)
		mx = max(a, b, mx)
	print((mn + mx) * 2)


t = int(input())
for q in range(t):
	n = int(input())
	maxs = 0
	tot = 0
	for i in range(n):
		(ai, bi) = map(int, input().split())
		maxs = max(maxs, ai, bi)
		tot += min(ai, bi)
	print(2 * tot + 2 * maxs)


t = int(input())
for j in range(0, t):
	n = int(input())
	s = 0
	m = 0
	for k in range(0, n):
		(a, b) = map(int, input().split())
		s += min(a, b)
		if max(a, b) > m:
			m = max(a, b)
	print(2 * (s + m))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	p = 0
	y = []
	for _ in range(n):
		(x_1, y_1) = map(int, input().split())
		p += min(x_1, y_1)
		y.append(max(x_1, y_1))
	p *= 2
	y = sorted(y)
	back = 0
	for i in y:
		p += i - back
		back = i
	p += y[-1]
	print(p)


t = int(input())
for _ in range(t):
	x = 0
	y = 0
	n = int(input())
	for _ in range(n):
		(a, b) = map(int, input().split())
		x += min(a, b)
		y = max(y, a, b)
	print(2 * x + 2 * y)


for CASE in range(int(input())):
	(w, h) = (0, 0)
	for i in range(int(input())):
		(a, b) = map(int, input().split())
		w += min(a, b)
		h = max(h, a, b)
	print((w + h) * 2)


for _ in range(int(input())):
	n = int(input())
	(x, y) = (0, 0)
	for i in range(n):
		z = [*map(int, input().split())]
		x += min(z)
		y = max(y, *z)
	print(2 * (x + y))


for _ in range(int(input())):
	n = int(input())
	k = 0
	mx = 0
	for __ in range(n):
		(x, y) = map(int, input().split())
		k += min(x, y)
		mx = max(mx, x, y)
	print(2 * mx + 2 * k)


for _ in range(int(input())):
	n = int(input())
	l1 = []
	l2 = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l1.append(max(a, b))
		l2.append(min(a, b))
	print(2 * (sum(l2) + max(l1)))


for _ in range(int(input())):
	n = int(input())
	sum_val = 0
	max_val = set()
	for x in range(n):
		(a, b) = map(int, input().split())
		c = max(a, b)
		max_val.add(c)
		sum_val += a + b - c
	print((max(max_val) + sum_val) * 2)


casecnt = int(input())
for case in range(casecnt):
	n = int(input())
	maxs = 0
	p = 0
	for i in range(n):
		(x, y) = [int(j) for j in input().split()]
		if x > y:
			maxs = max(x, maxs)
			p += y + y
		else:
			maxs = max(y, maxs)
			p += x + x
	print(p + maxs + maxs)


t = int(input())
for i in range(t):
	n = int(input())
	ans = 0
	maxi = 0
	for i in range(n):
		(p, q) = map(int, input().split())
		c = max(p, q)
		ans += min(p, q)
		if c > maxi:
			maxi = c
	fin = 2 * (ans + maxi)
	print(fin)


for _ in range(int(input())):
	x = 0
	y = 0
	for i in range(int(input())):
		(dx, dy) = map(int, input().split())
		x += min(dx, dy)
		y = max(y, dx, dy)
	print(2 * x + 2 * y)


t = int(input())
for _ in range(t):
	n = int(input())
	mx = 0
	k = 0
	for __ in range(n):
		(a, b) = map(int, input().split())
		if max(a, b) > mx:
			mx = max(a, b)
		k += min(a, b)
	print(2 * k + 2 * mx)


for _ in range(int(input())):
	n = int(input())
	l = []
	x = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append(a)
		l.append(b)
	for i in range(0, n * 2 - 1, 2):
		x += min(l[i], l[i + 1])
	print(2 * x + 2 * max(l))


for _ in range(int(input())):
	n = int(input())
	(H, L) = ([], [])
	for i in range(n):
		(a, b) = map(int, input().split())
		H.append(max(a, b))
		L.append(min(a, b))
	print(2 * (max(H) + sum(L)))


t = int(input())
for i in range(t):
	n = int(input())
	arr1 = []
	arr2 = []
	c = 0
	if n != 1:
		for i in range(n):
			(a, b) = map(int, input().split())
			arr1.append(min(a, b))
			arr2.append(max(a, b))
		c += sum(arr1) * 2
		c += max(arr2) * 2
		print(c)
	else:
		(a, b) = map(int, input().split())
		print(2 * a + 2 * b)


for _ in range(int(input())):
	n = int(input())
	l = []
	l2 = []
	for _ in range(n):
		(a, b) = map(int, input().split())
		l.append(min(a, b))
		l2.append(max(a, b))
	s = sum(l)
	m = max(l2)
	print(2 * (s + m))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	la = []
	co = 0
	for i in range(n):
		(a, b) = map(int, input().strip().split())
		(a, b) = (max(a, b), min(a, b))
		co += 2 * b
		la.append(a)
	la.sort()
	la.append(la[-1])
	for i in range(n - 1, 0, -1):
		la[i] -= la[i - 1]
	co += sum(la)
	print(co)


for _ in range(int(input())):
	k1 = 0
	k2 = 0
	for _ in range(int(input())):
		(g, f) = map(int, input().split())
		k1 += min(g, f)
		k2 = max(k2, max(g, f))
	if k2 == 0:
		print('0')
	else:
		print(2 * (k1 + k2))


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	val = -1
	ans = 0
	for j in range(n):
		(x, y) = map(int, input().strip().split())
		ans += min(x, y)
		val = max(x, y, val)
	print(2 * ans + 2 * val)


for _ in range(int(input())):
	(mn, mx) = ([], [])
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		mn.append(min(a, b))
		mx.append(max(a, b))
	print((sum(mn) + max(mx)) * 2)


n = int(input())
for i in range(n):
	a1 = []
	b1 = []
	m = int(input())
	for j in range(m):
		(x, y) = map(int, input().split())
		a1.append(max(x, y))
		b1.append(min(x, y))
	print(max(a1) * 2 + sum(b1) * 2)


t = int(input())
for i in range(t):
	n = int(input())
	l = 0
	p = 0
	for i in range(n):
		(a, b) = map(int, input().strip().split())
		l = max(l, a, b)
		p = p + min(a, b)
	p = p * 2
	p += 2 * l
	print(p)


def sol(n, ab):
	width = 0
	height = 0
	for i in range(n):
		(a, b) = ab[i]
		if a > b:
			width += b
			height = max(a, height)
		else:
			width += a
			height = max(b, height)
	return (width + height) * 2
t = int(input())
for _ in range(t):
	n = int(input())
	ab = [[int(v) for v in input().split()] for _ in range(n)]
	print(sol(n, ab))


t = int(input())
for k in range(t):
	n = int(input())
	(sum, max_) = (0, 0)
	for i in range(n):
		(a, b) = map(int, input().split(' '))
		sum += min(a, b)
		max_ = max(max_, max(a, b))
	print(f'{2 * (sum + max_)}')


for _ in range(int(input())):
	n = int(input())
	mx = 0
	sm = 0
	for x in range(n):
		(a, b) = list(map(int, input().split()))
		mx = max(a, b, mx)
		sm += min(a, b)
	ans = 2 * mx + 2 * sm
	print(ans)


T = int(input())
for tt in range(T):
	max_edge = 0
	bottom_edge = 0
	n = int(input())
	for i in range(n):
		(a, b) = tuple(map(int, input().split()))
		bottom_edge += min(a, b)
		max_edge = max(max_edge, a, b)
	print(bottom_edge * 2 + max_edge * 2)


test_case_count = int(input())
for _ in range(test_case_count):
	cheese_count = int(input())
	cheese_data_length = []
	cheese_data_width = []
	for i in range(cheese_count):
		(n, m) = map(int, input().split())
		cheese_data_length.append(max(n, m))
		cheese_data_width.append(min(n, m))
	print(2 * max(cheese_data_length) + 2 * sum(cheese_data_width))


t = int(input())
for _ in range(t):
	n = int(input())
	mini = 0
	maxi = -1000000000.0
	for __ in range(n):
		(a, b) = map(int, input().split())
		mini += min(a, b)
		maxi = max(maxi, max(a, b))
	if maxi == -1000000000.0:
		print(0)
	else:
		print(2 * (mini + maxi))


for _ in range(int(input())):
	n = int(input())
	(vmin, vmax) = (0, -1000000000.0)
	for i in range(n):
		(a, b) = map(int, input().split())
		vmin += min(a, b)
		vmax = max(vmax, max(a, b))
	if vmax == -1000000000.0:
		print(0)
	else:
		res = 2 * (vmax + vmin)
		print(res)


for i in range(int(input())):
	n = int(input())
	final = 0
	a = []
	m = 0
	for i in range(n):
		l = list(map(int, input().split()))
		if l[0] > l[1]:
			a.append(l[0])
			if m < l[0]:
				m = l[0]
		else:
			a.append(l[1])
			if m < l[1]:
				m = l[1]
		final += 2 * sum(l)
	print(final - 2 * sum(a) + 2 * m)


n = int(input())
for i in range(n):
	_ = int(input())
	tot = 0
	mx = 0
	for j in range(_):
		aiaj = list(map(int, input().split()))
		if aiaj[0] < aiaj[1]:
			(aiaj[0], aiaj[1]) = (aiaj[1], aiaj[0])
		tot += aiaj[1]
		mx = max(mx, aiaj[0])
	print((tot + mx) * 2)


def foo():
	N = int(input())
	res = 0
	m = 0
	for _ in range(N):
		vi = list(map(int, input().strip().split()))
		res += 2 * min(vi)
		m = max(m, max(vi))
	return res + m * 2
T = int(input())
for _ in range(T):
	print(foo())


t = int(input())
for _ in range(t):
	d = 0
	r = 0
	n = int(input())
	for _ in range(n):
		(a, b) = map(int, input().split())
		r += min(a, b)
		d = max(d, max(a, b))
	print((d + r) * 2)