Read problems statements in Mandarin Chinese  and Russian. 

Suraj, the Chief Prankster is back in action now and this time he has stolen the valentine's day gift given by Ashi (the love of Chef) to the Chef and ran away with it to Byteland.
Byteland is a not a regular place like Chef's town. The safest way from Chef's town to Byteland is through the path of tasty dishes. The path is named so because there are magical tasty dishes which appear to the traveler that no one can resist eating. Also, Suraj has added a strong sleep potion to each of the dish on this path to stop anyone from following him.
Knowing the devilish nature of Suraj, Ashi is concerned about the Chef and has asked all of Chef's town people to help. The distance from Chef's town to Byteland through the the path of tasty dishes is X units. They have the location where the magic dishes are and how many people are required to eat it completely. Anyone who eats a dish would go to a long sleep and won't be able to continue. They have the information about the tribal clans that live along the the path of tasty dishes who can be of real help in this journey. 
The journey Chef and his friends can be described as follows: There is a total of B dishes on the path of tasty dishes. Each dish is located at some distance from Chef's town denoted by x_{i} for the i^{th} dish ( x_{i-1} <  x_{i}). To minimize the number of friends Chef has to leave behind, all of them have decided that exactly y_{i} of them will eat the i^{th} dish, which is the required number of people needed to finish it completely. Also, there are a total of C tribal chef clans, each with their own population and location on the path that Chef and his friends will meet on their way to Byteland. They know that for some clan (say i), they are located at a distance of p_{i} ( p_{i-1} <  p_{i}) from Chef's town with a population of r_{i}. And if a group of at least q_{i} men approaches them, they would be able to convince them to join their forces against Suraj.

Given the information about all this, help the Chef to find out the minimum size of the group (including him and his friends) he should start with to reach Byteland and get back Ashi's gift from Suraj.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. Each test case contains three lines which are as follows:

First line of each test case contains X, the distance of Byteland from Chef's town.

Next line contains an integer B, the number of dishes on the path of tasty dishes. Then follows B pairs of space separated integers of the form x_{i} y_{i}, where x_{i} y_{i} are as defined above for the i^{th} dish.
Next line contains an integer C, followed C space separated triplets of integers p_{i} q_{i} r_{i} as defined above.

------ Output ------ 

For each test case, print the minimum size of the group  (including Chef) that is needed to reach Byteland.

------ Constraints ------ 

1 ≤ T ≤ 10
1 ≤ X ≤ 10^{9}
1 ≤ B ≤ 10000
Constraints on C

Subproblem 1 (25 points):  C = 0
Subproblem 2 (75 points): 1 ≤ C ≤ 10000

1 ≤ x_{i} < X, x_{i} < x_{i+1}
1 ≤ p_{i} < X, p_{i} < p_{i+1}
1 ≤ y_{i} ≤ 10^{14}
1 ≤ q_{i} ≤ 10^{14}
1 ≤ r_{i} ≤ 10^{14}
All the positions, of the tasty dishes and tribal clans are distinct.

----- Sample Input 1 ------ 
3

10

2 1 3 8 1

0

10

2 1 3 8 5

0

10

2 2 3 8 5

3 1 2 1 4 3 2 9 1 1
----- Sample Output 1 ------ 
5

9

6
----- explanation 1 ------ 
Example case 1. In the first case, there are no tribal clans, and two dishes, one which needs to be eaten by 3 chefs on their way and one to be eaten by 1 chef. Hence, we have to start with atleast 5 people in total to pass the path of tasty dishes.
Example case 2. Similar as Example Case 1.
Example case 3. In this case, if we start with 5 Chefs. At point 1, we have more than or equal to 2 chefs, hence the tribal clan of size 1 adds to the Chef's party and now they have size of 6. At position 2, three of them would be left behind eating a dish, leaving 3 of them to go ahead. At position 4, since the size is exactly 3, the tribal clan joins the chef's party making it of size 5. At position 8, all 5 of them will stop to eat the dish and none would go ahead. Similarly, if we start with 6, one of them would be able to pass position 8 and reach position 9, where it will also add one of the tribal clans to its party and reach Byteland.

