Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a tree with $N$ vertices (numbered $1$ through $N$). Its edges are numbered $1$ through $N-1$. For each valid $i$, there is an integer $a_{i}$ written on the $i$-th vertex. Also, for each valid $i$, there is an integer $b_{i}$ written on the $i$-th edge.

You want the following condition to be satisfied: for each vertex $v$ and each edge $e$ adjacent to $v$, $a_{v} ≥ b_{e}$. In order to achieve that, you may perform an arbitrary number of steps (including zero). In one step, you may perform one the following operations:
1. Select two different vertices $u$ and $v$. Swap $a_{u}$ and $a_{v}$.
2. Select two different edges $e$ and $f$. Swap $b_{e}$ and $b_{f}$.
3. Select a vertex $v$ and an integer $x$. Change $a_{v}$ to $x$ and pay one coin.

Calculate the minimum number of coins you need in order to satisfy the required condition.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N-1$ lines follow. For each $i$ ($1 ≤ i ≤ N-1$), the $i$-th of these lines contains three space-separated integers $u_{i}$, $v_{i}$ and $b_{i}$ denoting that the $i$-th edge connects vertices $u_{i}$ and $v_{i}$ and the initial value written on it is $b_{i}$.
The last line contains $N$ space-separated integers $a_{1}, a_{2}, \ldots, a_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum necessary number of coins.

------  Constraints  ------
$1 ≤ T ≤ 10$
$2 ≤ N ≤ 100,000$
$1 ≤ u_{i}, v_{i} ≤ N$ for each valid $i$
$1 ≤ b_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ a_{i} ≤ 10^{9}$ for each valid $i$
the graph on the input is a tree

------  Subtasks ------
Subtask #1 (10 points): $N ≤ 7$

Subtask #2 (10 points): $N ≤ 10$

Subtask #3 (30 points): $N ≤ 200$

Subtask #4 (50 points): original constraints

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

3

1 2 4

2 3 7

1 5 10
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
Example case 1: There is no way to satisfy the required condition without paying any coins. When we have one coin, we can perform the following operations:
- Swap the integers written on vertices $1$ and $2$.
- Pay one coin and change the integer written on vertex $2$ to $7$.

Source: codechef | Difficulty: HARD
Tags: Sorting

Greedy algorithms

Complete search

Mathematics

Data structures


Solutions:
def printMinCoins(edges, vertices):
	edges.sort(reverse=True)
	vertices.sort(reverse=True)
	edgeCount = len(edges)
	minCoins = 0
	i = 0
	if vertices[i] >= edges[0]:
		i += 1
	else:
		minCoins += 1
	for j in range(len(edges)):
		if vertices[i] >= edges[j]:
			i += 1
		else:
			minCoins += 1
	print(minCoins)
T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	edges = []
	for i in range(N - 1):
		x = list(map(int, input().split()))
		edges.append(x[2])
	vertices = list(map(int, input().split()))
	printMinCoins(edges, vertices)


import sys
T = int(input())
for t in range(T):
	N = int(sys.stdin.readline())
	nei = [set([]) for _ in range(N + 1)]
	edge_values = [None] * (N - 1)
	for n in range(N - 1):
		(a, b, v) = list(map(int, input().split()))
		nei[a].add(b)
		nei[b].add(a)
		edge_values[n] = v
	node_values = list(map(int, input().split()))
	node_values.sort(reverse=True)
	edge_values.sort(reverse=True)
	todo = [1]
	edge_values = [edge_values[0]] + edge_values
	edgevalidx = 0
	nodevalidx = 0
	while todo:
		node = todo.pop()
		last_edge = edge_values[edgevalidx]
		edgevalidx += 1
		if node_values[nodevalidx] >= last_edge:
			nodevalidx += 1
		for neighbour in nei[node]:
			nei[neighbour].remove(node)
		todo.extend(nei[node])
	print(N - nodevalidx)


T = int(input())
for t in range(T):
	N = int(input())
	weight = []
	for i in range(N - 1):
		weight.append([int(b) for b in input().split()][2])
	weight.sort(reverse=True)
	weight = [weight[0]] + weight
	nodes = [int(b) for b in input().split()]
	nodes.sort(reverse=True)
	ans = 0
	j = 0
	for i in weight:
		if i > nodes[j]:
			ans += 1
		else:
			j += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	weights = []
	ans = 0
	for x in range(n - 1):
		(u, v, w) = map(int, input().split())
		weights.append(w)
	weights.sort(reverse=True)
	weights = [weights[0]] + weights
	nodes = list(map(int, input().split()))
	nodes.sort(reverse=True)
	curr = 0
	for i in weights:
		if i > nodes[curr]:
			ans += 1
		else:
			curr += 1
	print(ans)


def testcase():
	n = int(input())
	edge = []
	maxx = 0
	for i in range(n - 1):
		(u, v, b) = [int(_) for _ in input().split()]
		edge.append(b)
		maxx = max(maxx, b)
	edge.append(maxx)
	weight = [int(i) for i in input().split()]
	count = 0
	edge.sort(reverse=True)
	weight.sort(reverse=True)
	j = 0
	for i in edge:
		if i > weight[j]:
			count += 1
		else:
			j += 1
	print(count)
t = int(input())
for test in range(t):
	testcase()


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

def ai():
	a = list(map(int, input().split()))
	return a

def mi():
	a = map(int, input().split())
	return a
for _ in range(ii()):
	n = ii()
	e = []
	for i in range(n - 1):
		(a, b, c) = mi()
		e.append(c)
	v = ai()
	v.sort(reverse=True)
	e.sort(reverse=True)
	ans = 0
	e.insert(0, e[0])
	j = 0
	for i in range(n):
		ew = e[i]
		if v[j] < ew:
			ans += 1
		else:
			j += 1
	print(ans)


def main(debug=False):
	for _ in range(int(input())):
		n = int(input())
		W = []
		for i in range(n - 1):
			(u, v, wi) = map(int, input().split())
			W.append(wi)
		N = list(map(int, input().split()))
		N = sorted(N, reverse=True)
		W = sorted(W, reverse=True)
		W.insert(1, W[0])
		if debug:
			print('W', W)
			print('N', N)
		j = 0
		cnt = 0
		for i in W:
			if debug:
				print('for W[i]=', i, 'and N[j]=', N[j])
			if i > N[j]:
				cnt += 1
			else:
				j += 1
			if debug:
				print('cnt for this iteration is', cnt)
		print(cnt)
main(debug=False)


t = int(input())
for u in range(t):
	n = int(input())
	be = []
	av = []
	for i in range(n - 1):
		(u, v, e) = map(int, input().split())
		be.append(e)
	av = [int(x) for x in input().split()]
	av.sort(reverse=True)
	be.sort(reverse=True)
	be.append(be[0])
	be.sort(reverse=True)
	j = 0
	count = 0
	for i in be:
		if i > av[j]:
			count += 1
		else:
			j += 1
	print(count)


