There are $n$ cities numbered from $1$ to $n$, and city $i$ has beauty $a_i$.

A salesman wants to start at city $1$, visit every city exactly once, and return to city $1$.

For all $i\ne j$, a flight from city $i$ to city $j$ costs $\max(c_i,a_j-a_i)$ dollars, where $c_i$ is the price floor enforced by city $i$. Note that there is no absolute value. Find the minimum total cost for the salesman to complete his trip.


-----Input-----

The first line contains a single integer $n$ ($2\le n\le 10^5$) — the number of cities.

The $i$-th of the next $n$ lines contains two integers $a_i$, $c_i$ ($0\le a_i,c_i\le 10^9$) — the beauty and price floor of the $i$-th city.


-----Output-----

Output a single integer — the minimum total cost.


-----Examples-----

Input
3
1 9
2 1
4 1
Output
11
Input
6
4 2
8 4
3 0
2 3
7 1
0 1
Output
13


-----Note-----

In the first test case, we can travel in order $1\to 3\to 2\to 1$.

The flight $1\to 3$ costs $\max(c_1,a_3-a_1)=\max(9,4-1)=9$.

The flight $3\to 2$ costs $\max(c_3, a_2-a_3)=\max(1,2-4)=1$.

The flight $2\to 1$ costs $\max(c_2,a_1-a_2)=\max(1,1-2)=1$.

The total cost is $11$, and we cannot do better.

Source: codeforces | Difficulty: HARD
Tags: Shortest paths

Sorting

Amortized analysis

Greedy algorithms

Dynamic programming

Data structures


Solutions:
import sys
N = int(input())
lst = []
for n in range(N):
	l = list(map(int, sys.stdin.readline().split()))
	lst.append(l)
lst.sort()
Sum = lst[0][1]
c = lst[0][0] + lst[0][1]
for i in lst[1:]:
	Sum += i[1]
	if i[0] > c:
		Sum += i[0] - c
	c = max(c, i[0] + i[1])
print(Sum)


n = int(input())
inps = []
ans = 0
for i in range(n):
	(a, c) = map(int, input().split())
	ans += c
	inps.append((a, c))
inps.sort()
topcover = inps[0][0]
for i in range(len(inps)):
	if inps[i][0] > topcover:
		ans += inps[i][0] - topcover
	topcover = max(topcover, inps[i][0] + inps[i][1])