Difficulty: HARD
Tags: Dynamic programming

Sorting

Complete search
Skill types: Dynamic programming

Sorting

Complete search

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	tarr = list(map(int, input().split()))
	np = tarr[0]
	arr = []
	sm = 1
	for i in range(1, 2 * np + 1, 2):
		arr.append([tarr[i], tarr[i + 1], -1])
		sm += tarr[i + 1]
	tgroup = list(map(int, input().split()))
	ng = tgroup[0]
	group = []
	for i in range(1, 3 * ng + 1, 3):
		k = [tgroup[i], tgroup[i + 2], tgroup[i + 1]]
		group.append(k)
	ans = []
	for item in arr:
		ans.append(item)
	for item in group:
		ans.append(item)
	ans.sort()

	def solve(m):
		for item in ans:
			if item[2] == -1:
				m = m - item[1]
			elif item[2] <= m:
				m += item[1]
		return m
	s = 1
	e = sm
	v = None
	while s <= e:
		m = (s + e) // 2
		if solve(m) >= 1:
			v = m
			e = m - 1
		else:
			s = m + 1
	print(v)


for _ in range(int(input())):
	_ = int(input())
	_in = iter(map(int, input().split()))
	_ = next(_in)
	a = [(x, 0, -y) for (x, y) in zip(_in, _in)]
	_in = iter(map(int, input().split()))
	_ = next(_in)
	a.extend(zip(_in, _in, _in))
	a.sort()

	def check(x):
		for (_, k, v) in a:
			if x >= k:
				x += v
			if x <= 0:
				return False
		return True
	n = len(a)
	(lb, ub) = (0, 1 << 63)
	while ub - lb > 1:
		mid = (ub + lb) // 2
		if check(mid):
			ub = mid
		else:
			lb = mid
	print(ub)


number_of_test_cases = int(input())
final_results = []

def f(initial, v):
	for item in v:
		if len(item) == 2:
			initial -= item[1]
		elif initial >= item[1]:
			initial += item[2]
	return initial > 0
for each_test_case in range(number_of_test_cases):
	X = int(input())
	(B, *xy) = map(int, input().split())
	final_xy = []
	best_case = 1
	for i in range(0, 2 * B, 2):
		final_xy.append([xy[i], xy[i + 1]])
		best_case += xy[i + 1]
	(C, *pqr) = map(int, input().split())
	final_pqr = []
	for i in range(0, 3 * C, 3):
		final_pqr.append([pqr[i], pqr[i + 1], pqr[i + 2]])
	final_vector = sorted(final_xy + final_pqr, key=lambda ele: (ele[0], -len(ele)))
	low = 1
	high = best_case
	possible_answer = best_case
	while low <= high:
		mid = (low + high) // 2
		if f(mid, final_vector):
			possible_answer = min(possible_answer, mid)
			high = mid - 1
		else:
			low = mid + 1
	final_results.append(possible_answer)
for i in final_results:
	print(i)


def bins(l, r, res):
	while l <= r:
		m = l + (r - l) // 2
		if isposs(m):
			res = min(res, m)
			r = m - 1
		else:
			l = m + 1
	return res

def isposs(n):
	for i in range(len(arr)):
		if arr[i][0][1]:
			n -= arr[i][1][0]
		elif n >= arr[i][1][0]:
			n += arr[i][1][1]
	return n > 0
for _ in range(int(input())):
	d = int(input())
	tmp = list(map(int, input().split()))
	arr = []
	i = qq = 1
	while i < 2 * tmp[0]:
		arr.append([[tmp[i], True], [tmp[i + 1], 0]])
		qq += tmp[i + 1]
		i += 2
	tmp = list(map(int, input().split()))
	i = 1
	while i < 3 * tmp[0]:
		arr.append([[tmp[i], False], [tmp[i + 1], tmp[i + 2]]])
		i += 3
	arr.sort()
	print(bins(1, qq, qq))