for case in range(int(input())):
	n = int(input())
	b = [0] * (n - 1)
	for i in range(n - 1):
		st = input().split()
		b[i] = int(st[-1])
	a = list(map(int, input().split()))
	a.sort()
	b.sort()
	(vind, eind) = (0, 0)
	ans = 0
	while vind < n and eind < n - 1:
		if a[vind] >= b[eind]:
			vind += 1
			eind += 1
		else:
			ans += 1
			vind += 1
	print(ans)


T = int(input())
while T:
	T -= 1
	N = int(input())
	e = []
	for i in range(N - 1):
		(u, v, w) = map(int, input().split())
		e.append(w)
	n = list(map(int, input().split()))
	n.sort(reverse=True)
	e.sort(reverse=True)
	e.insert(1, e[0])
	count = 0
	j = 0
	for i in range(N):
		if n[j] < e[i]:
			count += 1
		else:
			j += 1
	print(count)


for t in range(int(input())):
	n = int(input())
	edges = []
	vertices = []
	for i in range(n - 1):
		(u, v, w) = map(int, input().split(' '))
		edges.append(w)
	vertices = list(map(int, input().split(' ')))
	edges.sort(key=None, reverse=True)
	vertices.sort(key=None, reverse=True)
	edges.insert(0, edges[0])
	i = 0
	j = 0
	ans = 0
	while i < n and j < n:
		if vertices[j] >= edges[i]:
			j += 1
			i += 1
		else:
			ans += 1
			i += 1
	print(ans)


def testcase():
	n = int(input())
	node = set()
	weight = []
	maximumWeight = 0
	for i in range(n - 1):
		(u, v, w) = [int(_) for _ in input().split()]
		weight.append(w)
		maximumWeight = max(maximumWeight, w)
	weight.append(maximumWeight)
	weight.sort(reverse=True)
	node = [int(i) for i in input().split()]
	node.sort(reverse=True)
	j = 0
	counter = 0
	for i in weight:
		if i > node[j]:
			counter += 1
		else:
			j += 1
	print(counter)
t = int(input())
for test in range(t):
	testcase()


T = int(input())
for t in range(T):
	n = int(input())
	edges = list(sorted((int(input().split()[-1]) for i in range(n - 1))))
	nodes = list(sorted(map(int, input().split())))
	(j, cnt) = (0, 0)
	for i in range(n - 1):
		while j < len(nodes) and nodes[j] < edges[i]:
			j += 1
			cnt += 1
		j += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n - 1):
		(val1, val2, val3) = list(map(int, input().split()))
		a.append(val3)
	a.sort()
	arr = list(map(int, input().split()))
	arr.sort()
	(i, j, ans) = (0, 0, 0)
	while True:
		if arr[i] >= a[j]:
			i += 1
			j += 1
		else:
			i += 1
			ans += 1
		if j == n - 1 or i == n:
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	edges = []
	for _ in range(n - 1):
		(u, v, e) = input().split()
		edges.append(int(e))
	vertices = list(map(int, input().split()))
	vertices.sort()
	edges.sort()
	i = 0
	j = 0
	cnt = 0
	while i < n and j < n - 1:
		if vertices[i] < edges[j]:
			i += 1
			cnt += 1
		else:
			i += 1
			j += 1
	print(cnt)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	be = []
	for i in range(n - 1):
		(ui, vi, bi) = map(int, input().split())
		be.append(bi)
	ae = list(map(int, input().split()))
	be.sort()
	ae.sort()
	be = be + [be[-1]]
	i = len(ae) - 1
	j = len(be) - 1
	ans = 0
	while i >= 0 and j >= 0:
		if ae[i] < be[j]:
			ans += 1
		else:
			i -= 1
		j -= 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	b = list()
	for i in range(n - 1):
		(u, v, bi) = map(int, input().split())
		b.append(bi)
	a = list(map(int, input().split()))
	a.sort()
	b.sort()
	(i, j, ans) = (0, 0, 0)
	while True:
		if a[i] >= b[j]:
			i += 1
			j += 1
		else:
			i += 1
			ans += 1
		if j == n - 1 or i == n:
			break
	print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = []
	b = []
	for i in range(n - 1):
		b.append(int(input().split()[2]))
	a = list(map(int, input().split()))
	b.sort(reverse=1)
	a.sort(reverse=1)
	ans = 0
	i = 0
	j = 0
	if b[j] > a[i]:
		ans += 2
		j += 1
	else:
		i += 1
	while j < n - 1:
		if b[j] > a[i]:
			ans += 1
			j += 1
		else:
			i += 1
			j += 1
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	Adj = defaultdict(list)
	Ew = []
	Vertex = defaultdict(int)
	for i in range(N - 1):
		(a, b, w) = map(int, input().split())
		Adj[a].append(b)
		Adj[b].append(a)
		Ew.append(w)
	Vkey = sorted(list(map(int, input().split())))
	Ew = sorted(Ew)
	Change = 0
	if Vkey[-1] < Ew[0]:
		print(N)
		continue
	elif Vkey[0] > Ew[-1]:
		print('0')
		continue
	Start = [1]
	i = 0
	while True:
		NewStart = []
		if len(Start) == 0:
			break
		for x in Start:
			Neigh = Adj[x]
			Neighbour = []
			for ooo in Neigh:
				if Vertex[ooo] == 0:
					Neighbour.append(ooo)
			for neigh in Neighbour:
				e = Ew.pop()
				if Vertex[x] == 0:
					if Vkey[-1] >= e:
						Vertex[x] = Vkey.pop()
					else:
						Vertex[x] = e
						Change += 1
						Vkey[i] = -1
						i = i + 1
				if Vertex[neigh] == 0:
					if Vkey[-1] >= e:
						Vertex[neigh] = Vkey.pop()
					else:
						Vertex[neigh] = e
						Change += 1
						Vkey[i] = -1
						i = i + 1
				if len(Adj[neigh]) > 1:
					NewStart.append(neigh)
		Start = NewStart
	print(Change)


t = int(input())
while t:
	t -= 1
	n = int(input())
	ed = []
	for i in range(n - 1):
		(l, r, e) = map(int, input().split())
		ed.append(e)
	a = list(map(int, input().split()))
	ed.sort()
	a.sort()
	(i, j, res) = (0, 0, 0)
	while 100:
		if a[i] >= ed[j]:
			i += 1
			j += 1
		else:
			i += 1
			res += 1
		if i == n or j == n - 1:
			break
	print(res)


for _ in range(int(input())):
	N = int(input())
	V = []
	E = []
	k = 0
	for i in range(N - 1):
		E.append(int(input().split()[-1]))
	E.sort(reverse=True)
	E = [E[0]] + E
	V = sorted(map(int, input().split()), reverse=True)
	j = 0
	for i in E:
		if V[j] < i:
			k += 1
		else:
			j += 1
	print(k)


t = int(input())
while t:
	t -= 1
	n = int(input())
	vertices = []
	edges = []
	for i in range(n - 1):
		(u, v, b) = map(int, input().split())
		edges.append(b)
	vertices = list(map(int, input().split()))
	edges.sort()
	vertices.sort()
	ans = 0
	(i, j) = (0, 0)
	while i < n and j < n - 1:
		if edges[j] <= vertices[i]:
			j += 1
			i += 1
		else:
			ans += 1
			i += 1
	print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	edges = []
	for n in range(N - 1):
		edges.append(int(input().split()[-1]))
	vertices = [int(num) for num in input().split()]
	edges.sort()
	vertices.sort()
	edges.append(edges[-1])
	e = 0
	v = 0
	while v < N:
		if vertices[v] >= edges[e]:
			e += 1
		v += 1
	print(N - e)