print(ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	N = int(input())
	AC = []
	ans = 0
	for i in range(N):
		(a, c) = map(int, input().split())
		AC.append((a, c, i))
		ans += c
	AC.sort(key=lambda x: x[1])
	AC.sort(key=lambda x: x[0])
	b = AC[0][0] + AC[0][1]
	for i in range(1, N):
		(a, c, j) = AC[i]
		if a <= b:
			b = max(b, a + c)
		else:
			ans += a - b
			b = a + c
	print(ans)
main()


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	city = []
	for _ in range(n):
		city.append(tuple(map(int, input().split())))
	city.sort()
	ans = sum(map(lambda x: x[1], city))
	curMax = city[0][0] + city[0][1]
	for i in range(n):
		if curMax < city[i][0]:
			ans += city[i][0] - curMax
		curMax = max(curMax, city[i][0] + city[i][1])
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
a = sorted(([*map(int, input().split())] for i in range(n)))
(ans, c) = (a[0][1], sum(a[0]))
for w in a[1:]:
	ans += w[1] + max(w[0] - c, 0)
	c = max(c, sum(w))
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
l = []
ans = 0
for i in range(n):
	d = input().split()
	l.append((int(d[0]), int(d[1])))
	ans += int(d[1])
l.sort()
maxa = l[0][0] + l[0][1]
for i in range(1, n):
	if l[i][0] > maxa:
		ans += l[i][0] - maxa
	maxa = max(maxa, l[i][0] + l[i][1])
print(ans)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
n = inp()
seg = []
se = set()
res = 0
for _ in range(n):
	(a, c) = inpl()
	seg.append((a, a + c))
	se.add(a)
	se.add(a + c)
	res += c
d = dict()
ls = list(se)
ls.sort()
for (i, x) in enumerate(sorted(ls)):
	d[x] = i
imo = [0] * (len(ls) + 1)
for (l, r) in seg:
	L = d[l]
	R = d[r]
	imo[L] += 1
	imo[R] -= 1
imo = imo[:len(ls) - 1]
imo = list(itertools.accumulate(imo))
for (i, x) in enumerate(imo):
	if x == 0:
		res += ls[i + 1] - ls[i]
print(res)


n = int(input())
a = [[int(s) for s in input().split(' ')] for i in range(n)]
a.sort()
(ans, c) = (a[0][1], sum(a[0]))
for w in a[1:]:
	ans += w[1] + max(w[0] - c, 0)
	c = max(c, sum(w))
print(ans)


import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	cities = []
	ans = 0
	for i in range(N):
		(a, c) = getInts()
		cities.append((a, a + c))
		ans += c
	cities.sort()
	max_c = cities[0][1]
	for i in range(1, N):
		ans += max(cities[i][0] - max_c, 0)
		max_c = max(max_c, cities[i][1])
	return ans
print(solve())


import sys
input = sys.stdin.readline
n = int(input())
keyframes = []
ans = 0
for i in range(n):
	(a, c) = map(int, input().split())
	ans += c
	keyframes.append((a, -1))
	keyframes.append((a + c, 0))
keyframes.sort()
count = 0
(a, b) = keyframes[0]
prev = a
for (pos, t) in keyframes:
	if t == -1:
		if count == 0:
			ans += pos - prev
		count += 1
		prev = pos
	else:
		count -= 1
		prev = pos
print(ans)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
n = int(input())
a = [0] * n
c = [0] * n
for i in range(n):
	(a[i], c[i]) = mi()
res = sum(c)
idx = [i for i in range(n)]
idx.sort(key=lambda i: a[i])
a.sort()
c = [c[idx[i]] for i in range(n)]
dp = SegmentTree([10 ** 17] * n, min, 10 ** 17)
dp_a = SegmentTree([a[i] for i in range(n)], min, 10 ** 17)
dp.update(n - 1, 0)
for i in range(n - 2, -1, -1):
	tmp = 10 ** 17
	zero_r = bisect.bisect_right(a, a[i] + c[i])
	tmp = min(tmp, dp.query(i, zero_r))
	tmp = min(tmp, dp_a.query(zero_r, n) - a[i] - c[i])
	dp.update(i, tmp)
	dp_a.update(i, tmp + a[i])
print(dp.query(0, 1) + res)


import sys
input = lambda : sys.stdin.readline().rstrip()

class SegmentTree:

	def __init__(self, init, unitX, f):
		self.f = f
		self.unitX = unitX
		self.f = f
		if type(init) == int:
			self.n = init
			self.n = 1 << (self.n - 1).bit_length()
			self.X = [unitX] * (self.n * 2)
		else:
			self.n = len(init)
			self.n = 1 << (self.n - 1).bit_length()
			self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
			for i in range(self.n - 1, 0, -1):
				self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])

	def update(self, i, x):
		i += self.n
		self.X[i] = x
		i >>= 1
		while i:
			self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
			i >>= 1

	def getvalue(self, i):
		return self.X[i + self.n]

	def getrange(self, l, r):
		l += self.n
		r += self.n
		al = self.unitX
		ar = self.unitX
		while l < r:
			if l & 1:
				al = self.f(al, self.X[l])
				l += 1
			if r & 1:
				r -= 1
				ar = self.f(self.X[r], ar)
			l >>= 1
			r >>= 1
		return self.f(al, ar)

	def max_right(self, l, z):
		if l >= self.n:
			return self.n
		l += self.n
		s = self.unitX
		while 1:
			while l % 2 == 0:
				l >>= 1
			if not z(self.f(s, self.X[l])):
				while l < self.n:
					l *= 2
					if z(self.f(s, self.X[l])):
						s = self.f(s, self.X[l])
						l += 1
				return l - self.n
			s = self.f(s, self.X[l])
			l += 1
			if l & -l == l:
				break
		return self.n

	def min_left(self, r, z):
		if r <= 0:
			return 0
		r += self.n
		s = self.unitX
		while 1:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not z(self.f(self.X[r], s)):
				while r < self.n:
					r = r * 2 + 1
					if z(self.f(self.X[r], s)):
						s = self.f(self.X[r], s)
						r -= 1
				return r + 1 - self.n
			s = self.f(self.X[r], s)
			if r & -r == r:
				break
		return 0

	def debug(self):
		print('debug')
		print([self.getvalue(i) for i in range(min(self.n, 20))])