from sys import stdin
newpath = []
finalans = []

def check(num):
	point = 0
	for j in newpath:
		if j[2] == -99:
			num -= j[1]
			if num < 1:
				return False
		elif num >= j[1]:
			num += j[2]
	return True

def binary(low, high):
	if high - low == 1:
		if check(low):
			finalans.append(low)
		else:
			finalans.append(high)
		return
	mid = (low + high) // 2
	if check(mid):
		finalans.append(mid)
		binary(low, mid)
	else:
		binary(mid, high)
no = int(stdin.readline())
for _ in range(no):
	newpath.clear()
	finalans.clear()
	totdistance = int(stdin.readline())
	path = list(map(int, stdin.readline().split()))
	tribal = list(map(int, stdin.readline().split()))
	count = 1
	lever = 1
	for _ in range(path[0]):
		count += path[lever + 1]
		lever += 2
	if tribal[0] == 0:
		print(count)
	else:
		top = path[-2]
		flag = True
		pathpoint = 0
		tribalpoint = 0
		pathindex = 1
		tribalindex = 1
		while tribalpoint < tribal[0] and pathpoint < path[0]:
			if tribal[tribalindex] > top:
				break
			if tribal[tribalindex] < path[pathindex]:
				newpath.append(tribal[tribalindex:tribalindex + 3])
				tribalindex += 3
				tribalpoint += 1
			else:
				newpath.append([path[pathindex], path[pathindex + 1], -99])
				pathindex += 2
				pathpoint += 1
		rem = path[0] - pathpoint
		if rem > 0:
			for i in range(rem):
				newpath.append([path[pathindex], path[pathindex + 1], -99])
				pathindex += 2
		binary(1, count)
		print(finalans[-1])


def possible(val: int, path: list) -> bool:
	for item in path:
		if item[1] == 0:
			val -= item[2]
		elif val >= item[2]:
			val += item[3]
	return val > 0

def solve(maxChef: int, path: list) -> int:
	high = maxChef + 100
	low = 1
	ans = maxChef + 100
	while low <= high:
		mid = (low + high) // 2
		if possible(mid, path):
			ans = min(ans, mid)
			high = mid - 1
		else:
			low = mid + 1
	return ans
for _ in range(int(input())):
	X = int(input())
	maxChef = 0
	path = []
	(b, *arr) = [int(c) for c in input().split()]
	for i in range(0, len(arr), 2):
		location = arr[i]
		required_chef = arr[i + 1]
		path.append((location, 0, required_chef, 0))
		maxChef += required_chef
	(c, *arr) = [int(c) for c in input().split()]
	for i in range(0, len(arr), 3):
		location = arr[i]
		chef_required = arr[i + 1]
		chef_given = arr[i + 2]
		path.append((location, 1, chef_required, chef_given))
	path.sort(key=lambda x: x[0])
	print(solve(maxChef, path))


t = int(input())
for i in range(t):
	x = int(input())
	temp = [int(i) for i in input().split()]
	b = temp[0]
	dishes = []
	j = 1
	while j < 2 * b:
		dishes.append([temp[j], temp[j + 1]])
		j += 2
	temp = [int(i) for i in input().split()]
	c = temp[0]
	j = 1
	clan = []
	while j < 3 * c:
		clan.append([temp[j], temp[j + 1], temp[j + 2]])
		j += 3
	ans = 1
	dish_ptr = b - 1
	clan_ptr = c - 1
	while clan_ptr >= 0 and clan[clan_ptr][0] > dishes[dish_ptr][0]:
		clan_ptr -= 1
	while clan_ptr >= 0 or dish_ptr >= 0:
		if clan_ptr < 0:
			ans += dishes[dish_ptr][1]
			dish_ptr -= 1
		elif dish_ptr < 0:
			ans = min(ans, max(ans - clan[clan_ptr][2], clan[clan_ptr][1]))
			clan_ptr -= 1
		elif clan[clan_ptr][0] > dishes[dish_ptr][0]:
			ans = min(ans, max(ans - clan[clan_ptr][2], clan[clan_ptr][1]))
			clan_ptr -= 1
		else:
			ans += dishes[dish_ptr][1]
			dish_ptr -= 1
	print(ans)