test = int(input())
for intnn in range(test):
	num = int(input())
	array = []
	for i in range(num - 1):
		(val1, val2, val3) = list(map(int, input().split()))
		array.append(val3)
	arr = list(map(int, input().split()))
	arr.sort()
	array.sort()
	ar = []
	for i in range(num):
		ar.append(i)
	i = 0
	j = 0
	ans = 0
	while True:
		if arr[i] >= array[j]:
			i += 1
			j += 1
		else:
			i += 1
			ans += 1
		if j == num - 1 or i == num:
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	b = [0] * (n - 1)
	for i in range(n - 1):
		(u, v, b[i]) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b.sort()
	a.sort()
	ans = 0
	(vind, eind) = (0, 0)
	while vind < n and eind < n - 1:
		if a[vind] >= b[eind]:
			vind += 1
			eind += 1
		else:
			ans += 1
			vind += 1
	print(ans)


import numpy as np
i8 = np.int64

def solve_core(a, b):
	i = 0
	count = 0
	for j in range(b.shape[0]):
		while i < a.shape[0]:
			if a[i] >= b[j]:
				count += 1
				i += 1
				break
			i += 1
	if i < a.shape[0]:
		count += 1
	return count

def solve(stdin):
	N = int(stdin.readline())
	b = np.empty(N - 1, i8)
	for i in range(N - 1):
		(u, v, b[i]) = map(int, stdin.readline().split())
	a = np.fromstring(stdin.readline(), i8, sep=' ')
	a.sort()
	b.sort()
	res = solve_core(a, b)
	return N - res
stdin = open(0)
T = int(stdin.readline())
for _ in range(T):
	ans = solve(stdin)
	print(ans)


from sys import stdin
t = int(stdin.readline())

def makeGraph(a, b):
	idxA = 0
	idxB = 0
	k = 0
	b = [b[0]] + b
	while idxB < n:
		node = a[idxA]
		while idxB < n and node < b[idxB]:
			k += 1
			idxB += 1
		idxA += 1
		idxB += 1
	return k
for _ in range(t):
	n = int(stdin.readline())
	b = []
	for i in range(n - 1):
		(ui, vi, bi) = list(map(int, stdin.readline().split()))
		b.append(bi)
	a = list(map(int, stdin.readline().split()))
	a = sorted(a, reverse=True)
	b = sorted(b, reverse=True)
	res = makeGraph(a, b)
	print(res)


for _ in range(int(input())):
	n = int(input())
	d = {}
	deg = {}
	weight = []
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		weight.append(w)
		if d.get(u) == None:
			d[u] = [v]
			deg[u] = 1
		else:
			d[u].append(v)
			deg[u] += 1
		if d.get(v) == None:
			d[v] = [u]
			deg[v] = 1
		else:
			d[v].append(u)
			deg[v] += 1
	node = list(map(int, input().split()))
	node.sort(reverse=True)
	weight.sort(reverse=True)
	weight.insert(1, weight[0])
	count = 0
	j = 0
	for i in range(n):
		if weight[i] > node[j]:
			count += 1
		else:
			j += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	st = []
	en = []
	wt = {}
	m = []
	s_e = {}
	e_s = {}
	for __ in range(n - 1):
		(s, e, edj) = map(int, input().split())
		m.append(edj)
		s_e[s] = e
		e_s[e] = s
	ver = list(map(int, input().split()))
	m.sort()
	ver.sort()
	for i in range(1, n + 1):
		wt[i] = 0
	c = 0
	v = 0
	e = 0
	ans = 0
	while v < n and e < n - 1:
		i = 1
		c = 0
		while i < n + 1 and v < n and (e < n - 1):
			if v < n and e < n - 1:
				if wt[i] <= ver[v] and ver[v] >= m[e]:
					try:
						wt[e_s[i]] = m[e]
					except:
						wt[s_e[i]] = m[e]
					v += 1
					e += 1
				else:
					v += 1
					ans += 1
			i += 1
	print(ans)


from sys import *

def input():
	return stdin.readline()
for _ in range(int(input())):
	n = int(input())
	st = []
	en = []
	wt = {}
	m = []
	s_e = {}
	e_s = {}
	for __ in range(n - 1):
		(s, e, edj) = map(int, input().split())
		m.append(edj)
		s_e[s] = e
		e_s[e] = s
	ver = list(map(int, input().split()))
	m.sort()
	ver.sort()
	for i in range(1, n + 1):
		wt[i] = 0
	c = 0
	v = 0
	e = 0
	ans = 0
	while v < n and e < n - 1:
		i = 1
		c = 0
		while i < n + 1 and v < n and (e < n - 1):
			if v < n and e < n - 1:
				if wt[i] <= ver[v] and ver[v] >= m[e]:
					try:
						wt[e_s[i]] = m[e]
					except:
						wt[s_e[i]] = m[e]
					v += 1
					e += 1
				else:
					v += 1
					ans += 1
			i += 1
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	ew = []
	for i in range(n - 1):
		arr = [int(x) for x in input().split()]
		ew.append(arr[2])
	vw = [int(x) for x in input().split()]
	vw.sort()
	ew.sort()
	ans = 0
	vIt = len(vw) - 1
	eIt = len(ew) - 1
	req = 2
	vSize = len(vw)
	while vSize > 0:
		if vIt < 0 or eIt < 0:
			break
		v1 = vw[vIt]
		e1 = ew[eIt]
		if v1 < e1:
			if req > 0:
				ans += req
				vSize -= req
				req = 0
			eIt = eIt - 1
			req = req + 1
		else:
			req = req - 1
			vIt = vIt - 1
			vSize = vSize - 1
	print(ans)
	t = t - 1


from sys import *
from collections import *

def input():
	return stdin.readline()
for _ in range(int(input())):
	n = int(input())
	b = []
	for edge in range(n - 1):
		(x, y, wt) = map(int, input().split())
		b.append(wt)
	b.sort()
	a = deque(sorted([int(i) for i in input().split()]))
	cnt = 0
	if a[-1] >= b[-1]:
		a.pop()
	else:
		a.popleft()
		cnt += 1
	while len(b) != 0:
		if a[-1] >= b[-1]:
			a.pop()
		else:
			a.popleft()
			cnt += 1
		b.pop()
	print(cnt)


for i in range(int(input())):
	(n, p) = (int(input()), [])
	for j in range(n - 1):
		p.append([int(j) for j in input().split()][2])
	q = sorted([int(j) for j in input().split()])
	p.sort()
	(c, j, k) = (n, 0, 0)
	while k < n:
		if q[k] >= p[0]:
			(k, c) = (k + 1, c - 1)
			break
		k += 1
	while k < n and j < n - 2:
		if q[k] >= p[j] and q[k] >= p[j + 1]:
			(j, k, c) = (j + 1, k + 1, c - 1)
		else:
			k += 1
	print(c - int(k != n and q[-1] >= p[-1]))