from bisect import bisect_left as bl
from bisect import bisect_right as br
N = int(input())
ans = 0
X = []
A = []
for _ in range(N):
	(a, c) = map(int, input().split())
	X.append((a, c))
	ans += c
	A.append(a)
SA = sorted(set(A))
D = {a: i for (i, a) in enumerate(SA)}
X.sort(key=lambda x: x[0])
XX = [(D[a], c) for (a, c) in X]
f = min
unit = 2 * 10 ** 9
st1 = SegmentTree(N, unit, f)
st2 = SegmentTree(N, unit, f)
(i, c) = XX.pop()
st1.update(i, SA[i])
st2.update(i, 0)
for (i, c) in XX[::-1]:
	a = SA[i]
	j = bl(SA, a + c)
	b = max(min(st1.getrange(j, N) - a - c, st2.getrange(0, j)), 0)
	st1.update(i, a + b)
	st2.update(i, b)
print(st2.getvalue(0) + ans)


n = int(input())
cities = []
ans = 0
for i in range(n):
	(a, c) = map(int, input().split())
	cities += [(a, c)]
	ans += c
cities = sorted(cities, key=lambda city: city[0])
mx = cities[0][0] + cities[0][1]
for i in range(1, n):
	ans += max(0, cities[i][0] - mx)
	mx = max(mx, cities[i][0] + cities[i][1])
print(ans)


N = int(input())
pts = []
ans = 0
for n in range(N):
	(a, c) = map(int, input().split())
	pts.append((a, a + c))
	ans += c
pts.sort()
cur = pts[0][0]
for (a, b) in pts:
	ans += max(0, a - cur)
	cur = max(cur, b)
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
l = []
out = 0
for _ in range(n):
	(a, c) = map(int, input().split())
	out += c
	l.append((a, c))
l.sort(key=lambda x: x[0])
curr_best = l[0][0]
for (a, c) in l:
	if a > curr_best:
		out += a - curr_best
	curr_best = max(curr_best, a + c)
print(out)


import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
from math import gcd
from math import ceil, log2, factorial
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
I = lambda : list(map(int, input().split()))
TESTS = 0

def solve():
	(n,) = I()
	a = []
	for i in range(n):
		a.append(tuple(I()))
	a.sort()
	ans = 0
	for i in range(n):
		ans += a[i][1]
	mx = 0
	for i in range(n - 1):
		mx = max(mx, a[i][0] + a[i][1])
		if mx < a[i + 1][0]:
			ans += a[i + 1][0] - mx
	print(ans)

def main():
	if not TESTS:
		solve()
		return
	(t,) = I()
	while t:
		solve()
		t -= 1
main()


import sys
input = sys.stdin.readline
n = int(input())
cit = []
ccost = 0
for i in range(n):
	(a, c) = map(int, input().split())
	cit.append([a, c])
	ccost += c
acost = 0
cit.sort()
mx = cit[0][0] + cit[0][1]
for c in cit:
	if c[0] > mx:
		acost += c[0] - mx
	mx = max(mx, sum(c))
print(acost + ccost)


n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
l.sort()
t = [l[0][0], l[0][1] + l[0][0]]
ans = 0
for (a, c) in l:
	ans += c
	p = a
	q = a + c
	if t[-1] < p:
		t.append(p)
		t.append(q)
	else:
		t[-1] = max(t[-1], q)
for i in range(1, len(t) - 1, 2):
	ans += t[i + 1] - t[i]
print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 10 ** 16
md = 10 ** 9 + 7
n = II()
ac = LLI(n)
ac.sort(key=lambda x: x[0])
now = ac[0][0]
ans = 0
for (a, c) in ac:
	ans += c
	ans += max(0, a - now)
	now = max(now, a + c)
print(ans)


import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n
		self.group = n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		self.group -= 1
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return self.group

	def all_group_members(self):
		dic = {r: [] for r in self.roots()}
		for i in range(self.n):
			dic[self.find(i)].append(i)
		return dic

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
from collections import deque