def binary(l, r, ans):
	low = l
	high = r
	while low <= high:
		mid = (low + high) // 2
		if possible(mid):
			ans = min(ans, mid)
			high = mid - 1
		else:
			low = mid + 1
	return ans

def possible(n):
	v = n
	for i in range(len(e)):
		if e[i][0][1]:
			v -= e[i][1][0]
		elif v >= e[i][1][0]:
			v += e[i][1][1]
	return v > 0
for i in range(int(input())):
	x = int(input())
	t = list(map(int, input().split()))
	ans = 0
	q = 1
	i = 1
	e = []
	while i < 2 * t[0]:
		e.append([[t[i], 1], [t[i + 1], 0]])
		q = q + t[i + 1]
		i = i + 2
	t = list(map(int, input().split()))
	i = 1
	while i < 3 * t[0]:
		e.append([[t[i], 0], [t[i + 1], t[i + 2]]])
		i = i + 3
	e.sort()
	print(binary(1, q, q))


import bisect
import sys
import math

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()

def get_int():
	return int(sys.stdin.readline().strip())

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

def solve():
	distance = get_int()
	arr1 = get_list()
	arr2 = get_list()
	store1 = []
	store2 = []
	r = 1
	b = arr1[0]
	c = arr2[0]
	for i in range(1, len(arr1), 2):
		store1.append([arr1[i], arr1[i + 1]])
		r += arr1[i + 1]
	for i in range(1, len(arr2), 3):
		store2.append([arr2[i], arr2[i + 1], arr2[i + 2]])
	l = 1
	ans = r
	while l <= r:
		m = (l + r) // 2
		mid = m
		i = 0
		j = 0
		flag = 0
		while (i < len(store1) and j < len(store2)) and flag == 0:
			if store1[i][0] > store2[j][0]:
				if m >= store2[j][1]:
					m += store2[j][2]
				j += 1
			elif store1[i][0] < store2[j][0]:
				m -= store1[i][1]
				if m <= 0:
					flag = 1
				i += 1
			else:
				if m >= store2[j][1]:
					m += store2[j][2]
				m -= store1[i][1]
				if m <= 0:
					flag = 1
				i += 1
				j += 1
		if flag == 1:
			l = mid + 1
			continue
		while i < len(store1) and flag == 0:
			m -= store1[i][1]
			if m <= 0:
				flag = 1
			i += 1
		if flag == 1:
			l = mid + 1
		else:
			ans = mid
			r = mid - 1
	print(ans)
T = get_int()
while T:
	solve()
	T -= 1


def possible(R):
	for i in path:
		if i[2] == 'dish':
			R -= i[1]
		elif R >= i[1]:
			R += i[2]
	return R > 0
for _ in range(int(input())):
	n = int(input())
	d = list(map(int, input().split()))
	t = list(map(int, input().split()))
	b = d[0]
	dishes = []
	mn = 1
	mx = 0
	for i in range(1, 2 * b + 1, 2):
		dishes.append([d[i], d[i + 1], 'dish'])
		mx += d[i + 1]
	if t == [0]:
		required = 0
		for i in range(b):
			required += dishes[i][1]
		print(required + 1)
		continue
	c = t[0]
	clans = []
	for i in range(1, 3 * c + 1, 3):
		clans.append([t[i], t[i + 1], t[i + 2]])
	path = dishes + clans
	path.sort()
	ans = mx
	while mn < mx:
		m = (mn + mx) // 2
		if possible(m):
			ans = min(ans, m)
			mx = m
		else:
			mn = m + 1
	print(ans)