for _ in range(int(input())):
	n = int(input())
	edge_nums = [0] * (n - 1)
	for i in range(n - 1):
		(x, y, z) = map(int, input().split())
		edge_nums[i] = z
	edge_nums.sort()
	vertex_nums = list(map(int, input().split()))
	vertex_nums.sort()
	j = 0
	count = 0
	for i in range(n):
		if vertex_nums[i] < edge_nums[j]:
			count += 1
		else:
			j += 1
			if j == n - 1:
				break
	print(count)


T = int(input())
for time in range(T):
	N = int(input())
	A = []
	B = []
	res = 0
	a1 = 0
	b1 = 0
	for itr in range(N - 1):
		(u, v, b) = map(int, input().split())
		B.append(b)
	A = list(map(int, input().split()))
	A.sort()
	B.sort()
	while a1 < N and b1 < N - 1:
		if A[a1] >= B[b1]:
			a1 += 1
			b1 += 1
		else:
			a1 += 1
			res += 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	ver = []
	ed = []
	for _ in range(n - 1):
		(a, b, x) = map(int, input().split())
		ed.append(x)
	ver = list(map(int, input().split()))
	ed.sort()
	ver.sort()
	answer = 0
	i = 0
	j = 0
	while i < n and j < n - 1:
		if ver[i] >= ed[j]:
			i += 1
			j += 1
		else:
			i += 1
			answer += 1
	print(answer)


t = int(input())
for _ in range(t):
	n = int(input())
	vertex = []
	edge = []
	l = []
	for _ in range(n - 1):
		(a, b, x) = map(int, input().split())
		l.append([a, b])
		edge.append(x)
	vertex = list(map(int, input().split()))
	edge.sort()
	vertex.sort()
	ans = 0
	i = 0
	j = 0
	while i < n and j < n - 1:
		if vertex[i] >= edge[j]:
			i += 1
			j += 1
		else:
			i += 1
			ans += 1
	print(ans)


for t in range(int(input())):
	n = int(input())
	e = []
	for i in range(n - 1):
		(x, y, z) = map(int, input().split())
		e.append(z)
	e.sort()
	v = list(map(int, input().split()))
	v.sort()
	h = [0] * (n - 1)
	hind = 0
	vind = 0
	while hind < n - 1 and vind < n:
		if v[vind] < e[hind]:
			vind += 1
			continue
		if v[vind] >= e[hind]:
			h[hind] = vind
			hind += 1
			continue
	if hind < n - 1:
		for i in range(hind, n - 1):
			h[i] = vind
	ans = 0
	for i in range(n - 1):
		ans += max(0, h[i] - i - ans)
	print(ans)


import collections
t = int(input())
for _ in range(t):
	n = int(input())
	adj = [[] for i in range(n + 1)]
	a = []
	b = []
	for i in range(n - 1):
		(x, y, z) = map(int, input().split())
		adj[x].append(y)
		b.append(z)
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	(root, x, y) = (1, 0, 0)
	coins = 0
	if a[0] >= b[0]:
		x += 1
	else:
		coins = 1
	queue = collections.deque([root])
	sz = 1
	while queue:
		vertex = queue.popleft()
		sz -= 1
		for neighbour in adj[vertex]:
			queue.append(neighbour)
		if sz == 0:
			sz = len(queue)
			for _ in queue:
				if a[x] >= b[y]:
					x += 1
				else:
					coins += 1
				y += 1
	print(coins)


def DecimalToBinary(num):
	if num > 1:
		DecimalToBinary(num // 2)
from math import ceil, log2

def getMid(s, e):
	return s + (e - s) // 2

def getSumUtil(st, ss, se, qs, qe, si):
	if qs <= ss and qe >= se:
		return st[si]
	if se < qs or ss > qe:
		return 0
	mid = getMid(ss, se)
	return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2)

def updateValueUtil(st, ss, se, i, diff, si):
	if i < ss or i > se:
		return
	st[si] = st[si] + diff
	if se != ss:
		mid = getMid(ss, se)
		updateValueUtil(st, ss, mid, i, diff, 2 * si + 1)
		updateValueUtil(st, mid + 1, se, i, diff, 2 * si + 2)

def updateValue(arr, st, n, i, new_val):
	if i < 0 or i > n - 1:
		print('Invalid Input', end='')
		return
	diff = new_val - arr[i]
	arr[i] = new_val
	updateValueUtil(st, 0, n - 1, i, diff, 0)

def getSum(st, n, qs, qe):
	if qs < 0 or qe > n - 1 or qs > qe:
		print('Invalid Input', end='')
		return -1
	return getSumUtil(st, 0, n - 1, qs, qe, 0)

def constructSTUtil(arr, ss, se, st, si):
	if ss == se:
		st[si] = arr[ss]
		return arr[ss]
	mid = getMid(ss, se)
	st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) + constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)
	return st[si]

def constructST(arr, n):
	x = int(ceil(log2(n)))
	max_size = 2 * int(2 ** x) - 1
	st = [0] * max_size
	constructSTUtil(arr, 0, n - 1, st, 0)
	return st
u1 = 0
u2 = 113423443243442434
u3 = u1 + u2
u1 = 0
u2 = 113423443243442434
u3 = u1 + u2
u1 = 0
u2 = 113423443243442434
u3 = u1 + u2
u1 = 0
u2 = 113423443243442434
u3 = u1 + u2
u1 = 0
u2 = 113423443243442434
u3 = u1 + u2
u1 = 0
u2 = 113423443243442434
u3 = u1 + u2
for chandrima in range(int(input())):
	sandeep = []
	somdutta = []
	rashmi = int(input())
	for arnab in range(rashmi - 1):
		(debanjan, soham, shahid) = [int(x) for x in input().split()]
		sandeep.append(shahid)
	somdutta = list(map(int, input().split()))
	sandeep.sort()
	somdutta.sort()
	estrossa = 0
	meliodas = 0
	sfnjsjadjadjadjadaash = 0
	justforfun = 1
	while estrossa < rashmi - 1 and meliodas < rashmi:
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		justforfun += 1
		justforfun -= 1
		while somdutta[meliodas] < sandeep[estrossa]:
			justforfun += 1
			justforfun -= 1
			meliodas += 1
			sfnjsjadjadjadjadaash += 1
			if meliodas == rashmi:
				break
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
				u1 = 0
				u2 = 113423443243442434
				u3 = u1 + u2
		estrossa += 1
		meliodas += 1
	u1 = 0
	u2 = 113423443243442434
	u3 = u1 + u2
	u1 = 0
	u2 = 113423443243442434
	u3 = u1 + u2
	u1 = 0
	u2 = 113423443243442434
	u3 = u1 + u2
	print(sfnjsjadjadjadjadaash)
if False:
	num = 276768623 + 2112
	if num % 2 == 0:
		u1 = 1
	else:
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2
		u1 = 0
		u2 = 113423443243442434
		u3 = u1 + u2