def main():
	n = int(input())
	ac = [list(map(int, input().split())) for _ in range(n)]
	for i in range(n):
		ac[i][1] += ac[i][0]
	lst = []
	ans = 0
	for (i, (a, c)) in enumerate(ac):
		ans -= a
		lst.append((a, i, 'a'))
		lst.append((c, i, 'b'))
	lst.sort(key=lambda x: (x[0], x[2]))
	UF = UnionFind(n)
	a_s = deque()
	b_s = deque()
	for (v, i, ab) in lst:
		if ab == 'a':
			a_s.append((v, i))
			if b_s:
				if not UF.same(i, b_s[0][1]):
					(av, ai) = a_s.pop()
					(bv, bi) = b_s.popleft()
					UF.union(ai, bi)
					ans += max(av, bv)
				elif not UF.same(i, b_s[-1][1]):
					(av, ai) = a_s.pop()
					(bv, bi) = b_s.pop()
					UF.union(ai, bi)
					ans += max(av, bv)
		elif ab == 'b':
			b_s.append((v, i))
			if a_s:
				if not UF.same(a_s[0][1], i):
					(av, ai) = a_s.popleft()
					(bv, bi) = b_s.pop()
					UF.union(ai, bi)
					ans += max(av, bv)
				elif not UF.same(a_s[-1][1], i):
					(av, ai) = a_s.pop()
					(bv, bi) = b_s.pop()
					UF.union(ai, bi)
					ans += max(av, bv)
	ans += max(a_s[0][0], b_s[0][0])
	print(ans)
for _ in range(1):
	main()


import io
import os
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush
from itertools import permutations

def solve1(N, A, C):
	best = float('inf')
	for perm in permutations(range(1, N)):
		perm = [0] + list(perm) + [0]
		cost = 0
		for (i, j) in zip(perm, perm[1:]):
			cost += max(0, A[j] - A[i] - C[i])
		best = min(best, cost)
	return sum(C) + best

def solve2(N, A, C):
	order = sorted(range(N), key=lambda i: A[i])
	source = order[0]
	dest = order[-1]

	def getAdj(i):
		for j in range(N):
			yield (j, max(0, A[j] - A[i] - C[i]))
	inf = float('inf')
	dist = [inf] * N
	dist[source] = 0.0
	queue = [(0.0, float(source))]
	while queue:
		(d, u) = heappop(queue)
		u = int(u)
		if dist[u] == d:
			for (v, w) in getAdj(u):
				cost = d + w
				if cost < dist[v]:
					dist[v] = cost
					heappush(queue, (cost, float(v)))
	return sum(C) + int(dist[dest])

class RangeQuery:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, start, stop):
		depth = (stop - start).bit_length() - 1
		return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])

	def __getitem__(self, idx):
		return self._data[0][idx]

def solve(N, A, C):
	order = sorted(range(N), key=lambda i: A[i])
	rmq = RangeQuery([A[i] + C[i] for i in order], func=max)
	cost = 0
	for (i, index) in enumerate(order):
		if i != 0:
			cost += max(0, A[index] - rmq.query(0, i))
	return sum(C) + cost
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(10000):
		N = random.randint(1, 10)
		A = [random.randint(0, 10) for i in range(N)]
		C = [random.randint(0, 10) for i in range(N)]
		print('tc' + str(_), N, A, C)
		ans1 = solve1(N, A, C)
		ans2 = solve2(N, A, C)
		ans = solve(N, A, C)
		print(ans, ans1, ans2)
		assert ans == ans1 == ans2
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N,) = [int(x) for x in input().split()]
	A = []
	C = []
	for i in range(N):
		(a, c) = [int(x) for x in input().split()]
		A.append(a)
		C.append(c)
	ans = solve(N, A, C)
	print(ans)


n = int(input())
a = sorted(([*map(int, input().split())] for i in range(n)))
c = sum(a[0])
t = a[0][1]
for w in a[1:]:
	t += w[1]
	if w == a[-1] or sum(w) > c:
		t += max(w[0] - c, 0)
		c = sum(w)
print(t)