def check(road, pp):
	for i in road:
		if i == []:
			return False
		if len(i) == 2:
			pp -= i[1]
		elif i[1] <= pp:
			pp += i[2]
	if pp >= 1:
		return True
	else:
		return False
for _ in range(int(input())):
	x = int(input())
	dish = list(map(int, input().strip().split()))
	clan = list(map(int, input().strip().split()))
	ans = 0
	ppl = 0
	for i in range(2, len(dish), 2):
		ppl += dish[i]
	if clan[0] == 0:
		print(ppl + 1)
	else:
		road = []
		for i in range(1, len(dish), 2):
			road.append([dish[i], dish[i + 1]])
		for i in range(1, len(clan), 3):
			road.append([clan[i], clan[i + 1], clan[i + 2]])
		road.sort(key=lambda x: x[0])
		(l, h) = (1, ppl + 1)
		while l < h:
			m = (l + h) // 2
			if check(road, m):
				h = m
			else:
				l = m + 1
			ans = l
		print(ans)


def possible(n):
	for i in range(len(ls)):
		if ls[i][0][1]:
			n -= ls[i][1][0]
		elif n >= ls[i][1][0]:
			n += ls[i][1][1]
	return n > 0

def solve(l, r, ans):
	while l <= r:
		m = l + (r - l) // 2
		if possible(m):
			ans = min(ans, m)
			r = m - 1
		else:
			l = m + 1
	return ans
for _ in range(int(input())):
	d = int(input())
	temp = list(map(int, input().split()))
	ls = []
	i = req = 1
	while i < 2 * temp[0]:
		ls.append([[temp[i], True], [temp[i + 1], 0]])
		req += temp[i + 1]
		i += 2
	temp = list(map(int, input().split()))
	i = 1
	while i < 3 * temp[0]:
		ls.append([[temp[i], False], [temp[i + 1], temp[i + 2]]])
		i += 3
	ls.sort()
	print(solve(1, req, req))


def possible(z):
	for i in dis:
		if i in lands:
			z -= lands[i]
		if i in towns:
			if z >= towns[i][0]:
				z += towns[i][1]
	return z > 0
T = int(input())
while T > 0:
	x = int(input())
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	nb = b[0]
	nc = c[0]
	lands = {}
	towns = {}
	p = []
	q = []
	dis = []
	for i in range(1, len(b), 2):
		lands[b[i]] = b[i + 1]
		p.append(b[i])
	for i in range(1, len(c), 3):
		towns[c[i]] = (c[i + 1], c[i + 2])
		q.append(c[i])
	i = 0
	j = 0
	while i < nb and j < nc:
		if p[i] < q[j]:
			dis.append(p[i])
			i += 1
		else:
			dis.append(q[j])
			j += 1
	if i < nb:
		dis.extend(p[i:])
	if j < nc:
		dis.extend(q[j:])
	m = 1
	for y in range(2, len(b), 2):
		m += b[y]
	lo = 1
	hi = m
	res = m
	while lo <= hi:
		mid = (lo + hi) // 2
		if possible(mid):
			res = min(mid, res)
			hi = mid - 1
		else:
			lo = mid + 1
	print(res)
	T -= 1


def possible(v):
	for ele in combined_list:
		if len(ele) == 2:
			v -= ele[1]
		elif v >= ele[1]:
			v += ele[2]
	return v > 0