T = int(input())
for i in range(T):
	N = int(input())
	b = []
	a = []
	for j in range(N - 1):
		edge = input().split()
		b.append(int(edge[2]))
	vertex_values = input().split()
	for j in range(N):
		a.append(int(vertex_values[j]))
	a.sort()
	b.sort()
	great = len(a) * [0]
	pos_b = 0
	pos_a = 0
	while pos_b < N - 1 and pos_a < N:
		if b[pos_b] <= a[pos_a]:
			pos_b += 1
		else:
			great[pos_a] = pos_b
			pos_a += 1
	while pos_a < N:
		great[pos_a] = N - 1
		pos_a += 1
	coins = 0
	desired = list(range(1, N))
	desired.append(N - 1)
	for j in range(0, N):
		if great[j] < desired[j - coins]:
			coins += 1
	print(coins)


from collections import deque

def bfs(tree, edges, nodes):
	coins = 0
	visited = [False] * len(nodes)
	(i, j) = (0, len(nodes) - 1)
	if edges and nodes[i] >= edges[len(edges) - 1]:
		i += 1
	else:
		j -= 1
		coins += 1
	q = deque([1])
	visited[0] = True
	while q:
		s = q.popleft()
		for v in tree[s]:
			if not visited[v - 1]:
				if edges and nodes[i] >= edges[len(edges) - 1]:
					i += 1
				else:
					j -= 1
					coins += 1
				edges.pop()
				visited[v - 1] = True
				q.append(v)
	return coins
T = int(input())
for t in range(T):
	N = int(input())
	graph = dict()
	edgeWeights = list()
	for i in range(1, N):
		(u, v, w) = map(int, input().split())
		graph.setdefault(u, list()).append(v)
		graph.setdefault(v, list()).append(u)
		edgeWeights.append(w)
	nodeWeights = list(map(int, input().split()))
	edgeWeights.sort()
	nodeWeights.sort(reverse=True)
	print(bfs(graph, edgeWeights, nodeWeights))


from sys import stdin, stdout
try:
	testcase = stdin.readline()
	for __ in range(0, int(testcase)):
		m = stdin.readline()
		m = int(m)
		b = []
		for i in range(0, m - 1):
			b1 = [int(_) for _ in stdin.readline().split()]
			b.append(b1[2])
		b = sorted(b)
		a = [int(_) for _ in stdin.readline().split()]
		a = sorted(a)
		(ans, j) = (0, 0)
		for i in a:
			if i >= b[j]:
				j += 1
			else:
				ans += 1
			if j == m - 1:
				break
		print(ans)
except:
	pass


from sys import stdin, stdout
n = stdin.readline()
n = int(n)
while n:
	n -= 1
	m = stdin.readline()
	m = int(m)
	b = []
	for i in range(0, m - 1):
		bb = [int(x) for x in stdin.readline().split()]
		b.append(bb[2])
	a = [int(x) for x in stdin.readline().split()]
	b = sorted(b)
	a = sorted(a)
	c = 0
	j = 0
	for i in range(0, m):
		if a[i] >= b[j]:
			j += 1
		else:
			c += 1
		if j == len(b):
			break
	print(c)


for i in range(int(input())):
	n = int(input())
	e = []
	for i in range(n - 1):
		l = list(map(int, input().split()))
		e.append(l[2])
	v = list(map(int, input().split()))
	e = sorted(e)
	v = sorted(v)
	p = e[-1]
	q = v[-1]
	if p > q:
		ans = 2
		e.pop()
		v.pop(0)
		v.pop(0)
	elif p > v[-2]:
		ans = 1
		e.pop()
		v.pop(0)
		v.pop()
	else:
		ans = 0
		e.pop()
		v.pop()
		v.pop()
	a = n - 2
	while a > 0:
		a -= 1
		if e[-1] <= v[-1]:
			e.pop()
			v.pop()
		else:
			ans += 1
			e.pop()
	print(ans)


T = int(input())
for i in range(0, T):
	N = int(input())
	e = []
	r = []
	v = []
	h = 0
	o = 0
	for j in range(0, N - 1):
		e = input().split(' ')
		r.append(int(e[2]))
	v = list(map(int, input().split()))
	v.sort()
	r.sort()
	wa = N - 2
	w = N - 2
	z = r[N - 2]
	while wa >= 0:
		if v[w] < r[wa] and v[w + 1] < r[wa]:
			v.append(z)
			v.append(z)
			w = w + 2
			o += 2
		elif v[w] < r[wa]:
			v.append(z)
			w += 1
			o += 1
		w -= 1
		wa -= 1
	print(o)


class doublylinkedlist:

	class _Node:
		__slots__ = ('data', 'prev', 'next')

		def __init__(self, data, prev, next):
			self.data = data
			self.prev = prev
			self.next = next

	def __init__(self):
		self.head = self._Node(None, None, None)
		self.tail = self._Node(None, None, None)
		self.tail.prev = self.head
		self.head.next = self.tail
		self.size = 0

	def is_empty(self):
		return self.size == 0

	def add_last(self, value):
		new_node = self._Node(value, None, None)
		if self.is_empty():
			self.head = new_node
			self.tail = new_node
		else:
			self.tail.next = new_node
			new_node.prev = self.tail
		self.tail = new_node
		self.size += 1

	def remove_first(self):
		value = self.head.data
		self.head = self.head.next
		self.head.prev = None
		self.size -= 1
		if self.is_empty():
			self.tail = None
		return value

	def remove_last(self):
		value = self.tail.data
		self.tail = self.tail.prev
		self.tail.next = None
		self.size -= 1
		if self.is_empty():
			self.head = None
		return value
for _ in range(int(input())):
	n = int(input())
	edge = list()
	for i in range(n - 1):
		(a, b, c) = map(int, input().split())
		edge.append(c)
	arr = list(map(int, input().split()))
	arr.sort()
	edge.sort()
	dll = doublylinkedlist()
	for i in range(n):
		dll.add_last(arr[i])
	ans = 0
	for i in range(n - 2, -1, -1):
		(t1, t2) = (dll.tail.data, dll.tail.prev.data)
		if t1 >= edge[i] and t2 >= edge[i]:
			dll.remove_last()
			continue
		else:
			if t1 < edge[i]:
				ans += 2
				dll.remove_first()
				dll.remove_first()
				dll.add_last(edge[i])
				dll.add_last(edge[i])
			elif t2 < edge[i]:
				ans += 1
				dll.remove_first()
				dll.add_last(edge[i])
			dll.remove_last()
	print(ans)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	adj = defaultdict(list)
	edgeWeights = []
	vertices = defaultdict(int)
	vertexWeights = []
	for _ in range(n - 1):
		(u, v, b) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
		edgeWeights.append(b)
	vertexWeights = sorted(map(int, input().split()))
	edgeWeights.sort()
	cost = 0
	initial = 0
	toVisit = [1]
	weight = edgeWeights.pop()
	while toVisit:
		newToVisit = []
		for vertex in toVisit:
			adjs = adj[vertex]
			notVisited = []
			for adjVertex in adjs:
				if not vertices[adjVertex]:
					notVisited.append(adjVertex)
			if not vertices[vertex]:
				if vertexWeights[-1] >= weight:
					vertices[vertex] = vertexWeights.pop()
				else:
					cost += 1
					vertices[vertex] = weight
					vertexWeights[initial] = 0
					initial += 1
			for adjVertex in notVisited:
				if vertexWeights[-1] >= weight:
					vertices[adjVertex] = vertexWeights.pop()
				else:
					cost += 1
					vertices[adjVertex] = weight
					vertexWeights[initial] = 0
					initial += 1
				try:
					weight = edgeWeights.pop()
				except:
					pass
				if len(adj[adjVertex]) > 1:
					newToVisit.append(adjVertex)
		toVisit = newToVisit
	print(cost)


