Alexey is travelling on a train. Unfortunately, due to the bad weather, the train moves slower that it should!

Alexey took the train at the railroad terminal. Let's say that the train starts from the terminal at the moment $0$. Also, let's say that the train will visit $n$ stations numbered from $1$ to $n$ along its way, and that Alexey destination is the station $n$.

Alexey learned from the train schedule $n$ integer pairs $(a_i, b_i)$ where $a_i$ is the expected time of train's arrival at the $i$-th station and $b_i$ is the expected time of departure.

Also, using all information he has, Alexey was able to calculate $n$ integers $tm_1, tm_2, \dots, tm_n$ where $tm_i$ is the extra time the train need to travel from the station $i - 1$ to the station $i$. Formally, the train needs exactly $a_i - b_{i-1} + tm_i$ time to travel from station $i - 1$ to station $i$ (if $i = 1$ then $b_0$ is the moment the train leave the terminal, and it's equal to $0$).

The train leaves the station $i$, if both conditions are met:

it's on the station for at least $\left\lceil \frac{b_i - a_i}{2} \right\rceil$ units of time (division with ceiling);

current time $\ge b_i$.

Since Alexey spent all his energy on prediction of time delays, help him to calculate the time of arrival at the station $n$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($1 \le n \le 100$) — the number of stations.

Next $n$ lines contain two integers each: $a_i$ and $b_i$ ($1 \le a_i < b_i \le 10^6$). It's guaranteed that $b_i < a_{i+1}$.

Next line contains $n$ integers $tm_1, tm_2, \dots, tm_n$ ($0 \le tm_i \le 10^6$).


-----Output-----

For each test case, print one integer — the time of Alexey's arrival at the last station.


-----Examples-----

Input
2
2
2 4
10 12
0 2
5
1 4
7 8
9 10
13 15
19 20
1 2 3 4 5
Output
12
32


-----Note-----

In the first test case, Alexey arrives at station $1$ without any delay at the moment $a_1 = 2$ (since $tm_1 = 0$). After that, he departs at moment $b_1 = 4$. Finally, he arrives at station $2$ with $tm_2 = 2$ extra time, or at the moment $12$.

In the second test case, Alexey arrives at the first station with $tm_1 = 1$ extra time, or at moment $2$. The train, from one side, should stay at the station at least $\left\lceil \frac{b_1 - a_1}{2} \right\rceil = 2$ units of time and from the other side should depart not earlier than at moment $b_1 = 4$. As a result, the trains departs right at the moment $4$.

Using the same logic, we can figure out that the train arrives at the second station at the moment $9$ and departs at the moment $10$; at the third station: arrives at $14$ and departs at $15$; at the fourth: arrives at $22$ and departs at $23$. And, finally, arrives at the fifth station at $32$.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
from math import ceil
for _ in range(int(input())):
	n = int(input())
	(a, b) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(1, n + 1):
		(a[i], b[i]) = list(map(int, input().split()))
	tm = [0] + list(map(int, input().split()))
	travel_time = 0
	dep = 0
	for i in range(1, n):
		travel_time = dep + a[i] - b[i - 1] + tm[i]
		dep = max(b[i], travel_time + ceil((b[i] - a[i]) / 2))
	travel_time = dep + a[n] - b[n - 1] + tm[n]
	print(travel_time)


for z in range(int(input())):
	n = int(input())
	a = [[0, 0]]
	for i in range(n):
		a.append(list(map(int, input().split())))
	tm = list(map(int, input().split()))
	t = 0
	for i in range(1, n + 1):
		t += a[i][0] - a[i - 1][1] + tm[i - 1]
		if i != n:
			t = max(a[i][1], t - (a[i][0] - a[i][1]) // 2)
	print(t)


from math import ceil
t = int(input())
while t:
	t -= 1
	n = int(input())
	ab = []
	for i in range(n):
		(a, b) = map(int, input().split())
		ab.append([a, b])
	tm = list(map(int, input().split()))
	(enter, out, min_stay, diff) = (0, 0, 0, ab[0][0])
	for (i, [a, b]) in enumerate(ab):
		if i > 0:
			diff = a - ab[i - 1][1]
		enter = out + diff + tm[i]
		min_stay = ceil((b - a) / 2)
		out = max(b, enter + min_stay)
	print(enter)


t = int(input())
for _ in range(t):
	l = list()
	waits = list()
	times = list()
	n = int(input())
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
		wait = (b - a + 1) // 2
		waits.append(wait)
	times = list(map(int, input().split()))
	current = 0
	for j in range(n):
		if j == 0:
			current = l[0][0] + times[0]
		else:
			current += times[j]
		if j == n - 1:
			print(current)
			break
		if current + waits[j] > l[j][1]:
			current += waits[j]
		else:
			current = l[j][1]
		current += l[j + 1][0] - l[j][1]


t = int(input())
import math
while t:
	t -= 1
	n = int(input())
	ques = []
	ans = []
	ans.append(0)
	for i in range(n):
		(x, y) = map(int, input().strip().split())
		ques.append(x)
		ans.append(y)
	val = list(map(int, input().strip().split()))
	num = 0
	for j in range(n - 1):
		correct = num + val[j] + ques[j] - ans[j]
		num = max(correct + math.ceil((ans[j + 1] - ques[j]) / 2), ans[j + 1])
	correct = num + val[-1] + ques[-1] - ans[-2]
	print(correct)


import math, sys
t = int(sys.stdin.readline())
while t:
	t -= 1
	n = int(sys.stdin.readline())
	ta = []
	tb = []
	for lm in range(0, n):
		(a, b) = map(int, sys.stdin.readline().split())
		ta.append(a)
		tb.append(b)
	tm = list(map(int, sys.stdin.readline().split()))
	dt = 0
	for i in range(n):
		if i == 0:
			ct = dt + ta[i] + tm[i]
		else:
			ct = dt + ta[i] + tm[i] - tb[i - 1]
		dt = max(ct + math.ceil((tb[i] - ta[i]) / 2), tb[i])
	print(ct)


from math import ceil
t = int(input())
for _ in range(t):
	n = int(input())
	(a, b) = ([], [])
	for no in range(n):
		(ai, bi) = list(map(int, input().split()))
		a.append(ai)
		b.append(bi)
	b = [0] + b
	tm = list(map(int, input().split()))
	cur_time = 0
	for i in range(n):
		cur_time += a[i] - b[i] + tm[i]
		diff = ceil((b[i + 1] - a[i]) / 2)
		if i == n - 1:
			break
		cur_time = max(b[i + 1], cur_time + diff)
	print(cur_time)


import math
for t in range(int(input())):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
	delay = [int(i) for i in input().split()]
	d = 0
	for i in range(n - 1):
		d += delay[i]
		x = math.ceil((b[i] - a[i]) / 2)
		if b[i] <= d + a[i] + x:
			d = d - (b[i] - a[i] - x)
	print(a[n - 1] + d + delay[n - 1])


import math
tcase = int(input())
res = []
while tcase > 0:
	stationNo = int(input())
	iterVal = 0
	strTemp = '0 0 '
	while iterVal < stationNo:
		strX = input()
		strTemp += strX + ' '
		iterVal += 1
	time_list = strTemp.split()
	timeschx = list(map(int, time_list))
	strDelay = input()
	delay_list = strDelay.split()
	timedelayx = list(map(int, delay_list))
	currtime = 0
	iterVal = 0
	while iterVal < stationNo:
		currtime += timeschx[iterVal * 2 + 2] - timeschx[iterVal * 2 + 1] + timedelayx[iterVal]
		if iterVal < stationNo - 1:
			if currtime > timeschx[iterVal * 2 + 2]:
				diff = math.ceil((timeschx[iterVal * 2 + 3] - timeschx[iterVal * 2 + 2]) / 2)
				if diff + currtime > timeschx[iterVal * 2 + 3]:
					currtime += diff
				else:
					currtime = timeschx[iterVal * 2 + 3]
			else:
				currtime = timeschx[iterVal * 2 + 3]
		iterVal += 1
	res.append(currtime)
	tcase -= 1
for x in res:
	print(x)


from collections import defaultdict
from collections import deque
for _ in range(int(input())):
	n = int(input())
	(a, b) = ([], [])
	for i in range(n):
		(a_i, b_i) = (int(i) for i in input().split())
		a.append(a_i)
		b.append(b_i)
	tm = [int(i) for i in input().split()]
	for i in range(n):
		if i == 0:
			tm[i] += a[i]
		else:
			tm[i] += a[i] - b[i - 1]
	t = 0
	for i in range(n):
		arrived = t + tm[i]
		t1 = arrived + (b[i] - a[i] + 1) // 2
		t2 = b[i]
		if t1 < t2:
			departed = t2
		else:
			departed = t1
		t = departed
	print(arrived)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		ab = list(map(int, input().split()))
		arr.append((ab[0], ab[1]))
	delays = list(map(int, input().split()))
	arrival = 0
	for i in range(n):
		if i == 0:
			arrival += arr[i][0] + delays[i]
		else:
			arrival += arr[i][0] - arr[i - 1][1] + delays[i]
		if i != n - 1:
			wait = math.ceil((arr[i][1] - arr[i][0]) / 2)
			arrival += wait
			if arrival < arr[i][1]:
				arrival = arr[i][1]
	print(arrival)


import math
for i in range(int(input())):
	n = int(input())
	d = []
	for i in range(n):
		d.append([int(x) for x in input().split()])
	c = [int(x) for x in input().split()]
	t = c[0]
	t = t + d[0][0]
	for i in range(n - 1):
		t += math.ceil((d[i][1] - d[i][0]) / 2)
		if t >= d[i][1]:
			pass
		else:
			t = d[i][1]
		t = t + d[i + 1][0] - d[i][1] + c[i + 1]
	print(t)


import math
for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
	t = list(map(int, input().split()))
	(b0, b) = (0, 0)
	for i in range(n):
		a = b
		a += t[i] + (l[i][0] - b0)
		st = math.ceil((l[i][1] - l[i][0]) / 2)
		b = a + st
		if b < l[i][1]:
			b = l[i][1]
		b0 = l[i][1]
	print(a)


import math
import sys
import collections
import bisect
import time

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

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

def get_string():
	return sys.stdin.readline().strip()
for t in range(int(input())):
	n = int(input())
	time = []
	for i in range(n):
		time.append(get_list())
	arr = get_list()
	ans = 0
	prev = 0
	for i in range(n):
		(a, b) = time[i]
		arrival = a + arr[i] + prev
		min_stop = math.ceil((b - a) / 2)
		departure = max(arrival + min_stop, b)
		prev = departure - b
		if i == n - 1:
			print(arrival)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	time = []
	wait = []
	for i in range(n):
		time.append(list(map(int, input().split())))
		wait.append((time[i][1] - time[i][0] + 1) // 2)
	tm = list(map(int, input().split()))
	time.append([0, 0])
	now = 0
	for i in range(n - 1):
		ai = time[i][0]
		bi = time[i][1]
		now += tm[i] + ai - time[i - 1][1]
		if now > ai:
			now = bi if now + wait[i] < bi else now + wait[i]
		else:
			now += bi - ai
	print(now + tm[n - 1] + time[n - 1][0] - time[n - 2][1])


for _ in range(0, int(input())):
	n = int(input())
	s = []
	for i in range(0, n):
		s.append(list(map(int, input().split())))
	times = list(map(int, input().split()))
	flag = 0
	res = 0
	for i in range(0, n):
		(a, b) = s[i]
		flag += a - res + times[i]
		if i < n - 1:
			flag = max(flag + (0 - (a - b) // 2), b)
		res = b
	print(flag)


import math
for _ in range(int(input())):
	n = int(input())
	a = []
	b = [0]
	for i in range(n):
		(ai, bi) = list(map(int, input().split()))
		a.append(ai)
		b.append(bi)
	tm = list(map(int, input().split()))
	time = 0
	for i in range(n):
		time += a[i] - b[i] + tm[i]
		if i < n - 1:
			time = max(b[i + 1], time + math.ceil((b[i + 1] - a[i]) / 2))
	print(time)


for _ in range(0, int(input())):
	n = int(input())
	s = []
	for i in range(0, n):
		s.append(list(map(int, input().split())))
	times = list(map(int, input().split()))
	t = 0
	bp = 0
	for i in range(0, n):
		(a, b) = s[i]
		t += a - bp + times[i]
		if i < n - 1:
			t = max(t + (0 - (a - b) // 2), b)
		bp = b
	print(t)


import math

def comp_travel_times(deps):
	times = [0] * len(deps)
	dep = 0
	for i in range(len(deps)):
		times[i] = deps[i][0] - dep
		dep = deps[i][1]
	return times

def solve_problem(n, deps, tms):
	travel_times = comp_travel_times(deps)
	t = 0
	for i in range(n):
		arr = t + travel_times[i] + tms[i]
		if i == n - 1:
			print(arr)
		min_stay = math.ceil((deps[i][1] - deps[i][0]) / 2)
		if deps[i][1] - arr <= min_stay:
			arr += min_stay
		else:
			arr = deps[i][1]
		t = arr

def solve():
	t = int(input())
	for i in range(0, t):
		n = int(input())
		deps = []
		for j in range(n):
			x = input().split()
			ai = int(x[0])
			bi = int(x[1])
			deps.append((ai, bi))
		tms = [int(x) for x in input().split()]
		solve_problem(n, deps, tms)
solve()


def train():
	n = int(input())
	aibi_list = [0, 0]
	for i in range(n):
		aibi_list = aibi_list + int_split()
	tmn_list = int_split()
	time = 0
	for i in range(n):
		stop_time = max((aibi_list[2 * i + 1] - aibi_list[2 * i] + 1) // 2, aibi_list[2 * i + 1] - time)
		time = time + stop_time + aibi_list[2 * i + 2] - aibi_list[2 * i + 1] + tmn_list[i]
	return time

def int_split():
	str1 = input()
	list1 = str1.split()
	for i in range(len(list1)):
		list1[i] = int(list1[i])
	return list1
t = int(input())
for i in range(t):
	time = train()
	print(time)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = []
	b = []
	for i in range(0, n):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
	tm = list(map(int, input().split()))
	ans = a[0] + tm[0]
	for i in range(n - 1):
		x = max(b[i], ans + int((b[i] - a[i] + 1) / 2))
		ans = x + a[i + 1] - b[i] + tm[i + 1]
	print(ans)


test = int(input())
for t in range(test):
	n = int(input())
	a1 = []
	b1 = []
	for i in range(n):
		(ai, bi) = map(int, input().split())
		a1.append(ai)
		b1.append(bi)
	tma = list(map(int, input().split()))
	t = a1[0] + tma[0]
	for i in range(n - 1):
		dep = max(b1[i], t + (b1[i] - a1[i] + 1) // 2)
		t = dep + a1[i + 1] - b1[i] + tma[i + 1]
	print(t)


t = int(input())
for i in range(1, t + 1):
	n = int(input())
	ai = [0]
	bi = [0]
	for i in range(n):
		(a, b) = list(map(int, input().split()))
		ai.append(a)
		bi.append(b)
	ts = list(map(int, input().split()))
	time = 0
	for i in range(1, n + 1):
		arrival = time + (ai[i] - bi[i - 1]) + ts[i - 1]
		departure = max(bi[i], arrival + (bi[i] - ai[i] + 1) // 2)
		time = departure
	print(arrival)


import math
t = int(input())
for test in range(0, t):
	n = int(input())
	a = []
	b = []
	for i in range(0, n):
		ab = input().split(' ')
		a.append(int(ab[0]))
		b.append(int(ab[1]))
	tm = [int(i) for i in input().split(' ')]
	curr_time = 0
	for i in range(0, n):
		if i == 0:
			arival = curr_time + a[i] + tm[i]
		else:
			arival = curr_time + a[i] - b[i - 1] + tm[i]
		if i == n - 1:
			print(arival)
			break
		stay = math.ceil((b[i] - a[i]) / 2)
		dept = max(b[i], arival + stay)
		curr_time = dept


def solve():
	n = int(input())
	timetable = []
	for _ in range(n):
		(a, b) = input().split()
		timetable.append((int(a), int(b)))
	delays = [int(x) for x in input().split()]
	time = timetable[0][0] + delays[0]
	for i in range(n - 1):
		min_stay = (-timetable[i][0] + timetable[i][1] + 1) // 2
		departure = max(time + min_stay, timetable[i][1])
		time = departure + delays[i + 1] + timetable[i + 1][0] - timetable[i][1]
	print(time)
T = int(input())
for t in range(T):
	solve()


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	stations = [list(map(int, input().split())) for _ in range(n)]
	extra_time = [int(char) for char in input().split()]
	cur_time = extra_time[0] + stations[0][0]
	for (idx, (ex_arrival, ex_depart)) in enumerate(stations[:-1]):
		station_waiting_time = math.ceil((ex_depart - ex_arrival) / 2)
		if ex_depart - cur_time >= station_waiting_time:
			depart_time = ex_depart
		else:
			depart_time = cur_time + station_waiting_time
		cur_time = depart_time + stations[idx + 1][0] - ex_depart + extra_time[idx + 1]
	return cur_time
for _ in range(int(input())):
	print(solve())


import math
import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		ans = 0
		a = []
		b = []
		for i in range(n):
			(a_i, b_i) = map(int, input().split())
			a.append(a_i)
			b.append(b_i)
		tm = list(map(int, input().split()))
		b_pred = 0
		for i in range(n):
			(a_i, b_i) = (a[i], b[i])
			tm_i = tm[i]
			ans += a_i - b_pred + tm_i
			if i < n - 1:
				if math.ceil((b_i - a_i) / 2) <= b_i - ans:
					ans = b_i
					b_pred = b_i
				else:
					ans = ans + math.ceil((b_i - a_i) / 2)
					b_pred = b_i
		print(ans)
main()


t = int(input())
for g in range(t):
	n = int(input())
	a = []
	b = []
	tm = []
	for i in range(n):
		(f, s) = map(int, input().split())
		a.append(f)
		b.append(s)
	tm = list(map(int, input().split()))
	vp = 0
	vo = 0
	for i in range(n):
		if i == 0:
			vp = a[0] + tm[0]
		else:
			vp = vo + a[i] - b[i - 1] + tm[i]
		vo = max(b[i], vp + (b[i] - a[i] + 1) // 2)
	print(vp)


import math

def func(t):
	for i in range(t):
		n = int(input())
		a = [0]
		b = [0]
		for j in range(n):
			temp = [int(q) for q in input().split()]
			a.append(temp[0])
			b.append(temp[1])
		tm = [int(j) for j in input().split()]
		sar = 0
		for j in range(1, n + 1):
			prib = a[j] + tm[j - 1] + sar
			if j == n:
				print(prib)
			stoit = math.ceil((b[j] - a[j]) / 2)
			otb = max(prib + stoit, b[j])
			sar = otb - b[j]
t = int(input())
func(t)


import math

def alexey_and_train(n, t, tm):
	arr = 0
	halt = 0
	for i in range(1, n + 1):
		arr += halt
		arr += t[i][0] - t[i - 1][1] + tm[i]
		halt = max(math.ceil((t[i][1] - t[i][0]) / 2), t[i][1] - arr)
	print(arr)
tc = int(input().strip())
for i in range(tc):
	n = int(input().strip())
	t = [[0, 0]]
	for j in range(n):
		t.append(list(map(int, input().strip().split())))
	tm = [0]
	tm.extend(list(map(int, input().strip().split())))
	alexey_and_train(n, t, tm)


from math import ceil
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(t_a, t_b) = map(int, input().split())
		a.append(t_a)
		b.append(t_b)
	tm = list(map(int, input().split()))
	time = 0
	for i in range(n - 1):
		if i == 0:
			time += a[i] + tm[i]
		else:
			time += a[i] - b[i - 1] + tm[i]
		wait = max(b[i] - time, 0)
		time += max(wait, ceil((b[i] - a[i]) / 2))
	if n == 1:
		time = a[0] + tm[0]
	else:
		time += a[n - 1] - b[n - 2] + tm[n - 1]
	print(time)


def zip_sorted(a, b):
	(a, b) = zip(*sorted(zip(a, b)))
	sorted(zip(a, b), key=lambda x: x[1])
	return (a, b)

def number_to_list(a):
	b = []
	while a >= 1:
		c = a % 10
		a = int(a / 10)
		b.append(c)
	return list(reversed(b))

def str_list_to_int_list(a):
	a = list(map(int, a))
	return a

def make_1d_array(n, inti=0):
	a = [inti for _ in range(n)]
	return a

def make_2d_array(n, m, inti=0):
	a = [[inti for _ in range(m)] for _ in range(n)]
	return a

def make_3d_array(n, m, k, inti=0):
	a = [[[inti for _ in range(k)] for _ in range(m)] for _ in range(n)]
	return a

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
S = lambda : list(map(str, input()))
(t,) = I()
for t1 in range(t):
	(n,) = I()
	a = [0] * n
	b = [0] * n
	for i in range(n):
		(a[i], b[i]) = I()
	t = I()
	curr = 0
	prev = 0
	for i in range(len(a)):
		time_rq = a[i] - prev + t[i]
		curr += time_rq
		if i == n - 1:
			break
		wait = max(b[i] - curr, int((b[i] - a[i] + 1) / 2))
		curr += wait
		prev = b[i]
	print(curr)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
	tm = list(map(int, input().split()))
	ans = 0
	x = l[0][0]
	y = tm[0]
	dpt = x + y
	pos = ceil((l[0][1] - l[0][0]) / 2)
	dpt = max(l[0][1], x + y + pos)
	ans = dpt
	arr = x + y
	for i in range(1, n):
		x = l[i][0]
		y = tm[i]
		pos = ceil((l[i][1] - l[i][0]) / 2)
		ans = ans + (l[i][0] - l[i - 1][1]) + y
		arr = ans
		dpt = max(l[i][1], arr + pos)
		ans = dpt
	print(arr)


from math import ceil
T = int(input())
for t in range(T):
	n = int(input())
	td = []
	for nn in range(n):
		x = list(map(int, input().split()))
		td.append(x)
	tm = list(map(int, input().split()))
	c = 0
	d = 0
	for i in range(n):
		(a, b) = td[i]
		extra_time = tm[i]
		if i == 0:
			upper = ceil((b - a) / 2)
			c = a + extra_time
			d = c + upper
			if b > d:
				d = b
		if i > 0:
			extra_time = td[i][0] - td[i - 1][1] + tm[i]
			upper = ceil((b - a) / 2)
			c = d + extra_time
			d = c + upper
			if b > d:
				d = b
	print(c)


import os
import sys
import math

def main():
	fastReadInt = sys.stdin.buffer.readline

	def fastReadStr():
		return sys.stdin.buffer.readline().decode('utf-8').strip()

	def fastWrite(ans):
		return sys.stdout.buffer.write(str(str(ans) + '\n').encode('utf-8'))

	def fastWriteList(ans):
		return sys.stdout.write(' '.join(map(str, ans)) + '\n')
	DEBUG = 'DEBUG' in os.environ

	def debug(*args):
		if DEBUG:
			print('>', *args)

	def solution(stations, timings):
		answer = 0
		delay = 0
		for stationIdx in range(0, len(stations)):
			station = stations[stationIdx]
			timing = timings[stationIdx]
			minimumWaitTime = math.ceil((station[1] - station[0]) / 2)
			arriveTime = station[0] + timing + delay
			answer = arriveTime
			realDepartTime = max(arriveTime + minimumWaitTime, station[1])
			delay = realDepartTime - station[1]
		fastWrite(answer)
	for t in range(int(fastReadInt())):
		stationsLength = int(fastReadInt())
		stations = [None] * stationsLength
		for sIdx in range(stationsLength):
			stations[sIdx] = list(map(int, fastReadInt().split()))
		timings = list(map(int, fastReadInt().split()))
		solution(stations, timings)
main()


t = int(input())
ans = []
for i in range(t):
	a = [0]
	b = [0]
	n = int(input())
	for j in range(n):
		(ai, bi) = map(int, input().split())
		a.append(ai)
		b.append(bi)
	time = 0
	tm = [0]
	tm += [int(x) for x in input().split()]
	diff = 0
	for k in range(1, n + 1):
		time += a[k] - b[k - 1] + tm[k]
		if k != n:
			time += (b[k] - a[k] + 1) // 2
			if time < b[k]:
				time += b[k] - time
		else:
			continue
	ans.append(time)
for _ in range(len(ans)):
	print(ans[_])


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = sys.maxsize

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		(x, y) = get_ints()
		a.append([x, y])
	t = get_array()
	cur_arv = a[0][0] + t[0]
	cur_dep = 0
	for i in range(n - 1):
		rest = math.ceil((a[i][1] - a[i][0]) / 2)
		if cur_arv + rest < a[i][1]:
			cur_dep = a[i][1]
		else:
			cur_dep = cur_arv + rest
		cur_arv = cur_dep + a[i + 1][0] - a[i][1] + t[i + 1]
	print(cur_arv)


import math

def temp(t):
	for i in range(t):
		n = int(input())
		a = [0]
		b = [0]
		for j in range(n):
			tfun = [int(aq) for aq in input().split()]
			a.append(tfun[0])
			b.append(tfun[1])
		qwertm = [int(j) for j in input().split()]
		raqwer = 0
		for j in range(1, n + 1):
			prib = a[j] + qwertm[j - 1] + raqwer
			if j == n:
				print(prib)
			stoit = math.ceil((b[j] - a[j]) / 2)
			qazx = max(prib + stoit, b[j])
			raqwer = qazx - b[j]
temp(int(input()))


import math
t = int(input())
while t > 0:
	n = int(input())
	a = list()
	b = list()
	for i in range(n):
		x = input()
		a.append(int(x.split()[0]))
		b.append(int(x.split()[1]))
	tmi = input()
	timeDiff = list()
	tm = tmi.split()
	diff = list()
	for i in range(n):
		diff.append(math.ceil((b[i] - a[i]) / 2))
	a[0] += int(tm[0])
	for i in range(0, n - 1):
		timeDiff.append(a[i + 1] - b[i] + int(tm[i + 1]))
	actualArrival = list()
	for i in range(n - 1):
		b[i] = max(b[i], a[i] + diff[i])
		a[i + 1] = b[i] + timeDiff[i]
	print(a[n - 1])
	t -= 1


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
t = int(wtf[0])
k = 1
for i in range(t):
	n = int(wtf[i + k])
	A = []
	B = [0]
	for j in range(n):
		(a, b) = map(int, wtf[i + k + j + 1].split())
		A.append(a)
		B.append(b)
	T = list(map(int, wtf[i + k + n + 1].split()))
	ct = 0
	lt = 0
	for l in range(n):
		td = A[l] - B[l] + T[l]
		ct += td
		st = math.ceil((B[l + 1] - A[l]) / 2)
		lt = ct
		if ct < B[l + 1] and B[l + 1] - ct >= st:
			ct = B[l + 1]
		else:
			ct += st
	print(lt)
	k += n + 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = [[0, 0]]
	for j in range(n):
		(a, b) = map(int, input().split())
		l.append([a, b])
	tm = list(map(int, input().split()))
	time_taken = 0
	for j in range(1, n):
		time_taken += l[j][0] - l[j - 1][1] + tm[j - 1]
		val1 = math.ceil((l[j][1] - l[j][0]) / 2)
		val2 = l[j][1] - time_taken
		if val2 <= 0:
			time_taken += val1
		else:
			time_taken = max(l[j][1], time_taken + val1)
	time_taken += l[-1][0] - l[-2][1] + tm[-1]
	print(time_taken)


import math
import sys
from collections import *

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

def cstr():
	return list(map(str, input().split(' ')))

def solve():
	n = int(input())
	lst = []
	for i in range(n):
		lst.append(cint())
	tm = cint()
	currt = 0
	for i in range(n):
		(a, b) = lst[i]
		if i == 0:
			currt += a + tm[i]
			if i == n - 1:
				print(currt)
				return
			diff = int((b - a + 1) / 2)
			currt += diff
			currt = max(b, currt)
		else:
			(pa, pb) = lst[i - 1]
			currt += a - pb + tm[i]
			if i == n - 1:
				print(currt)
				return
			diff = int((b - a + 1) / 2)
			currt += diff
			currt = max(b, currt)
t = int(input())
while t != 0:
	solve()
	t -= 1


import sys
input = sys.stdin.readline
import math
for _ in range(int(input().strip())):
	n = int(input().strip())
	a = []
	b = []
	for _ in range(n):
		(a1, b1) = map(int, input().strip().split(' '))
		a.append(a1)
		b.append(b1)
	t = list(map(int, input().strip().split(' ')))
	o = 0
	cd = 0
	for i in range(n - 1):
		cd += t[i]
		cd = max(b[i], a[i] + cd + (b[i] + 1 - a[i]) // 2) - b[i]
	print(a[-1] + cd + t[-1])


for _ in range(int(input())):
	n = int(input())
	curr = 0
	a = []
	b = []
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
	t = list(map(int, input().split()))
	for i in range(n):
		if i == 0:
			curr += t[i] + a[i]
		else:
			curr += t[i] + a[i] - b[i - 1]
		temp = (b[i] - a[i]) / 2
		if int(temp) == temp:
			temp = int(temp)
		else:
			temp = int(temp) + 1
		if curr + temp >= b[i] and i != n - 1:
			curr += temp
		elif i != n - 1:
			curr = b[i]
	print(curr)


import math
test_cases = int(input())

def calculate(ab, tm):
	t = 0
	for i in range(len(tm)):
		t += tm[i]
		if i == 0:
			t += ab[i][0]
		if i == len(tm) - 1:
			print(t)
			return
		t += math.ceil((ab[i][1] - ab[i][0]) / 2)
		if ab[i][1] > t:
			t = ab[i][1]
		t = t - ab[i][1] + ab[i + 1][0]
for _ in range(test_cases):
	tm = []
	ab = []
	n = int(input())
	for i in range(n):
		ab_str = input().split(' ')
		ab_int = [int(a) for a in ab_str]
		ab.append(ab_int)
	tm_str = input().split(' ')
	tm = [int(t) for t in tm_str]
	calculate(ab, tm)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def modInverse(b):
	g = gcd(b, mod)
	if g != 1:
		return -1
	else:
		return pow(b, mod - 2, mod)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	n = int(inp())
	arr = []
	for i in range(n):
		(x, y) = sep()
		arr.append((x, y))
	tm = lis()
	curr = tm[0] + arr[0][0]
	for i in range(n - 1):
		stay = ceil((arr[i][1] - arr[i][0]) / 2)
		curr += stay
		if curr < arr[i][1]:
			curr = arr[i][1]
		if i != n - 1:
			curr += tm[i + 1] + arr[i + 1][0] - arr[i][1]
	print(curr)
testcase(int(inp()))


from math import *
for iii in range(int(input())):
	n = int(input())
	arr1 = []
	arr2 = []
	for i in range(n):
		(x, y) = map(int, input().split())
		arr1.append(x)
		arr2.append(y)
	arrm = list(map(int, input().split()))
	a = []
	b = []
	a.append(arr1[0] + arrm[0])
	b.append(max(arr2[0], a[0] + ceil((arr2[0] - arr1[0]) / 2)))
	for i in range(1, n):
		a.append(arr1[i] + arrm[i] + b[i - 1] - arr2[i - 1])
		b.append(max(arr2[i], a[i] + ceil((arr2[i] - arr1[i]) / 2)))
	print(a[-1])


import math
for testcase in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		li = [int(x) for x in input().split()]
		temp = math.ceil((li[1] - li[0]) / 2)
		li.append(temp)
		arr.append(li)
	delay = [int(x) for x in input().split()]
	if n == 1:
		temp = arr[0][0] + delay[0]
		print(temp)
		continue
	for i in range(n - 1):
		if i == 0:
			temp = arr[i][0] + delay[i] + arr[i][2]
			temp = max(temp, arr[i][1])
		else:
			temp += arr[i][0] - arr[i - 1][1]
			temp = max(temp, arr[i][0])
			temp += delay[i] + arr[i][2]
			temp = max(temp, arr[i][1])
	temp += arr[-1][0] - arr[-2][1]
	temp = max(temp, arr[-1][0])
	print(temp + delay[-1])


import math
for _ in range(int(input())):
	n = int(input())
	li = []
	for i in range(n):
		(a, b) = map(int, input().split())
		li.append((a, b))
	x = [*map(int, input().split())]
	t = 0
	arr = 0
	dep = 0
	for i in range(n):
		if i != 0:
			t += x[i] + (li[i][0] - li[i - 1][1])
		else:
			t += x[i] + li[i][0]
		arr = t
		y = math.ceil((li[i][1] - li[i][0]) / 2)
		dep = max(t + y, li[i][1])
		t = dep
	print(arr)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	a = [0]
	b = [0]
	t = [0]
	for l in range(n):
		lis = input().split(' ')
		a.append(int(lis[0]))
		b.append(int(lis[1]))
	til = input().split(' ')
	for x in range(n):
		t.append(int(til[x]))
	time_count = a[1] + t[1]
	m = 0
	for i in range(1, n):
		m = int(ceil((b[i] - a[i]) / 2))
		if b[i] - time_count > m:
			time_count = a[i + 1] + t[i + 1]
		else:
			time_count += m + a[i + 1] + t[i + 1] - b[i]
	print(time_count)


import sys, math, os
from math import factorial, inf, gcd, pi, sqrt, ceil
from heapq import *
from functools import *
from itertools import *
from collections import *
sys.setrecursionlimit(10 ** 5)
if os.environ.get('HOME') == '/Users/clarity':
	os.chdir(os.path.dirname(os.path.abspath(__file__)))
	inp = open('A_test.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass

def line():
	return list(map(int, inp().rstrip().split()))

def fline():
	return list(map(float, inp().rstrip().split()))

def number():
	return int(inp())

def print_array(l):
	print(' '.join(list(map(str, l))))

def testcase(t):
	for p in range(t):
		solve()

def solve():
	n = number()
	ss = []
	for i in range(n):
		(a, b) = line()
		ss.append([a, b])
	t = line()
	in_time = 0
	if len(ss) >= 2:
		in_time = ss[-2][1] + t[-1]
	else:
		in_time = ss[-1][0] + t[0]
	prev_dep_delay = 0
	for i in range(n):
		at_st_s = ss[i][0]
		depart_s = ss[i][1]
		delay = t[i]
		at_st_r = at_st_s + delay + prev_dep_delay
		depart_r = max(depart_s, at_st_r + ceil((depart_s - at_st_s) / 2))
		prev_dep_delay = depart_r - depart_s
	print(at_st_r)

def main():
	testcase(number())
main()


import sys
import math
t = int(input())
for tt in range(t):
	n = int(input())
	ad = []
	for i in range(n):
		(a, d) = map(int, input().split())
		e = math.ceil((d - a) / 2)
		ad.append([a, d, e])
	tm = list(map(int, input().split()))
	it = 0
	nt = [tm[0] + ad[0][0]]
	for i in range(n - 1):
		nt.append(ad[i + 1][0] - ad[i][1] + tm[i + 1])
	it = nt[0]
	for i in range(n - 1):
		it += ad[i][2]
		if it >= ad[i][1]:
			pass
		else:
			it = ad[i][1]
		it += nt[i + 1]
	print(it)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [0]
	b = [0]
	for __ in range(n):
		(ai, bi) = map(int, input().split())
		a.append(ai)
		b.append(bi)
	tm = [0]
	tm += [int(x) for x in input().split()]
	dep = [0] * (n + 1)
	arr = [0] * (n + 1)
	for i in range(1, n + 1):
		arr[i] = dep[i - 1] + (a[i] - b[i - 1]) + tm[i]
		dep[i] = max(b[i], arr[i] + (b[i] - a[i] + 1) // 2)
	print(arr[n])


T = int(input())
for t in range(T):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(ai, bi) = map(int, input().split())
		a.append(ai)
		b.append(bi)
	tm = list(map(int, input().split()))
	t = a[0] + tm[0]
	for i in range(n - 1):
		dep = max(b[i], t + (b[i] - a[i] + 1) // 2)
		t = dep + a[i + 1] - b[i] + tm[i + 1]
	print(t)


I = lambda : [*map(int, input().split())]
for _ in ' ' * I()[0]:
	n = I()[0] + 1
	a = [0] * n
	b = [0] * n
	for i in range(1, n):
		(a[i], b[i]) = I()
	t = I()
	ans = 0
	for i in range(1, n):
		ans += a[i] - b[i - 1] + t[i - 1]
		if i < n - 1:
			ans += max(b[i] - ans, (b[i] - a[i] + 1) // 2)
	print(ans)


import math

def solve(n, sch, delays):
	(at, dt) = (0, 0)
	psdt = 0
	for (s, d) in zip(sch, delays):
		(ai, bi) = s
		at = dt + (ai - psdt) + d
		dt = max(bi, at + math.ceil((bi - ai) / 2))
		psdt = bi
	return at
t = int(input())
for _ in range(t):
	n = int(input())
	sch = []
	for n_i in range(n):
		(a, b) = map(int, input().split())
		sch.append((a, b))
	delays = list(map(int, input().split()))
	result = solve(n, sch, delays)
	print(result)


import math
t = int(input())
for i in range(t):
	n = int(input())
	(a, b, t) = ([0], [0], [])
	for j in range(n):
		(ai, bi) = list(map(int, input().split()))
		a.append(ai)
		b.append(bi)
	t = list(map(int, input().split()))
	res = 0
	stay = 0
	for j in range(n):
		res = stay + a[j + 1] - b[j] + t[j]
		stay1 = res + math.ceil((b[j + 1] - a[j + 1]) / 2)
		wait = math.ceil((a[j + 1] - b[j + 1]) / 2)
		stay2 = b[j + 1]
		stay = max(stay1, stay2)
	print(res)


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


from sys import stdin

def main():

	def input():
		N = int(next(tokens))
		A = []
		B = []
		Tm = []
		for i in range(N):
			A.append(int(next(tokens)))
			B.append(int(next(tokens)))
		for i in range(N):
			Tm.append(int(next(tokens)))
		return (N, A, B, Tm)

	def solve():
		(N, A, B, Tm) = input()
		total_delay = 0
		for i in range(N - 1):
			total_delay += Tm[i] - (B[i] - A[i]) // 2
			total_delay = max(total_delay, 0)
		print(A[N - 1] + Tm[N - 1] + total_delay)
	tokens = iter(stdin.read().split())
	T = int(next(tokens))
	for t in range(T):
		solve()
main()


tests = int(input())
for _ in range(tests):
	n = int(input())
	ab = []
	for _ in range(n):
		ab.append(list(map(int, input().split())))
	tm = list(map(int, input().split()))
	res = ab[0][0] + tm[0]
	for i in range(1, n):
		stop = (ab[i - 1][1] - ab[i - 1][0] + 1) // 2
		res = ab[i][0] - ab[i - 1][1] + max(res + stop, ab[i - 1][1]) + tm[i]
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	t = []
	ai = 0
	bi = 0
	for _ in range(n):
		inp = list(map(int, input().strip().split()))
		a.append(inp[0])
		b.append(inp[1])
	t = list(map(int, input().strip().split()))
	if (b[0] - a[0]) % 2 == 0:
		x = (b[0] - a[0]) // 2
	else:
		x = (b[0] - a[0]) // 2 + 1
	ai = a[0] + t[0]
	bi = ai + int(x)
	if b[0] > bi:
		bi = b[0]
	for i in range(1, n):
		if (b[i] - a[i]) % 2 == 0:
			x = (b[i] - a[i]) // 2
		else:
			x = (b[i] - a[i]) // 2 + 1
		ai = a[i] + t[i] - b[i - 1] + bi
		bi = ai + int(x)
		if b[i] > bi:
			bi = b[i]
	print(ai)


import math
for _ in range(int(input())):
	n = int(input())
	t = []
	for i in range(n):
		(a, b) = map(int, input().split())
		t.append([a, b])
	tm = list(map(int, input().split()))
	c = t[0][0] + tm[0]
	for i in range(n - 1):
		if t[i][0] < c:
			c += math.ceil((t[i][1] - t[i][0]) / 2) + (t[i + 1][0] - t[i][1]) + tm[i + 1]
		else:
			c += t[i][1] - t[i][0] + (t[i + 1][0] - t[i][1]) + tm[i + 1]
	print(c)


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
ans = []
tests = inp()
for _ in range(tests):
	n = inp()
	a = []
	b = []
	for _ in range(n):
		tmp = inlt()
		(tmp_a, tmp_b) = (tmp[0], tmp[1])
		a.append(tmp_a)
		b.append(tmp_b)
	tm = inlt()
	time = 0
	prev_b = 0
	for (i, t) in enumerate(tm):
		time += a[i] - prev_b + t
		if i < len(tm) - 1:
			time += max(math.ceil((b[i] - a[i]) / 2), b[i] - time)
		prev_b = b[i]
	ans.append(time)
for a in ans:
	print(a)


import math
num_cases = int(input())
for i in range(num_cases):
	n = int(input())
	stations = list()
	for case in range(n):
		stations.append(list(map(int, input().split(' '))))
	latency = list(map(int, input().split(' ')))
	arrival_time = 0
	for i in range(len(stations)):
		if i == 0:
			arrival_time += stations[i][0] + latency[i]
		else:
			arrival_time += stations[i][0] - stations[i - 1][1] + latency[i]
		if i != len(stations) - 1:
			if arrival_time > (stations[i][0] + stations[i][1]) / 2:
				arrival_time += math.ceil((stations[i][1] - stations[i][0]) / 2)
			else:
				arrival_time += stations[i][1] - arrival_time
	print(arrival_time)


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n,) = R()
	(a, b) = zip(*(R() for _ in [0] * n))
	s = 0
	for (x, y, z, w) in zip(a, b, (0, *b), R()):
		p = s + x - z + w
		s = p + max(y - x + 1 >> 1, y - p)
	print(p)


__version__ = '0.5'
__date__ = '2021-03-16'
import sys

def solve(n, a, b, delay):
	departed = 0
	for i in range(n):
		if i == 0:
			travelled = a[i]
		else:
			travelled = a[i] - b[i - 1]
		arrived = departed + travelled + delay[i]
		stay = (b[i] - a[i] + 1) // 2
		departed = max(b[i], arrived + stay)
	return arrived

def main(argv=None):
	t = int(input())
	for _ in range(t):
		n = int(input())
		(a, b) = zip(*[list(map(int, input().split())) for _ in range(n)])
		tm = list(map(int, input().split()))
		print(solve(n, a, b, tm))
	return 0
STATUS = main()
sys.exit(STATUS)


import math

def solve(p, n, tm):
	prev = 0
	for i in range(n):
		(a, b) = point[i]
		md = math.ceil((b - a) / 2)
		a += tm[i] + prev
		if i == n - 1:
			return a
		if md <= b - a:
			continue
		new_b = a + md
		prev = new_b - b
t = int(input())
for _ in range(t):
	n = int(input())
	point = []
	for i in range(n):
		point.append(list(map(int, input().split())))
	tm = list(map(int, input().split()))
	print(solve(point, n, tm))


from math import ceil

def solve():
	n = int(input())
	time = [[0, 0]]
	for _ in range(n):
		time.append(list(map(int, input().split())))
	delay = []
	delay.extend(list(map(int, input().split())))
	(arrival, prevDep) = (0, 0)
	for i in range(1, n + 1):
		travel = abs(time[i][0] - time[i - 1][1])
		arrival = prevDep + travel + delay[i - 1]
		wait = ceil(abs(time[i][0] - time[i][1]) / 2)
		prevDep = arrival + wait
		prevDep = max(prevDep, time[i][1])
	print(arrival)
t = int(input())
for _ in range(t):
	solve()


import math
for _ in range(int(input())):
	n = int(input())
	la = [0] * (n + 1)
	lb = [0] * (n + 1)
	lc = [0] * (n + 1)
	s = 0
	for i in range(1, n + 1):
		(la[i], lb[i]) = map(int, input().split())
		lc[i] = math.ceil((lb[i] - la[i]) / 2)
	t = list(map(int, input().split()))
	for i in range(1, n + 1):
		s += la[i] - lb[i - 1] + t[i - 1]
		if i != n:
			if s + lc[i] <= lb[i]:
				s = lb[i]
			else:
				s += lc[i]
	print(s)


from sys import stdin
input = stdin.readline

def ceil(c):
	if int(c) == c:
		return int(c)
	return int(c) + 1

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def floor(f):
	return int(f)

def sqrt(s):
	return s ** 0.5

def max(a, b):
	return a if a > b else b

def abs(a):
	return a if a >= 0 else -1 * a

def min(a, b):
	return a if a < b else b

def primeInRange(n):
	l = [True] * n
	for i in range(2, int(sqrt(n)) + 1):
		if l[i - 1]:
			for j in range(i + i, n + 1, i):
				l[j - 1] = False
	return l

def solve(n):
	arival = []
	d = []
	wait = []
	for i in range(n):
		(a, b) = map(int, input().split())
		arival.append(a)
		d.append(b)
		wait.append(ceil((b - a) / 2))
	tm = list(map(int, input().split()))
	late = 0
	for i in range(n):
		late += tm[i]
		arival[i] += late
		if arival[i] + wait[i] <= d[i]:
			late = 0
		else:
			late = arival[i] + wait[i] - d[i]
	return arival[n - 1]
for _ in range(int(input())):
	print(solve(int(input())))


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [0]
	b = [0]
	for j in range(n):
		(ai, bi) = map(int, input().split())
		a.append(ai)
		b.append(bi)
	tm = [int(j) for j in input().split()]
	ras = 0
	for j in range(1, n + 1):
		prib = a[j] + tm[j - 1] + ras
		if j == n:
			print(prib)
		stoit = math.ceil((b[j] - a[j]) / 2)
		otb = max(prib + stoit, b[j])
		ras = otb - b[j]


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(ai, bi) = [int(i) for i in input().strip().split()]
		a.append(ai)
		b.append(bi)
	extra_time = [int(i) for i in input().strip().split()]
	real_b = [0]
	curr_time = 0
	for i in range(n):
		if i != 0:
			time_taken = a[i] - b[i - 1] + extra_time[i]
		else:
			time_taken = a[i] + extra_time[i]
		least_time = math.ceil((b[i] - a[i]) / 2)
		if i != n - 1:
			if curr_time + time_taken + least_time >= b[i]:
				curr_time = curr_time + time_taken + least_time
			else:
				curr_time = b[i]
		else:
			curr_time = curr_time + time_taken
	print(curr_time)


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
for i in range(inp()):
	s = inp()
	(a, b) = ([], [])
	for i in range(s):
		(c, d) = invr()
		a.append(c)
		b.append(d)
	tm = inlt()
	(time, delay) = (0, 0)
	for i in range(s - 1):
		time = a[i] + tm[i] + delay
		if time + math.ceil((b[i] - a[i]) / 2) < b[i]:
			delay = 0
		else:
			delay = time + math.ceil((b[i] - a[i]) / 2) - b[i]
	arrnew = a[-1] + delay + tm[-1]
	print(arrnew)


import sys, os, io, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	aibi = []
	for i in range(n):
		(ai, bi) = map(int, input().split())
		aibi.append([ai, bi])
	tmList = list(map(int, input().split()))
	arrival = aibi[0][0] + tmList[0]
	leastTime = math.ceil((aibi[0][1] - aibi[0][0]) / 2)
	if arrival + leastTime > aibi[0][1]:
		departure = arrival + leastTime
	else:
		departure = aibi[0][1]
	for i in range(1, n):
		ai = aibi[i][0]
		bi = aibi[i][1]
		prevai = aibi[i - 1][0]
		prevbi = aibi[i - 1][1]
		leastTime = math.ceil((bi - ai) / 2)
		arrival = departure + (ai - prevbi + tmList[i])
		if arrival + leastTime > ai:
			departure = arrival + leastTime
		else:
			departure = bi
	print(arrival)


import math
for _ in range(int(input())):
	n = int(input())
	arr_dep = []
	late = 0
	arrival_time = 0
	for i in range(n):
		arr_dep.append(tuple(map(int, input().split())))
	extra_time = list(map(int, input().split()))
	for i in range(n):
		arrival_time = arr_dep[i][0] + extra_time[i] + late
		late = max(arrival_time + math.ceil((arr_dep[i][1] - arr_dep[i][0]) / 2), arr_dep[i][1]) - arr_dep[i][1]
	print(arrival_time)


from math import ceil
t = int(input())
while t:
	t -= 1
	n = int(input())
	(a, b) = ([0], [0])
	for i in range(n):
		x = [int(j) for j in input().split()]
		a.append(x[0])
		b.append(x[1])
	tm = [int(j) for j in input().split()]
	count = 0
	moment = 0
	for i in range(1, n + 1):
		time = a[i] - b[i - 1] + tm[i - 1]
		moment += time
		count += 1
		wait = ceil((b[i] - a[i]) / 2)
		depart = moment + wait
		if count == n:
			break
		if depart < b[i]:
			moment = b[i]
		else:
			moment += wait
	print(moment)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = [li() for i in range(n)]
	x = li()
	z = 0
	for i in range(n - 1):
		arrived = l[i][0] + x[i] + z
		p = arrived + ceil((l[i][1] - l[i][0]) / 2)
		if p < l[i][1]:
			left = l[i][1]
		else:
			left = p
		if left - l[i][1] < 0:
			z = 0
		else:
			z = left - l[i][1]
	pr(l[-1][0] + z + x[-1])
for _ in range(inp()):
	solve()


import math

def solve(res, n, extime):
	if n == 1:
		return extime[0] + res[0][0]
	curr = 0
	for i in range(n):
		if i == 0:
			curr = max(extime[i] + res[0][0] + math.ceil((res[i][1] - res[i][0]) / 2), res[0][1])
		elif i == n - 1:
			curr = max(curr + extime[i] + (res[i][0] - res[i - 1][1]), res[i][0])
		else:
			curr = max(max(curr + extime[i] + (res[i][0] - res[i - 1][1]), res[i][0]) + math.ceil((res[i][1] - res[i][0]) / 2), res[i][1])
	return curr
t = int(input())
for _ in range(t):
	n = int(input())
	res = []
	for i in range(n):
		res.append(list(map(int, input().split())))
	extime = list(map(int, input().split()))
	res = solve(res, n, extime)
	print(res)


import sys
import math

class DictList(dict):

	def __setitem__(self, key, value):
		try:
			self[key].append(value)
		except KeyError:
			super(DictList, self).__setitem__(key, value)
		except AttributeError:
			super(DictList, self).__setitem__(key, [self[key], value])

def fn(n, x, m):
	a = []
	b = []
	for i in range(2 * n):
		if i % 2 == 0:
			a.append(x[i])
		else:
			b.append(x[i])
	dif = []
	for i in range(n - 1):
		dif.append(a[i + 1] - b[i] + m[i + 1])
	wait = []
	for i in range(n):
		k = math.ceil((b[i] - a[i]) / 2)
		wait.append(k)
	t = 0
	i = 0
	t = m[i] + a[i]
	while i != n - 1:
		if t + wait[i] > b[i]:
			t = t + wait[i]
		else:
			t = b[i]
		t = t + dif[i]
		i = i + 1
	return t
input = sys.stdin.read()
data = list(map(int, input.split()))
t = data[0]
l = 0
for i in range(t):
	n = data[l + 1]
	x = data[l + 2:l + 2 + 2 * n]
	m = data[l + 2 + 2 * n:l + 2 + 2 * n + n]
	l = l + 1 + 3 * n
	print(fn(n, x, m))


import math

def func(n, ab, t):
	ans = ab[0][0] + t[0]
	dep = max(ab[0][1], ans + math.ceil((ab[0][1] - ab[0][0]) / 2))
	for i in range(1, n):
		(ai, bim1) = (ab[i][0], ab[i - 1][1])
		tmi = t[i]
		ans = dep + ai - bim1 + tmi
		dep = max(ab[i][1], ans + math.ceil((ab[i][1] - ab[i][0]) / 2))
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	ab = [list(map(int, input().split())) for _ in range(n)]
	t = list(map(int, input().split()))
	print(func(n, ab, t))


from collections import defaultdict, OrderedDict, Counter
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import Queue, PriorityQueue
from heapq import *
from statistics import *
from math import *
import fractions
import copy
from copy import deepcopy
import sys
import io
sys.setrecursionlimit(10000)
import math
import os
import bisect
import collections
mod = pow(10, 9) + 7
import random
from random import *
from time import time

def ncr(n, r, p=mod):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def normalncr(n, r):
	r = min(r, n - r)
	count = 1
	for i in range(n - r, n + 1):
		count *= i
	for i in range(1, r + 1):
		count //= i
	return count
inf = float('inf')
adj = defaultdict(set)
visited = defaultdict(int)

def addedge(a, b):
	adj[a].add(b)
	adj[b].add(a)

def bfs(v):
	q = Queue()
	q.put(v)
	visited[v] = 1
	while q.qsize() > 0:
		s = q.get_nowait()
		print(s)
		for i in adj[s]:
			if visited[i] == 0:
				q.put(i)
				visited[i] = 1

def dfs(v, visited):
	if visited[v] == 1:
		return
	visited[v] = 1
	print(v)
	for i in adj[v]:
		dfs(i, visited)

def reverse_bisect_right(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x > a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def reverse_bisect_left(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x >= a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

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

def get_str_list_in_int():
	return [int(i) for i in list(input())]

def get_str_list():
	return list(input())

def get_map():
	return map(int, input().split())

def input_int():
	return int(input())

def matrix(a, b):
	return [[0 for i in range(b)] for j in range(a)]

def swap(a, b):
	return (b, a)

def find_gcd(l):
	a = l[0]
	for i in range(len(l)):
		a = gcd(a, l[i])
	return a

def is_prime(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return 0
	return 1

def prime_factors(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return [i] + prime_factors(n // i)
	return [n]

def p(a):
	if type(a) == str:
		print(a + '\n')
	else:
		print(str(a) + '\n')

def ps(a):
	if type(a) == str:
		print(a)
	else:
		print(str(a))

def kth_no_not_div_by_n(n, k):
	return k + (k - 1) // (n - 1)

def forward_array(l):
	n = len(l)
	stack = []
	forward = [0] * n
	for i in range(len(l) - 1, -1, -1):
		while len(stack) and l[stack[-1]] < l[i]:
			stack.pop()
		if len(stack) == 0:
			forward[i] = len(l)
		else:
			forward[i] = stack[-1]
		stack.append(i)
	return forward

def backward_array(l):
	n = len(l)
	stack = []
	backward = [0] * n
	for i in range(len(l)):
		while len(stack) and l[stack[-1]] < l[i]:
			stack.pop()
		if len(stack) == 0:
			backward[i] = -1
		else:
			backward[i] = stack[-1]
		stack.append(i)
	return backward
nc = 'NO'
yc = 'YES'
ns = 'No'
ys = 'Yes'
t = int(input())
for i in range(t):
	n = int(input())
	a = defaultdict(int)
	b = defaultdict(int)
	for i in range(n):
		(a[i], b[i]) = get_map()
	lis = get_list()
	time = [0] * n
	for i in range(n):
		time[i] = a[i] - b[i - 1] + lis[i]
	now = 0
	for i in range(n):
		now += time[i]
		if i != n - 1:
			now += ceil((b[i] - a[i]) / 2)
			if now < b[i]:
				now = b[i]
	print(now)


import math
for _ in range(int(input())):
	n = int(input())
	A = []
	B = []
	for i in range(n):
		(a, b) = map(int, input().split())
		A.append(a)
		B.append(b)
	l = list(map(int, input().split()))
	count = l[0] + A[0]
	for i in range(n - 1):
		count = max(count + math.ceil((B[i] - A[i]) / 2), B[i])
		count += A[i + 1] - B[i] + l[i + 1]
	print(count)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	A = [[0, 0]]
	for i in range(n):
		(x, y) = map(int, input().split())
		A.append([x, y])
	B = list(map(int, input().split()))
	ans = 0
	(a, b) = (0, 0)
	for i in range(1, n + 1):
		a1 = A[i][0] - A[i - 1][1] + B[i - 1]
		a = b + a1
		b = max(A[i][1], a + (A[i][1] - A[i][0] + 1) // 2)
	print(a)


from sys import stdin, stdout
input = stdin.readline
import math
from collections import Counter, defaultdict
import bisect

def ti():
	return map(int, input().split(' '))

def tl():
	return list(map(int, input().split(' ')))
for _ in range(int(input())):
	n = int(input())
	times = []
	for i in range(n):
		(a, b) = ti()
		times.append([a, b])
	tm = tl()
	ans = 0
	traveling_time = [times[0][0] + tm[0]]
	for i in range(n - 1):
		traveling_time.append(times[i + 1][0] - times[i][1] + tm[i + 1])
	actual_times = [[0, 0]]
	for i in range(n):
		arrived = actual_times[-1][1] + traveling_time[i]
		departed = max(times[i][1], arrived + (times[i][1] - times[i][0] + 1) // 2)
		actual_times.append([arrived, departed])
	print(actual_times[-1][0])


import math
t = int(input())
for i in range(t):
	n_stations = int(input())
	ari = []
	dept = []
	for j in range(n_stations):
		time = list(map(int, input().split()))
		ari.append(time[0])
		dept.append(time[1])
	tm = list(map(int, input().split()))
	prev_time = 0
	arrival_time = 0
	for j in range(n_stations):
		if j != 0:
			travel_time = ari[j] - dept[j - 1]
		else:
			travel_time = ari[j]
		arrival_time = prev_time + travel_time + tm[j]
		wait = math.ceil(abs(ari[j] - dept[j]) / 2)
		prev_time = arrival_time + wait
		prev_time = max(prev_time, dept[j])
	print(arrival_time)


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for _ in range(t):
	n = inp()
	s = []
	for __ in range(n):
		i = inlt()
		s.append(i)
	s.insert(0, [0, 0])
	tm = inlt()
	total = [s[i][0] - s[i - 1][1] + tm[i - 1] for i in range(1, n + 1)]
	alt = [math.ceil((j[1] - j[0]) / 2) for j in s]
	alt.remove(0)
	time = 0
	for i in range(n):
		time += total[i]
		if i < n - 1:
			time += alt[i]
			time = s[i + 1][1] if time < s[i + 1][1] else time
	print(time)


from sys import *
from math import *
t = stdin.readline
R = range
p = stdout.write

def I():
	return int(t())

def GI():
	return map(int, input().strip().split())

def IL():
	return list(map(int, t().strip().split()))
for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	for _ in range(n):
		(i, j) = map(int, input().split())
		a += [i]
		b += [j]
	t = list(map(int, input().split()))
	c = a[0] + t[0]
	for i in range(n - 1):
		c = max(c + (b[i] - a[i] + 1) // 2, b[i])
		c += a[i + 1] - b[i] + t[i + 1]
	print(c)


from sys import stdin as f
import math

def calculate_the_time(pointers, times):
	current_time = 0
	for i in range(len(pointers)):
		if i == 0:
			prev_b = 0
		else:
			prev_b = pointers[i - 1][1]
		a = pointers[i][0]
		b = pointers[i][1]
		c = times[i]
		time_passed = a - prev_b + c
		current_time = current_time + time_passed
		if i == n - 1:
			return current_time
		current_time = current_time + math.ceil((b - a) / 2)
		if current_time >= b:
			continue
		else:
			current_time = b
	return current_time
t = int(f.readline().strip())
for _ in range(t):
	n = int(f.readline().strip())
	pointers = []
	for i in range(n):
		(a, b) = [int(i) for i in f.readline().strip().split()]
		pointers.append((a, b))
	times = [int(i) for i in f.readline().strip().split()]
	current_time = calculate_the_time(pointers, times)
	print(current_time)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	AB = [list(map(int, input().strip().split())) for i in range(n)]
	TM = list(map(int, input().strip().split()))
	result = AB[0][0] + TM[0]
	for i in range(n - 1):
		result = max(result + (AB[i][1] - AB[i][0] + 1) // 2, AB[i][1])
		result += AB[i + 1][0] - AB[i][1] + TM[i + 1]
	print(result)


import sys
from math import ceil
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def process(n, ais, bis, tms):
	t = 0
	for i in range(1, n, 1):
		t = t + (ais[i] - bis[i - 1] + tms[i])
		d = ceil((bis[i] - ais[i]) / 2)
		if t >= bis[i]:
			t = t + d
		else:
			time_diff = bis[i] - t
			if time_diff >= d:
				t = t + time_diff
			else:
				t = t + d
	t = t + (ais[n] - bis[n - 1] + tms[n])
	print(t)

def main():
	t = inp()
	for case in range(t):
		(ais, bis) = ([0], [0])
		n = inp()
		for _ in range(n):
			(ai, bi) = inlt()
			ais.append(ai)
			bis.append(bi)
		tms = inlt()
		tms.insert(0, 0)
		process(n, ais, bis, tms)
main()


import math
for cases in range(int(input())):
	n = int(input())
	arr = [0]
	dep = [0]
	for i in range(n):
		(a, b) = map(int, input().split())
		arr.append(a)
		dep.append(b)
	tm = list(map(int, input().split()))
	tm = [0] + tm
	curr = 0
	for i in range(1, n + 1):
		curr = curr + arr[i] - dep[i - 1] + tm[i]
		if i != n:
			curr += math.ceil((dep[i] - arr[i]) / 2)
			curr = max(dep[i], curr)
	print(curr)


import math
tests = int(input())
for i in range(0, tests):
	stations = int(input())
	a = [0]
	b = [0]
	tm = []
	for j in range(1, stations + 1):
		(tempa, tempb) = map(int, input().split())
		a.append(tempa)
		b.append(tempb)
	tm = input().split()
	tm = [int(k) for k in tm]
	res = 0
	for j in range(1, stations + 1):
		res += a[j] - b[j - 1] + tm[j - 1]
		temp = math.ceil((b[j] - a[j]) / 2)
		if j < stations:
			res += temp
			if res <= b[j]:
				res = b[j]
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	b = []
	t = []
	for i in range(n):
		(f, s) = map(int, input().split())
		a.append(f)
		b.append(s)
	b.append(0)
	t = list(map(int, input().split()))
	time = 0
	for i in range(n - 1):
		time += a[i] - b[i - 1] + t[i]
		if time + (b[i] - a[i] + 1) // 2 < b[i]:
			time = b[i]
		else:
			time += (b[i] - a[i] + 1) // 2
	time += a[n - 1] - b[n - 2] + t[n - 1]
	print(time)


def ceil(c):
	if int(c) == c:
		return int(c)
	return int(c) + 1

def solve(n):
	ari = []
	dep = []
	minWait = []
	for i in range(n):
		(a, b) = map(int, input().split())
		ari.append(a)
		dep.append(b)
		minWait.append(ceil((b - a) / 2))
	tm = list(map(int, input().split()))
	late = 0
	for i in range(n):
		late += tm[i]
		ari[i] += late
		if ari[i] + minWait[i] <= dep[i]:
			late = 0
		else:
			late = ari[i] + minWait[i] - dep[i]
	return ari[-1]
for _ in range(int(input())):
	print(solve(int(input())))


for _ in range(int(input())):
	n = int(input())
	time = []
	wait = []
	for i in range(n):
		time.append(list(map(int, input().split())))
		wait.append((time[i][1] - time[i][0] + 1) // 2)
	tm = list(map(int, input().split()))
	time.append([0, 0])
	now = 0
	for i in range(n - 1):
		ai = time[i][0]
		bi = time[i][1]
		now += tm[i] + ai - time[i - 1][1]
		now = max(bi, now + wait[i])
	print(now + tm[n - 1] + time[n - 1][0] - time[n - 2][1])


cases = int(input())
for case in range(cases):
	n = int(input())
	h = [list(map(int, input().split())) for _ in range(n)]
	late = list(map(int, input().split()))
	t = h[0][0] + late[0]
	arr = 0
	for i in range(n - 1):
		(a, b) = h[i]
		(ap, bp) = h[i + 1]
		dep = max(b, t + (b - a + 1) // 2)
		t = dep + ap - b + late[i + 1]
	print(t)


from math import ceil, floor, sqrt

def fun(ls, d):
	prv = 0
	original = ls.copy()
	time_to_reach = []
	for (time, delay) in zip(ls, d):
		arrival = time[0]
		departure = time[1]
		temp = arrival - prv + delay
		time_to_reach.append(temp)
		prv = departure
	late_departure = 0
	i = 0
	ans = []
	for (time, delay) in zip(ls, time_to_reach):
		temp = late_departure + delay
		current = ls[i]
		ans.append(temp)
		original_current = original[i]
		start = original_current[0]
		end = original_current[1]
		val = ceil((end - start) / 2)
		if temp + val <= end:
			late_departure = end
		else:
			late_departure = temp + val
		i += 1
	print(ans[-1])
T = int(input())
for i in range(T):
	ls = []
	n = int(input())
	for i in range(n):
		lt = list(map(int, input().split()))
		ls.append(lt)
	delay = list(map(int, input().split()))
	fun(ls, delay)


from math import ceil

def solve(a, b, t):
	miint = []
	for i in range(n):
		miint.append(ceil((b[i] - a[i]) / 2))
	for i in range(n - 1):
		a[i] = a[i] + t[i]
		if b[i] - a[i] < miint[i]:
			a[i + 1] += miint[i] - (b[i] - a[i])
	return a[-1] + t[-1]
t = int(input())
for _ in range(t):
	a = []
	b = []
	n = int(input())
	for _ in range(n):
		(ai, bi) = map(int, input().split())
		a.append(ai)
		b.append(bi)
	t = list(map(int, input().split()))
	print(solve(a, b, t))


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(ai, bi) = [int(i) for i in input().split()]
		a.append(ai)
		b.append(bi)
	t = [int(i) for i in input().split()]
	d = 0
	curr = 0
	arr = [0 for i in range(n)]
	for i in range(n):
		arr[i] = d + a[i] + t[i]
		diff = b[i] - a[i]
		if diff % 2 == 0:
			diff = diff // 2
		else:
			diff = diff // 2 + 1
		leave = max(diff + arr[i], b[i])
		d = leave - b[i]
	print(arr[-1])


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
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')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree2:

	def __init__(self, data, default=3000006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 10, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=-10 ** 10, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor, t):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += t
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += t
		self.temp.data = pre_xor

	def query(self, p, l):
		ans = 0
		self.temp = self.root
		for i in range(31, -1, -1):
			val = p & 1 << i
			val1 = l & 1 << i
			if val1 == 0:
				if val == 0:
					if self.temp.left and self.temp.left.count > 0:
						self.temp = self.temp.left
					else:
						return ans
				elif self.temp.right and self.temp.right.count > 0:
					self.temp = self.temp.right
				else:
					return ans
			elif val != 0:
				if self.temp.right:
					ans += self.temp.right.count
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				else:
					return ans
			else:
				if self.temp.left:
					ans += self.temp.left.count
				if self.temp.right and self.temp.right.count > 0:
					self.temp = self.temp.right
				else:
					return ans
		return ans
for ik in range(int(input())):
	n = int(input())
	l = []
	last = 0
	end = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
	tm = list(map(int, input().split()))
	for i in range(n):
		(a, b) = l[i]
		st = a - last + tm[i] + end
		end = max(b, st + int(math.ceil((b - a) / 2)))
		last = b
	print(st)


from math import ceil
p = lambda : list(map(int, input().split()))
t = p()[0]
while t:
	n = p()[0]
	a = [[0, 0]]
	for _ in range(n):
		a.append(p())
	d = [0] + p()
	time = 0
	for i in range(1, n):
		time += a[i][0] - a[i - 1][1] + d[i]
		wait = ceil((a[i][1] - a[i][0]) / 2)
		time = max(time + wait, a[i][1])
	time += a[n][0] - a[n - 1][1] + d[n]
	print(time)
	t -= 1


import math
from collections import defaultdict
from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	l = []
	for i in range(n):
		arr = list(map(int, input().split()))
		l.append(arr)
	d = list(map(int, input().split()))
	dep = 0
	for i in range(n):
		lis = l[i]
		if i == 0:
			a = lis[0] + d[i]
			dur = math.ceil((lis[1] - lis[0]) / 2)
			dep = max(a + dur, lis[1])
			if n == 1:
				print(a)
		elif i == n - 1:
			lis1 = l[i - 1]
			a = lis[0] - lis1[1] + d[i] + dep
			print(a)
		else:
			lis1 = l[i - 1]
			a = lis[0] - lis1[1] + d[i] + dep
			dur = math.ceil((lis[1] - lis[0]) / 2)
			dep = max(a + dur, lis[1])


import math
testcases = int(input())
while testcases > 0:
	n = int(input())
	myList = []
	i = n
	while i > 0:
		(a, b) = map(int, input().split())
		myList.append([a, b])
		i -= 1
	myArray = list(map(int, input().split()))
	arrivalTime = myList[0][0] + myArray[0]
	departureTime = max(arrivalTime + math.ceil((myList[0][1] - myList[0][0]) / 2), myList[0][1])
	i = 1
	while i < len(myList):
		arrivalTime = departureTime + myList[i][0] - myList[i - 1][1] + myArray[i]
		departureTime = max(arrivalTime + math.ceil((myList[i][1] - myList[i][0]) / 2), myList[0][1])
		i += 1
	print(arrivalTime)
	testcases -= 1


try:
	test = int(input())
	while test != 0:
		n = int(input())
		(a, b) = ([0] * (n + 1), [0] * (n + 1))
		for i in range(1, n + 1):
			(a1, b1) = map(int, input().split())
			a[i] = a1
			b[i] = b1
		time = list(map(int, input().split()))
		time = [0] + time
		ans = 0
		for i in range(1, n):
			temp = ans + a[i] - b[i - 1] + time[i] + (b[i] - a[i] + 1) // 2
			ans = max(temp, b[i])
		ans += a[n] - b[n - 1] + time[n]
		print(ans)
		test -= 1
except EOFError:
	print(' ')


import sys, os.path
import math
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	n = int(input())
	arr = []
	dep = []
	for i in range(n):
		(a, b) = map(int, input().split())
		arr.append(a)
		dep.append(b)
	delay = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1):
		if i == 0:
			ans = arr[0] + delay[0]
		else:
			ans += arr[i] + delay[i] - dep[i - 1]
		if ans + math.ceil((dep[i] - arr[i]) / 2) > dep[i]:
			ans += math.ceil((dep[i] - arr[i]) / 2)
		else:
			ans = dep[i]
	if n >= 2:
		ans += delay[-1] + (arr[n - 1] - dep[n - 2])
	else:
		ans += delay[-1] + arr[-1]
	print(ans)


import math
t = int(input())
x_list = []
if t <= 100 and t >= 1:
	for j in range(t):
		n = int(input())
		a = []
		b = []
		for i in range(n):
			(a_list, b_list) = input().split()
			a_list = int(a_list)
			b_list = int(b_list)
			if a_list >= 1 and b_list >= a_list and (1000000 >= b_list):
				a.append(a_list)
				b.append(b_list)
		tm = [int(tm) for tm in input().split()]
		tmar1 = a[0] + tm[0]
		d1 = math.ceil((b[0] - a[0]) / 2)
		if tmar1 + d1 >= b[0]:
			tmbr1 = tmar1 + d1
		else:
			tmbr1 = b[0]
		x = tmbr1
		if n == 1:
			x_list.append(tmar1)
		else:
			for i in range(1, n):
				if i != n - 1:
					tr = a[i] - b[i - 1] + tm[i]
					x = x + tr
					d = math.ceil((b[i] - a[i]) / 2)
					if x + d >= b[i]:
						x = x + d
					else:
						x = b[i]
				elif i == n - 1:
					tr = a[i] - b[i - 1] + tm[i]
					x = x + tr
			x_list.append(x)
for i in x_list:
	print(i)


import math
for tc in range(int(input())):
	n = int(input())
	arrive = []
	depart = []
	delay = []
	for pair in range(n):
		(a, b) = map(int, input().split())
		arrive.append(a)
		depart.append(b)
	delay = list(map(int, input().split()))
	come = arrive[0] + delay[0]
	go = max(depart[0], come + math.ceil((depart[0] - arrive[0]) / 2))
	for i in range(1, n):
		come = go + delay[i] + (arrive[i] - depart[i - 1])
		go = max(depart[i], come + math.ceil(abs(depart[i] - arrive[i]) / 2))
	print(come)


read = lambda : map(int, input().split(' '))
for _ in range(int(input())):
	n = int(input())
	start = [0] * (n + 1)
	end = [0] * (n + 1)
	for i in range(1, n + 1):
		(start[i], end[i]) = read()
	delay = list(read())
	arr = [0] * (n + 1)
	brr = [0] * (n + 1)
	for i in range(1, n + 1):
		arr[i] = brr[i - 1] + start[i] - end[i - 1] + delay[i - 1]
		brr[i] = max(end[i], arr[i] + (end[i] - start[i] + 1) // 2)
	print(arr[n])


from math import ceil
for _ in range(int(input())):
	n = int(input())
	store = []
	for i in range(n):
		(a, b) = map(int, input().split())
		store.append([a, b])
	t = list(map(int, input().split()))
	ans = 0
	store = [[0, 0]] + store
	c_ans = 0
	for i in range(1, n + 1):
		ans += store[i][0] - store[i - 1][1] + t[i - 1]
		c_ans = ans
		ans = max(ans + ceil((store[i][1] - store[i][0]) / 2), store[i][1])
	print(c_ans)


T = int(input())
for _ in range(T):
	n = int(input())
	a = [(0, 0)]
	for i in range(n):
		(s, d) = map(int, input().split())
		a.append((s, d))
	delay = list(map(int, input().split()))
	s = 0
	for i in range(0, n):
		s += int((a[i][1] - a[i][0]) / 2 + 0.5)
		if s < a[i][1]:
			s = a[i][1]
		s += a[i + 1][0] - a[i][1]
		s += delay[i]
	print(s)


import math
_ = int(input())
for i in range(0, _):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		ab = list(map(int, input().strip().split()))
		a.append(ab[0])
		b.append(ab[1])
	ti = list(map(int, input().strip().split()))
	current_time = 0
	real_out_prev_time = 0
	real_in_time = a[0]
	for i in range(len(ti)):
		if i == 0:
			current_time = current_time + (a[i] - 0 + ti[i])
		else:
			current_time = current_time + (a[i] - b[i - 1] + ti[i])
		if not i == len(ti) - 1:
			if current_time > b[i] - math.ceil((b[i] - a[i]) / 2):
				current_time = current_time + math.ceil((b[i] - a[i]) / 2)
			else:
				current_time = b[i]
	print(current_time)


for _ in range(int(input())):
	t = int(input())
	a = []
	for i in range(t):
		(x, y) = map(int, input().split())
		a.append([x, y])
	l = list(map(int, input().split()))
	if t == 1:
		print(a[0][0] + l[0])
		continue
	s = a[0][0] + l[0]
	p = a[0][1] - a[0][0] + 1
	s += p // 2
	s = max(s, a[0][1])
	for i in range(1, t - 1):
		s += a[i][0] - a[i - 1][1] + l[i]
		p = a[i][1] - a[i][0] + 1
		s += p // 2
		s = max(a[i][1], s)
	s += a[-1][0] - a[-2][1] + l[-1]
	print(s)


import math
for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		b = list(map(int, input().split()))
		l.append(b)
	prev = 0
	dept = 0
	t = list(map(int, input().split()))
	for i in range(n):
		arr = dept + t[i] + l[i][0] - prev
		prev = l[i][1]
		x = math.ceil((l[i][1] - l[i][0]) / 2)
		dept = max(arr + x, l[i][1])
	print(arr)


import os
DEBUG = 'DEBUG' in os.environ
import math
import sys
fastInput = sys.stdin.buffer.readline

def debug(*args):
	if DEBUG:
		print('>', *args)

def solution(stations, timings):
	debug('>>')
	answer = 0
	delay = 0
	for stationIdx in range(0, len(stations)):
		station = stations[stationIdx]
		timing = timings[stationIdx]
		minimumWaitTime = math.ceil((station[1] - station[0]) / 2)
		arriveTime = station[0] + timing + delay
		answer = arriveTime
		realDepartTime = max(arriveTime + minimumWaitTime, station[1])
		delay = realDepartTime - station[1]
		debug(station, {'arrives': arriveTime, 'realDepartTime': realDepartTime})
	debug('> final delay', delay)
	return answer
for t in range(int(fastInput())):
	stations = []
	for station in range(int(fastInput())):
		stations.append(list(map(int, fastInput().split())))
	timings = list(map(int, fastInput().split()))
	print(solution(stations, timings))


for _ in range(int(input())):
	n = int(input())
	(a, b) = ([0] * n, [0] * n)
	for i in range(n):
		(a[i], b[i]) = map(int, input().split())
	b += [0]
	tm = list(map(int, input().split()))
	res = 0
	for i in range(n):
		res += a[i] - b[i - 1] + tm[i]
		if i < n - 1:
			res = max(res + (b[i] - a[i] + 1) // 2, b[i])
	print(res)


import math
for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		(ai, bi) = [int(y) for y in input().split()]
		a.append((ai, bi, math.ceil((bi - ai) / 2)))
	t = [int(y) for y in input().split()]
	tm = 0
	for i in range(n):
		if i == 0:
			tm += t[i] + a[i][0]
		else:
			tm += t[i] + a[i][0] - a[i - 1][1]
		if i == n - 1:
			print(tm)
			break
		if tm + a[i][2] >= a[i][1]:
			tm += a[i][2]
		else:
			tm = a[i][1]


for _ in range(int(input())):
	n = int(input())
	a = [tuple(map(int, input().split())) for _ in range(n)]
	b = list(map(int, input().split()))
	t = a[0][0]
	for i in range(n - 1):
		t += b[i]
		t = max(t + (a[i][1] - a[i][0] + 1) // 2, a[i][1])
		t += a[i + 1][0] - a[i][1]
	print(t + b[n - 1])


def chk(p, a):
	if p % a == 0:
		return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	ct = 0
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
	t = list(map(int, input().split()))
	prev = 0
	for i in range(n):
		a = l[i][0]
		b = l[i][1]
		time = t[i]
		if i == 0:
			ct += a + time
		else:
			ct += a - prev + time
		if i == n - 1:
			break
		wait = (b - a) // 2 + chk(b - a, 2)
		ct += wait
		prev = b
		if ct >= b:
			continue
		else:
			r = b - ct
			ct += r
	print(ct)


import sys
import math
from itertools import permutations
from bisect import bisect_left
import heapq
from collections import deque

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

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

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

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(II()):
	n = II()
	x = []
	y = []
	for i in range(n):
		(a, b) = MI()
		x.append(a)
		y.append(b)
	tm = LI()
	temp = x[0]
	for i in range(n - 1):
		temp += tm[i]
		if y[i] - temp >= math.ceil((y[i] - x[i]) / 2):
			temp = x[i + 1]
		else:
			temp += math.ceil((y[i] - x[i]) / 2)
			temp += x[i + 1] - y[i]
	print(temp + tm[-1])


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


import io, os
stdin = io.BytesIO(os.read(0, os.fstat(0).st_size))
from collections import defaultdict, Counter
from itertools import combinations, permutations
from os import path
if path.exists('tc.txt'):
	stdin = open('tc.txt', 'r')

def gmi():
	return map(int, stdin.readline().strip().split())

def gms():
	return map(str, stdin.readline().strip().split())

def gari():
	return list(map(int, stdin.readline().strip().split()))

def gars():
	return list(map(str, stdin.readline().strip().split()))

def gs():
	return stdin.readline().strip()

def gls():
	return list(stdin.readline().strip())

def gi():
	return int(stdin.readline())
from math import ceil
t = gi()
while t:
	t -= 1
	n = gi()
	ar = []
	for i in range(n):
		ar.append(tuple(gmi()))
	m = gari()
	d = 0
	for i in range(n):
		avl = ar[i][0] + m[i] + d
		dep = max(ar[i][1], ceil((ar[i][1] - ar[i][0]) / 2) + avl)
		d = dep - ar[i][1]
	print(avl)


import math
for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	d = []
	for i in range(n):
		(x, y) = map(int, input().split())
		z = math.ceil((y - x) / 2)
		a.append(x)
		b.append(y)
		d.append(z)
	tm = list(map(int, input().split()))
	if n == 1:
		ans = a[0] + tm[0]
	for j in range(n):
		if j == 0:
			a[j] = a[j] + tm[j]
			prev = b[j]
			if b[j] - a[j] < d[j]:
				b[j] += d[j] - (b[j] - a[j])
		else:
			dist = a[j] - prev + tm[j]
			a[j] = b[j - 1] + dist
			if j == n - 1:
				ans = a[j]
				break
			prev = b[j]
			if b[j] - a[j] < d[j]:
				b[j] += d[j] - (b[j] - a[j])
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	curr = 0
	(arrival, departure) = ([], [])
	for _ in range(n):
		(a, b) = map(int, input().split())
		arrival.append(a)
		departure.append(b)
	arr = list(map(int, input().split()))
	prev = 0
	for i in range(n):
		duration = arrival[i] - prev + arr[i]
		curr += duration
		if i != n - 1:
			stop = math.ceil((departure[i] - arrival[i]) / 2)
			curr += stop
			while curr < departure[i]:
				curr += 1
			prev = departure[i]
	print(curr)


try:
	import math
	for _ in range(int(input())):
		n = int(input())
		arr = []
		for _ in range(n):
			arr.append(list(map(int, input().split())))
		trim = list(map(int, input().split()))
		if n == 1:
			print(arr[0][0] + trim[0])
		else:
			diff = 0
			if math.ceil((arr[0][1] - arr[0][0]) / 2) + trim[0] + arr[0][0] <= arr[0][1]:
				pass
			else:
				diff = math.ceil((arr[0][1] - arr[0][0]) / 2) + trim[0] + arr[0][0] - arr[0][1]
			for i in range(1, n):
				if i == n - 1:
					print(arr[i][0] + diff + trim[i])
				elif math.ceil((arr[i][1] - arr[i][0]) / 2) + trim[i] + diff + arr[i][0] <= arr[i][1]:
					pass
				else:
					diff = math.ceil((arr[i][1] - arr[i][0]) / 2) + trim[i] + arr[i][0] + diff - arr[i][1]
except EOFError:
	print(' ')


import math
for i in range(int(input())):
	n = int(input())
	a = [0]
	b = [0]
	for j in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
	t = list(map(int, input().split()))
	time = 0
	sumo = 0
	for j in range(1, n + 1):
		k = 0
		if sumo + math.ceil((b[j - 1] - a[j - 1]) / 2) > b[j - 1]:
			sumo = sumo + math.ceil((b[j - 1] - a[j - 1]) / 2)
		else:
			sumo = b[j - 1]
		sumo = sumo + a[j] - b[j - 1] + t[j - 1]
	print(sumo)


import math
for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	tm = list(map(int, input().split()))
	res = l[0][0] + tm[0]
	for i in range(n - 1):
		res = max(res + math.ceil((l[i][1] - l[i][0]) / 2), l[i][1])
		res += l[i + 1][0] - l[i][1] + tm[i + 1]
	print(res)


from math import ceil
counter = int(input())
for count in range(counter):
	n = int(input())
	ab = []
	for i in range(n):
		ab.append(list(map(int, input().split())))
	tm = list(map(int, input().split()))
	t = 0
	for i in range(n):
		if i == 0:
			t += tm[0] + ab[0][0]
		else:
			t += ab[i][0] - ab[i - 1][1] + tm[i]
		if i == n - 1:
			break
		dt = max(ceil((ab[i][1] - ab[i][0]) / 2), ab[i][1] - t)
		t += dt
	print(t)


n = int(input())
for i in range(n):
	t = int(input())
	e = []
	for j in range(t):
		e1 = list(map(int, input().split()))
		e.append(e1)
	l = list(map(int, input().split()))
	s = 0
	for j in range(t):
		if j == 0:
			s += e[j][0] + l[j]
		else:
			s += e[j][0] - e[j - 1][1] + l[j]
		if j == t - 1:
			break
		ses = (e[j][1] - e[j][0] + 1) // 2
		if s + ses < e[j][1]:
			s = e[j][1]
		else:
			s += ses
	print(s)


import sys
import math

def input():
	return sys.stdin.readline().rstrip()

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

def read_int_tuple():
	return tuple(map(int, input().split()))

def read_int():
	return int(input())
t = read_int()
for _ in range(t):
	n = read_int()
	(a, b) = ([0], [0])
	for idx in range(n):
		(_a, _b) = read_int_list()
		a.append(_a)
		b.append(_b)
	tm = [0] + read_int_list()
	cur = 0
	for i in range(1, n + 1):
		cur += a[i] - b[i - 1] + tm[i]
		if i == n:
			break
		least_waiting = (b[i] + 1 - a[i]) // 2
		leaving = cur + least_waiting
		if leaving < b[i]:
			cur = b[i]
		else:
			cur = leaving
	print(cur)


t = int(input())
import math
while t > 0:
	t -= 1
	n = int(input())
	rs = []
	for i in range(n):
		(ai, bi) = map(int, input().split())
		rs.append([math.ceil((bi - ai) / 2), ai, bi])
	tms = list(map(int, input().split()))
	bPrev = 0
	leaving = 0
	for i in range(n):
		(c, a, b) = rs[i]
		ti = tms[i]
		delay = a - bPrev + ti
		if i < n - 1:
			leaving = max(leaving + delay + c, b)
		else:
			leaving += delay
		bPrev = b
	print(leaving)


for _ in range(int(input())):
	n = int(input())
	a = [list(map(int, input().split())) for i in range(n)]
	time = list(map(int, input().split()))
	ans = a[0][0] + time[0]
	for i in range(n - 1):
		ans = max(a[i][1], ans + (a[i][1] - a[i][0] + 1) // 2)
		ans += a[i + 1][0] - a[i][1] + time[i + 1]
	print(ans)


def hel(l, a):
	t = 0
	cs = 0
	for i in range(len(a)):
		ns = l[i][0]
		t += ns - cs + a[i]
		if i == len(a) - 1:
			break
		br = -1 * (-(l[i][1] - l[i][0]) // 2)
		if t + br < l[i][1]:
			t = l[i][1]
		else:
			t += br
		cs = l[i][1]
	return t
t = int(input())
for i in range(t):
	n = int(input())
	l = [0] * n
	for j in range(n):
		arr = list(map(int, input().split()))
		l[j] = [arr[0], arr[1]]
	a = list(map(int, input().split()))
	print(hel(l, a))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	d = []
	for _ in range(n):
		(x, y) = list(map(int, input().split()))
		a.append(x)
		d.append(y)
	tm = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if i >= 1:
			ans += a[i] - d[i - 1] + tm[i]
		else:
			ans += a[i] + tm[i]
		if i < n - 1:
			r = int(math.ceil((d[i] - a[i]) / 2))
			ans = max(ans + r, d[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		a = list(map(int, input().split()))
		arr.append(a)
	delay = list(map(int, input().split()))
	ans = delay[0]
	for i in range(n - 1):
		diff = arr[i][1] - arr[i][0]
		if diff % 2 == 0:
			diffi = diff // 2
		else:
			diffi = diff // 2
		if ans != 0 and diff - diffi > 0:
			if diffi <= ans:
				ans = ans - diffi
			else:
				ans = 0
		ans += delay[i + 1]
	print(arr[n - 1][0] + ans)


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from math import ceil
for _ in range(it()):
	n = it()
	v = [[0, 0]]
	for _ in range(n):
		v.append(mp())
	t = mp()
	ans = 0
	ct = 0
	for i in range(1, n + 1):
		x = v[i][0] - v[i - 1][1] + t[i - 1]
		ct += x + v[i][1] - v[i][0]
		if ct > v[i][1]:
			p = ceil((v[i][1] - v[i][0]) / 2)
		else:
			p = v[i][1] - v[i][0]
		ans += x + p
	print(ans - p)


t = int(input())
for gjbg in range(t):
	n = int(input())
	g = [[0, 0]]
	for i in range(n):
		g.append(list(map(int, input().split())))
	tm = list(map(int, input().split()))
	tm.insert(0, 0)
	dep = [0 for x in range(n + 1)]
	ar = [0 for x in range(n + 1)]
	for i in range(1, n + 1):
		ar[i] = dep[i - 1] + (g[i][0] - g[i - 1][1]) + tm[i]
		dep[i] = max(g[i][1], ar[i] + (g[i][1] - g[i][0] + 1) // 2)
	print(ar[n])


import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append([x, y])
	delay = list(map(int, input().split()))
	l = [[0, 0]] + l
	i = 1
	ct = 0
	bac = 0
	while i <= n:
		ct = bac + l[i][0] - l[i - 1][1] + delay[i - 1]
		tar = math.ceil((l[i][1] - l[i][0]) / 2)
		bac = max(l[i][1], ct + tar)
		i += 1
	print(ct)


import math
for _ in range(int(input())):
	n = int(input())
	lis = []
	for i in range(n):
		lis.append(list(map(int, input().split())))
	t = list(map(int, input().split()))
	time = 0
	for i in range(n):
		if i == 0:
			travel_time = lis[0][0] + t[0]
		else:
			travel_time = lis[i][0] - lis[i - 1][1] + t[i]
		time += travel_time
		if i == n - 1:
			break
		if time + math.ceil((lis[i][1] - lis[i][0]) / 2) > lis[i][1]:
			time += math.ceil((lis[i][1] - lis[i][0]) / 2)
		else:
			time = lis[i][1]
	print(time)


for _ in range(int(input())):
	n = int(input())
	station = [[0, 0]]
	stay = [0]
	time = 0
	for _ in range(n):
		tmp = list(map(int, input().split()))
		station.append(tmp)
		if (tmp[1] - tmp[0]) % 2 == 0:
			stay.append((tmp[1] - tmp[0]) // 2)
		else:
			stay.append((tmp[1] - tmp[0]) // 2 + 1)
	tmi = list(map(int, input().split()))
	for i in range(1, n + 1):
		during = tmi[i - 1] + station[i][0] - station[i - 1][1]
		time += during
		if i == n:
			break
		time += stay[i]
		if time >= station[i][1]:
			continue
		else:
			time = station[i][1]
	print(time)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
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))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	for _ in range(int(input())):
		n = int(input())
		ab = []
		for i in range(n):
			ab.append(list(map(int, input().split())))
		tm = list(map(int, input().split()))
		b = 0
		time = 0
		for i in range(n):
			time += ab[i][0] - b + tm[i]
			b = ab[i][1]
			if i != n - 1:
				time += (ab[i][1] - ab[i][0] + 1) // 2
				if time < ab[i][1]:
					time = ab[i][1]
		print(time)
	return
main()


import math
for _ in range(int(input())):
	n = int(input())
	pair = [list(map(int, input().split())) for i in range(n)]
	tm = list(map(int, input().split()))
	if n == 1:
		print(pair[0][0] + tm[0])
		continue
	ans = pair[0][0] + tm[0]
	ans += math.ceil((pair[0][1] - pair[0][0]) / 2)
	if ans < pair[0][1]:
		ans += pair[0][1] - ans
	for i in range(1, n - 1):
		ans += pair[i][0] - pair[i - 1][1] + tm[i]
		ans += math.ceil((pair[i][1] - pair[i][0]) / 2)
		if ans < pair[i][1]:
			ans += pair[i][1] - ans
	ans += pair[-1][0] - pair[-2][1] + tm[-1]
	print(ans)


T = int(input())
for x in range(T):
	n = int(input())
	a = []
	b = []
	for y in range(n):
		c = [int(z) for z in input().split()]
		a.append(c[0])
		b.append(c[1])
	tm = [int(p) for p in input().split()]
	time1 = 0
	for q in range(n):
		if q == 0:
			time1 = time1 + a[q] + tm[q]
		else:
			time1 = time1 + a[q] - b[q - 1] + tm[q]
		if (b[q] - a[q]) % 2 == 0:
			d = int((b[q] - a[q]) / 2)
		else:
			d = int((b[q] - a[q]) / 2) + 1
		if q != n - 1:
			if time1 + d >= b[q]:
				time1 = time1 + d
			else:
				time1 = b[q]
	print(time1)


n = int(input())
for a in range(n):
	m = int(input())
	artime = []
	deptime = []
	for i in range(m):
		(a, d) = [int(x) for x in input().split()]
		artime.append(a)
		deptime.append(d)
	x = [int(x) for x in input().split()]
	at = 0
	dt = 0
	for i in range(m):
		st = deptime[i] - artime[i]
		if st % 2 == 0:
			st = st // 2
		else:
			st = st // 2 + 1
		if i == 0:
			at = artime[0] + x[0]
			dt = at + st
			if dt < deptime[i]:
				dt = deptime[i]
		else:
			at = dt + artime[i] - deptime[i - 1] + x[i]
			if i == m - 1:
				break
			else:
				dt = at + st
				if dt < deptime[i]:
					dt = deptime[i]
	print(at)


import math

def ii():
	return int(input())

def fi():
	return float(input())

def si():
	return input()

def msi():
	return map(str, input().split())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def lsi():
	return list(msi())
for _ in range(ii()):
	n = ii()
	a = []
	b = []
	for i in range(n):
		(p, q) = mi()
		a.append(p)
		b.append(q)
	t = li()
	temp = t1 = 0
	for i in range(n):
		temp += a[i] - t1 + t[i]
		p = (b[i] - a[i] + 1) // 2
		if i != n - 1:
			temp += p
			if temp < b[i]:
				temp = b[i]
		t1 = b[i]
	print(temp)


for _ in range(int(input())):
	n = int(input())
	(a, b) = ([], [])
	for i in range(n):
		(aa, bb) = map(int, input().split())
		a.append(aa)
		b.append(bb)
	t = list(map(int, input().split()))
	cur = a[0] + t[0]
	for i in range(n - 1):
		cur = max(cur + (b[i] - a[i] + 1) // 2, b[i])
		cur += a[i + 1] - b[i] + t[i + 1]
	print(cur)


import math
for _ in range(int(input())):
	n = int(input())
	ad = []
	for i in range(n):
		ad.append(list(map(int, input().split())))
	et = list(map(int, input().split()))
	delay = 0
	for i in range(n - 1):
		depart = max(ad[i][1], ad[i][0] + delay + et[i] + math.ceil((ad[i][1] - ad[i][0]) / 2))
		delay = depart - ad[i][1]
	print(ad[-1][0] + delay + et[-1])


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def fi():
	return float(input())

def si():
	return input()

def msi():
	return map(str, input().split())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def lsi():
	return list(msi())

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	return x * y // gcd(x, y)
mod = 1000000007

def modInverse(b, m):
	g = gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def ceil(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def modu(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return -999999999
	else:
		return inv * a % m
from math import log, factorial, cos, tan, sin, radians, floor, sqrt, log2
import bisect
import random
import string
from decimal import *
getcontext().prec = 50
abc = 'abcdefghijklmnopqrstuvwxyz'
pi = 3.141592653589793

def gcd1(a):
	if len(a) == 1:
		return a[0]
	ans = a[0]
	for i in range(1, len(a)):
		ans = gcd(ans, a[i])
	return ans

def mykey(x):
	return (x[1], -x[0])

def main():
	for _ in range(ii()):
		n = ii()
		a = []
		b = []
		for i in range(n):
			(u, v) = mi()
			a.append(u)
			b.append(v)
		t = li()
		ans = 0
		x = []
		for i in range(n):
			if i:
				x.append(t[i] + a[i] - b[i - 1])
			else:
				x.append(t[i] + a[i])
		y = []
		for i in range(n):
			if i:
				ans = y[i - 1] + x[i]
			else:
				ans = x[0]
			y.append(max(b[i], ans + ceil(b[i] - a[i], 2)))
		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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	n = int(input())
	a = [0]
	b = [0]
	for i in range(n):
		(c, d) = map(int, input().split())
		a.append(c)
		b.append(d)
	l = list(map(int, input().split()))
	t = 0
	d = 0
	temp = 0
	for i in range(1, n + 1):
		t += a[i] - b[i - 1] + l[i - 1]
		temp = (b[i] - a[i] + 1) // 2
		if i == n:
			break
		if t + temp <= b[i]:
			t = b[i]
		else:
			t += temp
	print(t)


for _ in range(int(input())):
	n = int(input())
	arr = [[0, 0]] * (n + 1)
	for index in range(1, n + 1):
		temp = list(map(int, input().split()))
		arr[index] = temp
	tm = [0]
	tm.extend(list(map(int, input().split())))
	time = 0
	for i in range(1, n + 1):
		time += arr[i][0] - arr[i - 1][1] + tm[i]
		if time >= arr[i][1] - (arr[i][1] - arr[i][0] + 1) // 2:
			if i == n:
				break
			time += (arr[i][1] - arr[i][0] + 1) // 2
		else:
			if i == n:
				break
			time += arr[i][1] - time
	print(time)


import math

def getint():
	return [int(i) for i in input().split()]

def getstr():
	return [str(i) for i in input().split()]

def solve():
	n = int(input())
	a = [0]
	b = [0]
	for i in range(n):
		(x, y) = getint()
		a.append(x)
		b.append(y)
	tt = getint()
	t = [0] + tt
	current = 0
	ans = 0
	for i in range(1, n):
		current += a[i] - b[i - 1] + t[i]
		current = max(current + math.ceil((b[i] - a[i]) / 2), b[i])
	current += a[-1] - b[-2] + t[-1]
	print(current)
for _ in range(int(input())):
	solve()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	trains = []
	for i in range(n):
		train = list(map(int, input().split()))
		trains.append(train)
	delay = list(map(int, input().split()))
	alrdLate = 0
	currArrive = 0
	for i in range(n - 1):
		(s, e) = trains[i]
		currArrive = s + delay[i] + math.ceil((e - s) / 2) + alrdLate
		if currArrive > e:
			alrdLate = currArrive - e
	currArrive = trains[n - 1][0] + delay[n - 1] + alrdLate
	print(currArrive)


for tt in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		(l, r) = map(int, input().split())
		a.append((l, r))
	tm = list(map(int, input().split()))
	ans = tm[0] + a[0][0]
	for i in range(n - 1):
		wait = max(a[i][1] - ans, 0)
		ans += a[i + 1][0] - a[i][1] + tm[i + 1] + wait + max(0, (a[i][1] - a[i][0] + 1) // 2 - wait)
	print(ans)


from math import ceil
t = int(input())
for i in range(t):
	n = int(input())
	m = []
	for j in range(n):
		m.append([int(k) for k in input().split()])
	w = [int(j) for j in input().split()]
	res = 0
	for j in range(n - 1):
		res += m[j][0] - (m[j - 1][1] if j > 0 else 0)
		res += w[j]
		res += ceil((m[j][1] - m[j][0]) / 2)
		res = max(res, m[j][1])
	res += m[-1][0] - (m[-2][1] if n > 1 else 0)
	res += w[-1]
	print(res)


for _ in [0] * int(input()):
	n = int(input())
	w = [list(map(int, input().split())) for i in range(n)]
	s = list(map(int, input().split()))
	c = w[0][0]
	for i in range(n - 1):
		c += s[i]
		c = max(c + (w[i][1] - w[i][0] + 1) // 2, w[i][1])
		c += w[i + 1][0] - w[i][1]
	print(c + s[-1])


from math import ceil
for _ in range(int(input())):
	n = int(input())
	stat = [(0, 0)]
	for i in range(n):
		j = tuple(map(int, input().split()))
		stat.append(j)
	tm = list(map(int, input().split()))
	current_time = 0
	for i in range(1, n + 1):
		pass_time = stat[i][0] - stat[i - 1][1] + tm[i - 1]
		if i == n:
			station_time = 0
			current_time += station_time + pass_time
			break
		else:
			station_time = ceil((stat[i][1] - stat[i][0]) / 2)
			current_time += station_time + pass_time
		if current_time <= stat[i][1]:
			current_time = stat[i][1]
		else:
			pass
	print(current_time)


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	b = []
	for _1 in range(n):
		s = input().split()
		a.append(int(s[0]))
		b.append(int(s[1]))
	tm = [int(i) for i in input().split()]
	k = a[0] + tm[0]
	for i in range(n - 1):
		d = (b[i] - a[i] + 1) // 2
		if k + d >= b[i]:
			k += d
		else:
			k = b[i]
		k += a[i + 1] - b[i] + tm[i + 1]
	print(k)


import sys
from math import ceil

def main():
	(_, *l) = sys.stdin.read().strip().split('\n')
	i = 0
	out = []
	while i < len(l):
		n = int(l[i])
		t = [[int(x) for x in y.split()] for y in l[i + 1:i + n + 1]]
		k = [int(x) for x in l[i + n + 1].split()]
		last = 0
		for j in range(n):
			a = last + t[j][0] - t[j - 1][1] * (j != 0) + k[j]
			last = max(a + int(ceil((t[j][1] - t[j][0]) / 2)), t[j][1])
		out.append(a)
		i += n + 2
	return out
print(*main(), sep='\n')


import math
for i in range(int(input())):
	n = int(input())
	min_wait = []
	k = []
	tra = []
	for i in range(n):
		(a, b) = map(int, input().split())
		if i == 0:
			tra.append(a)
		else:
			tra.append(a - k[-1])
		k.append(b)
		min_wait.append(math.ceil((b - a) / 2))
	l = list(map(int, input().split()))
	z = 0
	for j in range(n - 1):
		z += l[j] + min_wait[j] + tra[j]
		if z < k[j]:
			z = k[j]
	z += l[-1] + tra[-1]
	print(z)


for i in range(int(input())):
	a = []
	b = []
	num = int(input())
	for i in range(num):
		(ai, bi) = map(int, input().split())
		a.append(ai)
		b.append(bi)
	t = list(map(int, input().split()))
	time = a[0] + t[0]
	for i in range(num - 1):
		dep = max(b[i], time + (b[i] - a[i] + 1) // 2)
		time = dep + a[i + 1] - b[i] + t[i + 1]
	print(time)


from math import *
import io, os, sys

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	r = []
	for i in range(n):
		(x, y) = ma()
		r.append([x, y])
	a = lis()
	prb = 0
	cur = 0
	for i in range(n):
		wait = ceil((r[i][1] - r[i][0]) / 2)
		aar = r[i][0] - prb + a[i]
		cur += aar
		pos = cur
		prb = r[i][1]
		cur += wait
		cur = max(cur, r[i][1])
	print(pos)


for t in range(int(input())):
	n = int(input())
	a_list = []
	b_list = []
	for i in range(n):
		(a, b) = map(int, input().split())
		a_list.append(a)
		b_list.append(b)
	tm = list(map(int, input().split()))
	answer = a_list[0] + tm[0]
	for i in range(n - 1):
		st_stop = max(b_list[i], answer + (b_list[i] - a_list[i] + 1) // 2)
		answer = st_stop + a_list[i + 1] - b_list[i] + tm[i + 1]
	print(answer)