for _ in range(int(input().strip())):
	x = int(input().strip())
	lst = list(map(int, input().strip().split()))
	(b, lst) = (lst[0], lst[1:])
	dish_list = [(lst[2 * i], lst[2 * i + 1]) for i in range(b)]
	max_men = 1
	for dish in dish_list:
		max_men += dish[1]
	lst = list(map(int, input().strip().split()))
	(c, lst) = (lst[0], lst[1:])
	j = 0
	clan_list = []
	for i in range(c):
		clan_list.append((lst[j], lst[j + 1], lst[j + 2]))
		j += 3
	combined_list = dish_list + clan_list
	combined_list.sort()
	low = 1
	high = max_men
	ans = max_men
	while low <= high:
		m = (low + high) // 2
		if possible(m):
			ans = min(ans, m)
			high = m - 1
		else:
			low = m + 1
	print(high if possible(high) else low)


t = int(input())
for i in range(t):
	x = int(input())
	d = []
	l = [int(x) for x in input().split()]
	b = l[0]
	l.remove(l[0])
	for i in range(0, len(l), 2):
		d.append([l[i], -l[i + 1]])
	q = [int(x) for x in input().split()]
	c = q[0]
	q.remove(q[0])
	for i in range(0, len(q), 3):
		d.append([q[i], q[i + 1], q[i + 2]])
	d.sort()
	if c == 0:
		sum = 0
		for i in range(1, len(l), 2):
			sum = sum + l[i]
		sum += 1
		print(sum)
	else:

		def possible(m):
			for i in range(len(d)):
				if len(d[i]) == 2:
					m += d[i][1]
				elif m >= d[i][1]:
					m += d[i][2]
			return m > 0
		sum = 0
		for i in range(1, len(l), 2):
			sum = sum + l[i]
		sum += 1
		low = 1
		high = sum
		ans = sum
		while low <= high:
			m = (low + high) // 2
			if possible(m):
				ans = min(ans, m)
				high = m - 1
			else:
				low = m + 1
		print(ans)


def check(noOfPeople, plus, minus):
	pcnt = 0
	mcnt = 0
	while pcnt < len(plus) and mcnt < len(minus):
		if plus[pcnt][0] < minus[mcnt][0]:
			if noOfPeople >= plus[pcnt][1]:
				noOfPeople += plus[pcnt][2]
			pcnt += 1
		elif minus[mcnt][0] < plus[pcnt][0]:
			noOfPeople -= minus[mcnt][1]
			mcnt += 1
		else:
			if noOfPeople >= plus[pcnt][1]:
				noOfPeople += plus[pcnt][2]
			pcnt += 1
			noOfPeople -= minus[mcnt][1]
			mcnt += 1
		if noOfPeople <= 0:
			return False
	while mcnt < len(minus):
		noOfPeople -= minus[mcnt][1]
		mcnt += 1
		if noOfPeople <= 0:
			return False
	return True

def solve(plus, minus, X, maxval):
	low = 0
	high = maxval + 1
	while high - low > 1:
		mid = low + (high - low) // 2
		if check(mid, plus, minus) == True:
			high = mid
		else:
			low = mid
	return high
for _ in range(int(input())):
	X = int(input())
	temp = list(map(int, input().split()))
	B = temp[0]
	minus = []
	cnt = 1
	maxval = 1
	for i in range(B):
		minus.append([temp[cnt], temp[cnt + 1]])
		maxval += temp[cnt + 1]
		cnt += 2
	temp = list(map(int, input().split()))
	C = temp[0]
	cnt = 1
	plus = []
	for i in range(C):
		plus.append([temp[cnt], temp[cnt + 1], temp[cnt + 2]])
		cnt += 3
	if B == 0:
		print(1)
	elif C == 0:
		print(maxval)
	else:
		print(solve(plus, minus, X, maxval))


def binser(l, r, ans):
	low = l
	high = r
	while low <= high:
		mid = (low + high) // 2
		if possible(mid):
			ans = min(ans, mid)
			high = mid - 1
		else:
			low = mid + 1
	return ans

def possible(n):
	v = n
	for i in range(len(li)):
		if li[i][0][1]:
			v -= li[i][1][0]
		elif v >= li[i][1][0]:
			v += li[i][1][1]
	return v > 0