t = int(input())
for i in range(t):
	n = int(input())
	edge = []
	for i in range(n - 1):
		(u, v, b) = [int(i) for i in input().split()]
		edge.append(b)
	edge.sort()
	vertex = [int(i) for i in input().split()]
	vertex.sort()
	error = 0
	vv = 0
	ee = 0
	while vv < n and ee < n - 1:
		while vv < n and vertex[vv] < edge[ee]:
			error += 1
			vv += 1
		ee += 1
		vv += 1
	print(error)


for _ in range(int(input())):
	n = int(input())
	if n < 200:
		deg = [0] * n
		graph = [[] for i in range(n + 1)]
		edg = []
		for i in range(n - 1):
			(a, b, c) = map(int, input().split())
			graph[a].append(b)
			graph[b].append(a)
			deg[a - 1] += 1
			deg[b - 1] += 1
			edg.append(c)
		ve = list(map(int, input().split()))
		ve.sort()
		edg.sort()
		ep = 0
		vp = 0
		ans = 0
		while True:
			di = min(deg)
			if di == 0 or di > 10 ** 9:
				break
			fl = 0
			while fl == 0:
				k = ep
				for i in range(di):
					if edg[k] > ve[vp]:
						fl = 0
						break
					k += 1
					fl = 1
				if fl == 0:
					vp += 1
					ve.append(10 ** 9 + 1)
					ans += 1
				else:
					ep = k
					vp += 1
			x = deg.index(di)
			deg[x] = 10 ** 9 + 1
			for i in graph[x + 1]:
				deg[i - 1] -= 1
		print(ans)
	else:
		deg = [0] * n
		graph = [[] for i in range(n + 1)]
		edg = []
		for i in range(n - 1):
			(a, b, c) = map(int, input().split())
			graph[a].append(b)
			graph[b].append(a)
			deg[a - 1] += 1
			deg[b - 1] += 1
			edg.append(c)
		ve = list(map(int, input().split()))
		ve.sort()
		edg.sort()
		op = set()
		for i in range(n):
			if deg[i] == 1:
				op.add(i)
		ep = 0
		vp = 0
		ans = 0
		while True:
			if ep == n - 2:
				break
			if len(op) == 1:
				break
			di = 1
			if di == 0 or di > 10 ** 9:
				break
			fl = 0
			while fl == 0:
				k = ep
				for i in range(di):
					if edg[k] > ve[vp]:
						fl = 0
						break
					k += 1
					fl = 1
				if fl == 0:
					vp += 1
					ve.append(10 ** 9 + 1)
					ans += 1
				else:
					ep = k
					vp += 1
		print(ans)


test = int(input())
for k in range(test):
	vertices = int(input())
	edges = []
	vv = []
	for i in range(vertices - 1):
		arr = list(map(int, input().split()))
		edges.append(arr[2])
	vv = list(map(int, input().split()))
	vv.sort()
	edges.sort()
	coins = 0
	if vv[vertices - 1] < edges[vertices - 2]:
		vv[0] = edges[vertices - 2]
		vv[1] = edges[vertices - 2]
		coins += 2
	elif vv[vertices - 1] >= edges[vertices - 2] and edges[vertices - 2] > vv[vertices - 2]:
		vv[0] = edges[vertices - 2]
		coins += 1
	vv.sort()
	p1 = vertices - 2
	for p2 in range(vertices - 2, -1, -1):
		if vv[p1] >= edges[p2]:
			p1 -= 1
		else:
			coins += 1
	print(coins)


maxi = None
ans = 0

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None
		self.v = 1

def insertNode(root, data, par):
	if root is None:
		if data <= par.data:
			par.left = Node(data)
		else:
			par.right = Node(data)
		return
	if data <= root.data:
		insertNode(root.left, data, root)
	else:
		insertNode(root.right, data, root)

def findJustMax(data, root):
	global maxi
	if root is None:
		return
	if data >= root.data and root.v == 1:
		if maxi is None or root.data > maxi.data:
			maxi = root
		findJustMax(data, root.right)
	else:
		findJustMax(data, root.left)

def giveAns(root):
	global ans
	if root is None:
		return
	if root.v == 1:
		ans += 1
	giveAns(root.left)
	giveAns(root.right)
for h in range(int(input())):
	N = int(input())
	w = []
	for _ in range(N - 1):
		w.append(int(input().strip().split()[2]))
	a = list(map(int, input().strip().split()))
	req = [max(w)] + w
	req.sort()
	a.sort()
	c = 0
	j = 0
	for i in a:
		if i >= req[j]:
			j += 1
		else:
			c += 1
	print(c)


T = int(input())
for _ in range(T):
	N = int(input())
	eWeights = []
	for i in range(N - 1):
		eWeights.append([int(x) for x in input().strip().split()])
	nWeights = [int(x) for x in input().strip().split()]
	n = len(nWeights)
	edgeWeights = []
	nodeWeights = []
	for (u, v, w) in eWeights:
		edgeWeights.append(w)
	INF = 10 ** 10
	nodeWeights = nWeights
	edgeWeights.sort()
	nodeWeights.sort()
	count = 0
	i = 0
	j = 0
	if n > 1000:
		while True:
			if i == len(edgeWeights) - 1:
				break
			if i == len(edgeWeights) - 1:
				if nodeWeights[j] >= edgeWeights[i]:
					if nodeWeights[j + 1] >= edgeWeights[i]:
						break
				if nodeWeights[j + 1] < edgeWeights[i]:
					count += 2
					break
			if nodeWeights[j] >= edgeWeights[i]:
				j += 1
				i += 1
			else:
				j += 1
				nodeWeights.append(10 ** 10)
				count += 1
	else:
		while True:
			if len(edgeWeights) == 0:
				break
			if len(edgeWeights) == 1:
				if nodeWeights[0] >= edgeWeights[0] or nodeWeights[0] == INF:
					if nodeWeights[1] >= edgeWeights[0] or nodeWeights[1] == INF:
						break
				if nodeWeights[1] < edgeWeights[0] and nodeWeights[1] != INF:
					count += 2
					break
			if nodeWeights[0] >= edgeWeights[0] or nodeWeights[0] == INF:
				edgeWeights = edgeWeights[1:]
				nodeWeights = nodeWeights[1:]
			else:
				nodeWeights = nodeWeights[1:]
				nodeWeights.append(INF)
				count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	b = []
	for i in range(n - 1):
		(x, y, z) = list(map(int, input().split()))
		b.append(z)
	a = list(map(int, input().split()))
	a.sort()
	b.sort()
	i = 0
	j = 0
	count = 0
	while True:
		if a[i] >= b[j]:
			i += 1
			j += 1
		else:
			i += 1
			count += 1
		if j == n - 1 or i == n:
			break
	print(count)