import sys
from sys import stdin
n = int(stdin.readline())
ans = 0
ac = []
LAC = []
RAC = []
for i in range(n):
	(a, c) = map(int, stdin.readline().split())
	ans += c
	ac.append((a, c))
	LAC.append((a, c))
LAC.sort()
nans1 = 0
nmax = LAC[0][0] + LAC[0][1]
for ac in LAC:
	(a, c) = ac
	if nmax < a:
		nans1 += a - nmax
	nmax = max(nmax, a + c)
print(ans + nans1)


from sys import stdin, stdout

def travelling_salesman(n, ac_a):
	ac_a.sort()
	pre = 0
	lmax = ac_a[0][0] + ac_a[0][1]
	r = ac_a[0][1]
	for i in range(1, n):
		if lmax < ac_a[i][0] + ac_a[i][1]:
			pre = i
			r += max(0, ac_a[i][0] - lmax)
			lmax = ac_a[i][0] + ac_a[i][1]
		r += ac_a[i][1]
	if pre != n - 1:
		r += max(0, ac_a[n - 1][0] - lmax)
	return r
n = int(stdin.readline())
ac_a = []
for _ in range(n):
	(a, c) = map(int, stdin.readline().split())
	ac_a.append([a, c])
r = travelling_salesman(n, ac_a)
stdout.write(str(r) + '\n')


import sys
input = sys.stdin.readline
import bisect
n = int(input())
seg_el = 1 << (n + 1).bit_length()
SEG = [1 << 60] * (2 * seg_el)

def getvalue(n, seg_el):
	i = n + seg_el
	ANS = 1 << 60
	ANS = min(SEG[i], ANS)
	i >>= 1
	while i != 0:
		ANS = min(SEG[i], ANS)
		i >>= 1
	return ANS

def updates(l, r, x):
	L = l + seg_el
	R = r + seg_el
	while L < R:
		if L & 1:
			SEG[L] = min(x, SEG[L])
			L += 1
		if R & 1:
			R -= 1
			SEG[R] = min(x, SEG[R])
		L >>= 1
		R >>= 1
updates(0, 1, 0)
A = []
SUM = 0
for i in range(n):
	(a, b) = map(int, input().split())
	SUM += b
	A.append((a, b))
A.sort()
for i in range(n):
	(a, b) = A[i]
	x = bisect.bisect(A, (a + b, 1000000005))
	now = getvalue(i, seg_el)
	updates(i + 1, x, now)
	if x < n:
		updates(x, x + 1, now + A[x][0] - a - b)
print(getvalue(n - 1, seg_el) + SUM)


import sys
from bisect import bisect_left
input = sys.stdin.readline

def solve():
	n = int(input())
	a = [tuple(map(int, input().split())) for i in range(n)]
	a.sort()
	c = a[0][0]
	r = 0
	for i in range(len(a)):
		if a[i][0] > c:
			r += a[i][0] - c
		r += a[i][1]
		c = max(c, a[i][0] + a[i][1])
	print(r)
solve()


import sys, io, os
try:
	Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
except:
	Z = lambda : sys.stdin.readline().encode()
n = int(Z())
a = []
for _ in range(n):
	a.append(tuple(map(int, Z().split())))
a.sort()
c = a[0][0] + a[0][1]
t = a[0][1]
for p in range(1, n):
	t += a[p][1]
	v = a[p][0] + a[p][1]
	if v > c or p == n - 1:
		d = a[p][0] - c
		if d > 0:
			t += d
		c = v
print(t)


n = int(input())
price = []
total = 0
for i in range(n):
	(a, c) = map(int, input().split())
	price.append((a, a + c))
	total = total + c
price.sort()
current = price[0][0]
for (i, j) in price:
	total = total + max(0, i - current)
	current = max(current, j)
print(total)


from collections import defaultdict
from itertools import accumulate
from bisect import bisect_left
from collections import deque
import sys
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353
n = int(input())
A = []
ans = 0
for i in range(n):
	(tmpa, tmpc) = map(int, input().split())
	A.append([tmpa, tmpc])
	ans += tmpc
A = sorted(A)
mx = A[0][0] + A[0][1]
for i in range(n):
	ans += max(0, A[i][0] - mx)
	mx = max(mx, A[i][0] + A[i][1])
print(ans)