t = int(input())
for _ in range(t):
	x = int(input())
	temp = list(map(int, input().split()))
	ans = 0
	q = 1
	i = 1
	li = []
	while i < 2 * temp[0]:
		li.append([[temp[i], True], [temp[i + 1], 0]])
		q = q + temp[i + 1]
		i = i + 2
	temp = list(map(int, input().split()))
	i = 1
	while i < 3 * temp[0]:
		li.append([[temp[i], False], [temp[i + 1], temp[i + 2]]])
		i = i + 3
	li.sort()
	print(binser(1, q, q))


def solve():
	X = int(input(''))
	g = input('').split()
	B = g[0]
	x = []
	lo = 1
	hi = 1
	for j in range(1, len(g), 2):
		hi += int(g[j + 1])
		x.append([int(g[j]), int(g[j + 1])])
	h = input('').split()
	C = h[0]
	p = []
	for j in range(1, len(h), 3):
		p.append([int(h[j]), int(h[j + 1]), int(h[j + 2])])
	while hi > lo:
		m = (lo + hi) // 2
		mid = m
		i = j = 0
		while i < len(x) and j < len(p):
			if x[i][0] > p[j][0]:
				if m >= p[j][1]:
					m += p[j][2]
				j += 1
			elif x[i][0] < p[j][0]:
				if m > x[i][1]:
					m -= x[i][1]
				else:
					m -= x[i][1]
					lo = mid + 1
					i += 1
					break
				i += 1
			else:
				if m >= p[j][1]:
					m += p[j][2]
				j += 1
				if m > x[i][1]:
					m -= x[i][1]
				else:
					lo = mid + 1
					break
				i += 1
		if i < len(x):
			while i < len(x):
				m -= x[i][1]
				i += 1
		if m <= 0:
			lo = mid + 1
			continue
		hi = mid
	return hi
for i in range(0, int(input(''))):
	print(solve())


def sufficient_log(dishes, clans, k, b, c):
	(i, j) = (0, 0)
	while i < b and j < c:
		if dishes[i] < clans[j]:
			k = k - dishes[i][1]
			if k <= 0:
				return False
			i += 1
		else:
			if clans[j][1] <= k:
				k += clans[j][2]
			j += 1
	for l in range(i, b):
		k = k - dishes[l][1]
		if k <= 0:
			return False
	return True
for z in range(int(input())):
	x = int(input())
	dis = list(map(int, input().split()))
	b = dis[0]
	dishes = []
	for i in range(b):
		dishes.append((dis[2 * i + 1], dis[2 * i + 2]))
	dishes.sort()
	cla = list(map(int, input().split()))
	c = cla[0]
	clans = []
	for i in range(c):
		clans.append((cla[3 * i + 1], cla[3 * i + 2], cla[3 * i + 3]))
	clans.sort()
	mn = 1
	mx = 1
	for i in range(b):
		mx += dishes[i][1]
	while mn < mx:
		mid = (mn + mx) // 2
		if sufficient_log(dishes, clans, mid, b, c):
			mx = mid
		else:
			mn = mid + 1
	print(mn)


def comp(cakes, clans, x, c, val):
	i = 0
	j = 0
	while i < x:
		while j < c and clans[j][0] < cakes[i][0]:
			if clans[j][1] <= val:
				val += clans[j][2]
			j += 1
		if val <= cakes[i][1]:
			return -1
		else:
			val -= cakes[i][1]
		i += 1
	return val
for _ in range(int(input().strip())):
	dist = int(input().strip())
	a = list(map(int, input().strip().split()))
	cakes = []
	x = a[0]
	for i in range(1, 2 * x, 2):
		cakes.append([a[i], a[i + 1]])
	b = list(map(int, input().strip().split()))
	clans = []
	c = b[0]
	for i in range(1, 3 * (c - 1) + 2, 3):
		clans.append([b[i], b[i + 1], b[i + 2]])
	cakes_sum = 0
	for i in range(x):
		cakes_sum += cakes[i][1]
	if c == 0:
		print(cakes_sum + 1)
	else:
		start = 1
		end = cakes_sum + 1
		remain = 0
		while start < end:
			mid = (start + end) // 2
			remain = comp(cakes, clans, x, c, mid)
			if remain == -1:
				start = mid + 1
			else:
				end = mid
		print(end)