from collections import deque
test = int(input())
for _ in range(test):
	N = int(input())
	graph = [[] for i in range(N + 1)]
	es = []
	for i in range(N - 1):
		(u, v, val) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
		es.append(val)
	vs = [int(x) for x in input().split()]
	es.sort(reverse=True)
	vs.sort(reverse=True)
	coins = 0
	used = [False for i in range(N + 1)]
	q = deque([1])
	used[1] = True
	max_vals = [0 for i in range(N)]
	es.insert(0, es[0])
	e_ind = 0
	bfs = []
	while len(q) != 0:
		v = q[0]
		q.popleft()
		max_vals[v - 1] = es[e_ind]
		e_ind += 1
		bfs.append(v - 1)
		for u in graph[v]:
			if not used[u]:
				used[u] = True
				q.append(u)
	coins = 0
	v_ind = 0
	for i in bfs:
		if max_vals[i] > vs[v_ind]:
			coins += 1
		else:
			v_ind += 1
	print(coins)


t = int(input())
while t:
	n = int(input())
	b = [0] * (n - 1)
	for i in range(0, n - 1):
		(u, v, b[i]) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	b.sort()
	cnt = 0
	j = 0
	i = 0
	while i < n - 1 and j < n:
		if b[i] > a[j]:
			cnt += 1
		else:
			i += 1
		j += 1
	print(cnt)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	u = []
	v = []
	b = []
	l = []
	ans = 0
	for k in range(0, n - 1):
		(p, q, r) = map(int, input().split(' '))
		u.append(p)
		v.append(q)
		b.append(r)
	a = list(map(int, input().split(' ')))
	b.sort()
	a.sort()
	pa = n - 2
	p = n - 2
	j = b[n - 2]
	while pa >= 0:
		if a[p] < b[pa] and a[p + 1] < b[pa]:
			a.append(j)
			a.append(j)
			p = p + 2
			ans = ans + 2
		elif a[p] < b[pa]:
			a.append(j)
			p = p + 1
			ans = ans + 1
		p = p - 1
		pa = pa - 1
	print(ans)


for _ in range(int(input())):
	N = int(input())
	alist = [[] for i in range(N)]
	ewt = []
	for i in range(N - 1):
		(u, v, b) = [int(j) for j in input().split()]
		(u, v) = (u - 1, v - 1)
		ewt.append(b)
		alist[u].append(v)
		alist[v].append(u)
	ewt.sort(reverse=True)
	ewt_i = 0
	vwt = sorted([int(i) for i in input().split()], reverse=True)
	(vwt_start, vwt_end) = (0, len(vwt) - 1)
	coins = 0
	(start, __) = max(enumerate(alist), key=lambda x: len(x[1]))
	q = [start]
	unvisited = [True] * N
	nbs = alist
	unvisited[start] = False
	if vwt[vwt_start] < ewt[0]:
		coins += 1
		vwt_end -= 1
	else:
		vwt_start += 1
	while q:
		curr = q.pop(0)
		for v in nbs[curr]:
			if unvisited[v]:
				vewt = ewt[ewt_i]
				ewt_i += 1
				if vewt <= vwt[vwt_start]:
					vvwt = vwt[vwt_start]
					vwt_start += 1
				else:
					vvwt = vwt[vwt_end]
					vwt_end -= 1
				coins += vewt > vvwt
				q.append(v)
				unvisited[curr] = False
	print(coins)


t = int(input())
for _ in range(t):
	n = int(input())
	edges = []
	for i in range(n - 1):
		inp = list(map(int, input().strip().split(' ')))
		edges.append(inp[2])
	ver = list(map(int, input().strip().split(' ')))
	edges.sort()
	ver.sort()
	count = 0
	i = 0
	j = 0
	while i < n and j < n - 1:
		if edges[j] <= ver[i]:
			j += 1
			i += 1
		else:
			count += 1
			i += 1
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	E = []
	for j in range(N - 1):
		(a, b, c) = map(int, input().split())
		E.append(c)
	V = list(map(int, input().split()))
	V.sort()
	E.sort()
	E.append(0)
	ans = 0
	index = 0
	for j in V:
		if j >= E[index]:
			index += 1
		else:
			ans += 1
	print(ans)


T = int(input())
while T:
	T = T - 1
	N = int(input())
	weight = []
	for edge in range(N - 1):
		temp = input()
		a = temp.split(' ')
		weight.append(int(a[2]))
	vertice = []
	temp = input()
	b = temp.split(' ')
	for i in b:
		vertice.append(int(i))
	ans = 0
	weight.sort()
	vertice.sort()
	i = N - 2
	o = N - 2
	k = 0
	j = weight[N - 2] + 1
	while i >= 0:
		if vertice[o] < weight[i]:
			if vertice[o + 1] < weight[i]:
				vertice.append(j)
				vertice.append(j)
				o = o + 2
				ans = ans + 2
			else:
				vertice.append(j)
				o = o + 1
				ans = ans + 1
		o = o - 1
		i = i - 1
	print(ans)


t = int(input())
for i in range(t):
	N = int(input())
	edges = [0 for x in range(N - 1)]
	for p in range(N - 1):
		(_, _, edges[p]) = [int(x) for x in input().split()]
	vertices = [int(x) for x in input().split()]
	vertices.sort()
	edges.sort()
	max1 = 0
	count = 0
	for t in range(N - 1):
		if vertices[t] >= edges[max1]:
			max1 += 1
		else:
			count += 1
	if max1 < N - 1:
		if vertices[-1] < edges[max1]:
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	edge = []
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b, c) = [int(x) for x in input().split()]
		edge.append(c)
	vertex = [int(x) for x in input().split()]
	vertex = sorted(vertex, reverse=True)
	edge = sorted(edge, reverse=True)
	j = 1
	count = 0
	if vertex[0] < edge[0]:
		count += 1
		j = 0
	for i in range(n - 1):
		if vertex[j] < edge[i]:
			count += 1
			j -= 1
		j += 1
	print(count)


from collections import OrderedDict
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	dict = {}
	mx = int(0)
	for i in range(n - 1):
		(x, y, z) = map(int, input().split())
		if dict.get(z) == None:
			dict[z] = -1
		else:
			dict[z] -= 1
		mx = max(mx, z)
	l = list(map(int, input().split()))
	for i in range(n):
		if dict.get(l[i]) == None:
			dict[l[i]] = 1
		else:
			dict[l[i]] += 1
		mx = max(mx, l[i])
	pop_ele = dict.pop(mx)
	z = int(0)
	c = int(0)
	for i in sorted(dict.keys()):
		z += dict[i]
		c = max(c, z)
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr_real = []
	for _ in range(n - 1):
		(a, b, val) = map(int, input().split())
		arr_real.append(val)
	arr_given = list(map(int, input().split()))
	arr_real.sort(reverse=True)
	arr_real = [arr_real[0]] + arr_real
	arr_given.sort(reverse=True)
	(i, j) = (0, 0)
	while i != n:
		if arr_given[j] >= arr_real[i]:
			i += 1
			j += 1
		else:
			i += 1
	print(n - j)


t = int(input())
for p in range(t):
	edges = []
	n = int(input())
	for i in range(n - 1):
		(a, b, c) = input().split()
		c = int(c)
		edges.append(c)
	vertices = [int(x) for x in input().split()]
	vertices.sort()
	edges.sort()
	ans = 0
	count = 0
	while count < n:
		v1 = vertices.pop()
		e1 = edges.pop()
		if count == 0:
			count += 2
			if v1 < e1:
				ans += 2
				vertices.append(v1)
			else:
				v2 = vertices.pop()
				if v2 < e1:
					vertices.append(v2)
					ans += 1
		else:
			count += 1
			if v1 < e1:
				vertices.append(v1)
				ans += 1
	print(ans)


import sys
T = int(input())
for t in range(T):
	N = int(input())
	B = [0] * (N - 1)
	for i in range(N - 1):
		(ui, vi, b) = map(int, sys.stdin.readline().split(' '))
		B[i] = b
	A = list(map(int, sys.stdin.readline().split(' ')))
	A.sort(reverse=True)
	B.sort(reverse=True)
	count = 0
	i = 0
	j = 0
	if A[0] < B[0]:
		count += 1
	else:
		j = 1
	while i < N - 1:
		if B[i] > A[j]:
			count += 1
		else:
			j += 1
		i += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	edge = []
	for i in range(n - 1):
		(u, v, a) = map(int, input().split())
		edge.append(a)
	node = [int(i) for i in input().split()]
	node = sorted(node)
	edge = sorted(edge)
	ans = 0
	i = 0
	j = 0
	while i < n and j < n - 1:
		if edge[j] <= node[i]:
			j += 1
			i += 1
		else:
			ans += 1
			i += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	b = []
	for i in range(n - 1):
		b.append(int(input().split()[-1]))
	a = list(map(int, input().split()))
	a.sort()
	b.sort()
	b.append(b[-1])
	c = 0
	j = n - 1
	for i in range(n - 1, -1, -1):
		if a[j] < b[i]:
			c += 1
			j += 1
		j -= 1
	print(c)


T = int(input())
for v in range(T):
	n = int(input(''))
	g = []
	b = []
	for i in range(n + 1):
		g.append([])
	for i in range(n - 1):
		a = input('').split(' ')
		u = int(a[0])
		v = int(a[1])
		g[u].append(v)
		g[v].append(u)
		e = int(a[2])
		b.append(e)
	a = list(map(int, input('').split(' ')))
	b.sort()
	a.sort()
	i = 0
	j = 0
	pos = []
	c = 0
	while i < n and j < n - 1:
		if b[j] <= a[i]:
			c = c + 1
			j = j + 1
		else:
			pos.append(c)
			i = i + 1
	if j == n - 1:
		while i < n:
			pos.append(c)
			i = i + 1
	num = [0]
	for i in range(1, n + 1, 1):
		num.append(len(g[i]))
	mn = n
	cur = 0
	for i in range(1, n + 1, 1):
		if num[i] < mn:
			mn = num[i]
			cur = i
	t = 0
	I = 0
	ed = 0
	mn = 1
	while I < n - 1:
		p = pos[I]
		if p - ed >= mn:
			ed = ed + mn
		else:
			t = t + 1
		I = I + 1
	if ed == n - 1:
		print(0)
	elif ed < n - 1:
		if pos[-1] - ed >= mn:
			print(t)
		else:
			print(t + 1)


def solve(V, E):
	E.sort()
	V.sort()
	(edge_ptr, vertex_ptr, coins) = (0, 0, 0)
	while edge_ptr < len(E) and vertex_ptr < len(V):
		while vertex_ptr < len(V) and V[vertex_ptr] < E[edge_ptr]:
			vertex_ptr += 1
			coins += 1
		edge_ptr += 1
		vertex_ptr += 1
	return coins
for _ in range(int(input())):
	n = int(input())
	E = []
	for _ in range(n - 1):
		(u, v, b) = map(int, input().split())
		E.append(b)
	V = [int(x) for x in input().split()]
	print(solve(V, E))


t = int(input())
for i in range(t):
	n = int(input())
	le = []
	for j in range(1, n):
		s = input()
		ls = s.split(' ')
		le.append(int(ls[2]))
	le.sort()
	a = input()
	lv1 = a.split(' ')
	lv = []
	for v in range(n):
		lv.append(int(lv1[v]))
	lv.sort()
	l = []
	for k in range(2 * n - 1):
		if k % 2 == 0:
			l.append(lv[k // 2])
		else:
			l.append(le[k // 2])
	arr1 = []
	for m in range(0, 2 * n - 1, 2):
		if 0 < m < 2 * n - 2:
			if l[m] < l[m + 1] or l[m] < l[m - 1]:
				if len(arr1) > 0 and arr1[0] <= l[m]:
					arr1.pop(0)
				arr1.append(l[m + 1])
		elif m == 0 and l[m] < l[m + 1]:
			arr1.append(l[m + 1])
		elif m == 2 * n - 2 and l[m] < l[m - 1]:
			if len(arr1) > 0 and arr1[0] <= l[m]:
				arr1.pop(0)
			arr1.append(l[m - 1])
	print(len(arr1))


from collections import defaultdict
from heapq import *
import itertools, math

def parse_integer_list():
	return [int(x) for x in input().split()]

def handle_input(edges, vertices, N):
	coins = 0
	vertex_index = 0
	if vertices[0] < edges[0]:
		coins += 1
	else:
		vertex_index += 1
	for i in range(len(edges)):
		if vertices[vertex_index] < edges[i]:
			coins += 1
		else:
			vertex_index += 1
	return coins
T = int(input())
for i in range(T):
	N = int(input())
	edges = []
	for i in range(N - 1):
		(_, _, x) = parse_integer_list()
		edges.append(x)
	vertices = parse_integer_list()
	print(handle_input(sorted(edges, reverse=True), sorted(vertices, reverse=True), N))


for i in range(int(input())):
	n = int(input())
	edg = []
	for i in range(n - 1):
		c = int(input().split()[2])
		edg.append(c)
	ver = list(map(int, input().split()))
	edg.sort()
	ver.sort()
	a = 0
	b = 0
	while a < n and b < n - 1:
		if ver[a] >= edg[b]:
			b += 1
		a += 1
	if a == n - 1:
		b += 1
	print(n - b)


T = int(input())
for _ in range(T):
	N = int(input())
	C = []
	for i in range(N - 1):
		(u, v, b) = map(int, input().split())
		C.append(b)
	C.sort()
	C.append(C[len(C) - 1])
	B = list(map(int, input().split()))
	B.sort()
	coin = 0
	j = N - 1
	for i in range(N - 1, -1, -1):
		if B[j] < C[i]:
			coin = coin + 1
		else:
			j = j - 1
	print(coin)