import sys

def possible(val, path):
	for item in path:
		if item[1] == 0:
			val -= item[2]
		elif val >= item[2]:
			val += item[3]
	return val > 0

def findans(maxY, path):
	high = maxY + 100
	low = 1
	ans = maxY + 100
	while low <= high:
		mid = (low + high) // 2
		if possible(mid, path):
			ans = min(ans, mid)
			high = mid - 1
		else:
			low = mid + 1
	return ans
for _ in range(int(input())):
	X = int(input())
	path = []
	maxY = 0
	(b, *arr) = [int(c) for c in input().split()]
	for i in range(0, len(arr), 2):
		x = arr[i]
		y = arr[i + 1]
		path.append((x, 0, y, 0))
		maxY += y
	(c, *arr) = [int(c) for c in input().split()]
	for i in range(0, len(arr), 3):
		p = arr[i]
		q = arr[i + 1]
		r = arr[i + 2]
		path.append((p, 1, q, r))
	path.sort(key=lambda x: x[0])
	print(findans(maxY, path))


def check(chef, road):
	for v in road:
		if chef == 0:
			return False
		if len(v) == 2:
			chef -= v[1]
		elif v[1] <= chef:
			chef += v[2]
	if chef >= 1:
		return True
	else:
		return False
t = int(input())
for z in range(t):
	answer = 0
	X = int(input())
	dishes = list(map(int, input().split()))
	clans = list(map(int, input().split()))
	max_chef = 0
	for i in range(2, len(dishes), 2):
		max_chef += dishes[i]
	if clans[0] == 0:
		answer = max_chef + 1
	else:
		road = []
		for i in range(1, dishes[0] * 2 + 1, 2):
			road.append([dishes[i], dishes[i + 1]])
		for i in range(1, clans[0] * 3 + 1, 3):
			road.append([clans[i], clans[i + 1], clans[i + 2]])
		road.sort(key=lambda x: x[0])
		low = 1
		high = max_chef + 1
		while low < high:
			mid = low + (high - low) // 2
			if check(mid, road):
				high = mid
			else:
				low = mid + 1
		answer = low
	print(answer)


def fun(x, X, B, C, d, c):
	i = 0
	j = 0
	count = 0
	per = x
	while i < 2 * d:
		di = B[i]
		if j + 2 < c * 3:
			pj = C[j]
		else:
			pj = None
		if pj != None and pj == di:
			if per >= C[j + 1]:
				per += C[j + 2]
				j += 3
			per -= B[i + 1]
			if per <= 0:
				break
			i += 2
		elif pj != None and pj < di:
			if per >= C[j + 1]:
				per += C[j + 2]
			j += 3
		else:
			per -= B[i + 1]
			if per <= 0:
				break
			i += 2
	if per >= 1:
		return True
	else:
		return False

def binaryfun(d, c, B, C, i, x, X):
	if i <= x:
		m = (x + i) // 2
		if fun(m, X, B, C, d, c) == True:
			return binaryfun(d, c, B, C, i, m - 1, X)
		else:
			return binaryfun(d, c, B, C, m + 1, x, X)
	else:
		return max(i, x)
for _ in range(int(input())):
	X = int(input())
	B = [int(x) for x in input().split()]
	d = B.pop(0)
	C = [int(x) for x in input().split()]
	c = C.pop(0)
	x = 0
	for i in range(1, len(B), 2):
		x += B[i]
	x += 1
	if c == 0:
		print(x)
	else:
		print(binaryfun(d, c, B, C, 1, x, X))