Chef Po has given an online advertisement to provide Event organizing services. Chef got a huge response for his advertisement. He got various orders to conduct the events from different organizations. In turn, Chef will receive a compensation depend upon the type of event and the total numbers of persons in the event. Chef has received N orders for conducting events in this weekend in all. As weekend consists of two days all events will take place during the period of 48 hours. For the i-th order the corresponding event will start at S_{i} hours, ends at E_{i} hours and Chef will receive a compensation C_{i} for this event. For example, if S_{i} = 17 and E_{i} = 22 then duration of event is 22 – 17 = 5 hours and its time period is 17:00 – 22:00 of Saturday. Hours of Sunday are numbered by numbers from 24 to 48. So, for example, 10:00 of Sunday will be represented as 10 + 24 = 34. Because Chef is a newbie, the organizations had put a condition that Chef will receive a compensation for the event if and only if he is available for the entire duration of the event. It means that he can not choose overlapping events. Note, however, that if some event starts just in the moment another event has finished the Chef can safely conduct them both.

In general Chef will obey the orders on first come first serve basis. But on weekends Chef will select the orders in such a way that the total compensation for all the events he will conduct will be the maximal. Now your task is to help Chef and find this maximal total compensation.

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

The first line of the input contains an integer T, the number of test cases. T test cases follow. The first line of each test case contains an integer N, the number of received orders for conducting events. Each of the next N lines contains three space separated integers S_{i}, E_{i}, C_{i}, the parameters of the i-th event described in the problem statement.

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

1 ≤ T ≤ 10
1 ≤ N ≤ 2000
0 ≤ S_{i} < E_{i} ≤ 48
0 ≤ C_{i} ≤ 10^{6}

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

Output for each test case should contain a single integer in a separate line, the maximal compensation Chef Po can get.

----- Sample Input 1 ------ 
2
4
1 2 100
2 3 200
3 4 1600
1 3 2100
3
1 10 2000
2 5 100
6 9 400
----- Sample Output 1 ------ 
3700
2000
----- explanation 1 ------ 

Case 1. The best choice here is to conduct 3rd and 4th events. The total compensation is equal to 1600 + 2100 = 3700. These events do not overlap since 3rd event starts just after the finish of the 4th one. Alternatively we can conduct first three events that also do not overlap. But in this case compensation will be only 100 + 200 + 1600 = 1900.

Case 2. Note that first event overlaps with both second and third events, while the last two events do not overlap. Hence there are two reasonable choices available for Chef. One is to take just the first order with total compensation 2000 and the second one is to take the last two orders with total compensation 100 + 400 = 500. Clearly the first choice is better. Hence the answer is 2000.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Implementation


Solutions:
def FW():
	for k in range(49):
		for i in range(49):
			for j in range(49):
				if i <= k and k <= j:
					dist[i][j] = max(dist[i][k] + dist[k][j], dist[i][j])
T = int(input())
for _ in range(T):
	dist = [[0] * 49 for i in range(49)]
	n = int(input())
	for i in range(n):
		(u, v, w) = map(int, input().split())
		dist[u][v] = max(dist[u][v], w)
	FW()
	print(dist[0][48])


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


def compare(x):
	return x[1]
for _ in range(int(input())):
	n = int(input())
	inf = list()
	[inf.append(list(map(int, input().split(' ')))) for i in range(n)]
	inf.sort(key=compare)
	d = [0] * 50
	for (source, dest, cost) in inf:
		d[dest] = max(max(d[:source + 1]) + cost, d[dest])
	print(max(d))


def main():
	test_case = int(input())
	for t in range(test_case):
		n = int(input())
		d = [[] for i in range(49)]
		for i in range(49):
			for j in range(49):
				d[i].append(0 if i <= j else -10 ** 9)
		for i in range(n):
			(s, e, c) = map(int, input().split())
			d[s][e] = max(d[s][e], c)
		for k in range(49):
			for i in range(49):
				for j in range(i, 49):
					d[i][j] = max(d[i][j], d[i][k] + d[k][j])
		print(d[0][48])
main()


import numpy as np
TH = 49

def get_best(comp_array):
	best_comp_till_i = np.zeros(TH)
	for fh in range(TH):
		comp_end_fh = comp_array[fh]
		max_comp = max(comp_end_fh + best_comp_till_i)
		best_comp_till_i[fh] = max_comp
	return int(best_comp_till_i[-1])
T = int(input())
for t in range(T):
	n = int(input())
	comp_array = np.zeros((TH, TH))
	for _ in range(n):
		(sh, fh, comp) = map(int, input().split())
		comp_array[fh, sh] = max(comp_array[fh, sh], comp)
	print(get_best(comp_array))


a = int(input())
for i in range(a):
	b = []
	d = [0] * 50
	a1 = int(input())
	for j in range(a1):
		c = [int(x) for x in input().split()]
		b.append(c)
	b.sort()
	for i in range(len(b)):
		(x, y, k) = b[i]
		m = d[x] + k
		for j in range(y, len(d)):
			d[j] = max(d[j], m)
	print(d[-1])


T = int(input())
for t in range(T):
	N = int(input())
	C = [[0 for _ in range(49)] for _ in range(49)]
	for i in range(N):
		(s, e, c) = map(int, input().split())
		C[s][e] = max(C[s][e], c)
	maxC = [0 for _ in range(49)]
	for E in range(49):
		for S in range(E):
			maxC[E] = max(maxC[E], maxC[S] + C[S][E])
	print(maxC[48])


T = int(input())
for T in range(T):
	n = int(input())
	G = [[] for i in range(50)]
	f = [0] * 50
	for i in range(n):
		(L, R, w) = map(int, input().split(' '))
		G[R] += [[L, w]]
	for i in range(49):
		f[i] = max([f[j] + w for (j, w) in G[i]] + [0])
		if i:
			f[i] = max(f[i], f[i - 1])
	print(f[48])


import queue
MAX = 49
INF = int(1000000000.0)

def FloydWarshall(graph, dist):
	for i in range(MAX):
		for j in range(MAX):
			dist[i][j] = graph[i][j]
	for k in range(MAX):
		for i in range(MAX):
			for j in range(MAX):
				if i <= k and k <= j and (dist[i][j] < dist[i][k] + dist[k][j]):
					dist[i][j] = dist[i][k] + dist[k][j]
test = int(input())
while test > 0:
	test -= 1
	m = int(input())
	graph = [[0 for i in range(MAX)] for j in range(MAX)]
	dist = [[None for i in range(MAX)] for j in range(MAX)]
	for i in range(m):
		(u, v, w) = map(int, input().split())
		graph[u][v] = max(w, graph[u][v])
	FloydWarshall(graph, dist)
	print(dist[0][48])


t = int(input())
for _ in range(t):
	n = int(input())
	dp = [[0 for i in range(49)] for j in range(49)]
	for i in range(n):
		(s, e, c) = map(int, input().split())
		dp[s][e] = max(dp[s][e], c)
	c = [0] * 49
	for i in range(49):
		c[i] = 0
		for j in range(i):
			c[i] = max(c[i], c[j] + dp[j][i])
	c.sort()
	print(c[-1])


INF = float('inf')

def floyd_warshall():
	best_comp_so_far = [0] * (last_time + 1)
	for j in range(1, last_time + 1):
		for i in range(j):
			temp_comp = best_comp_so_far[i] + dist[i][j]
			if temp_comp > best_comp_so_far[j]:
				best_comp_so_far[j] = temp_comp
	return best_comp_so_far[last_time]
num_tests = int(input())
for t in range(num_tests):
	num_orders = int(input())
	dist = [[0 for i in range(49)] for j in range(49)]
	last_time = 0
	for o in range(num_orders):
		(s, e, c) = map(int, input().split())
		dist[s][e] = max(dist[s][e], c)
		if e > last_time:
			last_time = e
	result = floyd_warshall()
	print(result)


INF = float('inf')

def FloydWarshall(graph, M):
	dist = [[0] * M for _ in range(M)]
	for i in range(M):
		for j in range(M):
			dist[i][j] = graph[i][j]
	for _ in range(5):
		for k in range(M):
			for i in range(M):
				for j in range(M):
					if i <= k <= j and dist[i][j] < dist[i][k] + dist[k][j]:
						dist[i][j] = dist[i][k] + dist[k][j]
	max_compensation = 0
	for i in range(M):
		for j in range(M):
			if max_compensation < dist[i][j]:
				max_compensation = dist[i][j]
	return max_compensation
T = int(input())
for _ in range(T):
	N = int(input())
	max_M = 49
	graph = [[0] * max_M for _ in range(max_M)]
	for _ in range(N):
		(S, E, C) = map(int, input().split())
		if C > graph[S][E]:
			graph[S][E] = C
	result = FloydWarshall(graph, max_M)
	print(result)


import sys
for z in range(int(sys.stdin.readline())):
	arr = []
	another = [[] for m in range(49)]
	for f in range(int(sys.stdin.readline())):
		temp = list(map(int, sys.stdin.readline().split()))
		another[temp[1]].append(temp)
		arr.append(temp)
	best = [0 for m in range(49)]
	arr.sort()
	for i in range(1, 49):
		temp = another[i]
		if temp == []:
			best[i] = best[i - 1]
		else:
			maxi = best[i - 1]
			for j in range(len(temp)):
				maxi = max(maxi, best[temp[j][0]] + temp[j][2])
			best[i] = maxi
	print(best[-1])


for _ in range(int(input())):
	N = int(input())
	dp = [0] * 50
	entries = []
	for i in range(N):
		(S, E, C) = list(map(int, input().split()))
		entries.append((S, E, C))
	entries.sort()
	for i in range(len(entries)):
		(S, E, C) = entries[i]
		m = dp[S] + C
		for j in range(E, len(dp)):
			dp[j] = max(dp[j], m)
	print(dp[-1])


def f(x):
	return x[1]
t = int(input())
for _ in range(t):
	n = int(input())
	l = [0] * 50
	p = []
	for q in range(n):
		(a, b, c) = map(int, input().split(' '))
		p.append([a, b, c])
	p.sort(key=lambda x: x[1])
	for i in range(n):
		(a, b, c) = (p[i][0], p[i][1], p[i][2])
		if l[a] + c > l[b]:
			temp = l[b]
			l[b] = l[a] + c
			for k in range(b + 1, 49):
				l[k] = l[k] + l[b] - temp
	print(l[48])


import math

def floyd_marshall(graph, dist, n):
	for i in range(n):
		for j in range(n):
			if i <= j:
				dist[i][j] = graph[i][j]
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if i <= k <= j:
					dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])
	return (graph, dist)

def maxcomp(graph, dist, n):
	(graph, dist) = floyd_marshall(graph, dist, n)
	print(dist[0][48])
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	graph = [[0 for _ in range(49)] for _ in range(49)]
	dist = [[0 for _ in range(49)] for _ in range(49)]
	for _ in range(n):
		(s, e, c) = list(map(int, input().strip().split(' ')))
		if c > graph[s][e]:
			graph[s][e] = c
	maxcomp(graph, dist, 49)


INF = int(1000000000.0)
MAX = 50

def FloydWarshall(dist):
	for k in range(MAX):
		for i in range(MAX):
			for j in range(MAX):
				if i <= k <= j:
					if dist[i][j] < dist[i][k] + dist[k][j]:
						dist[i][j] = dist[i][k] + dist[k][j]
T = int(input())
for t in range(T):
	dist = [[0 for i in range(MAX)] for j in range(MAX)]
	n = int(input())
	for i in range(n):
		(s, e, c) = map(int, input().split())
		if c > dist[s][e]:
			dist[s][e] = c
	FloydWarshall(dist)
	max = -1
	for i in range(MAX):
		for j in range(MAX):
			if dist[i][j] > max:
				max = dist[i][j]
	print(max)


for _ in range(int(input())):
	n = int(input())
	a = [[0 for i in range(49)] for j in range(48)]
	max_list = [0 for i in range(49)]
	for i in range(n):
		(s, e, c) = map(int, input().split())
		a[s][e] = max(c, a[s][e])
	for end in range(1, 49):
		for start in range(end):
			max_list[end] = max(max_list[end], max_list[start] + a[start][end])
	print(max(max_list))


MAX = 48

def FloydWarshall():
	for k in range(MAX + 1):
		for i in range(MAX + 1):
			for j in range(MAX + 1):
				if i <= k <= j:
					dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])
T = int(input())
for _ in range(T):
	N = int(input())
	dist = [[0] * (MAX + 1) for i in range(MAX + 1)]
	for i in range(N):
		(S, E, C) = map(int, input().split())
		if C > dist[S][E]:
			dist[S][E] = C
	FloydWarshall()
	print(dist[0][MAX])


def solve():
	max_lst = [0] * 49
	for e in range(49):
		for s in range(e):
			max_lst[e] = max(max_lst[e], lst[s][e] + max_lst[s])
	print(max_lst[48])
t = int(input())
for _ in range(t):
	n = int(input())
	lst = [[0 for j in range(49)] for i in range(49)]
	for i in range(n):
		(s, e, c) = list(map(int, input().split()))
		lst[s][e] = max(lst[s][e], c)
	solve()


for _ in range(int(input())):
	n1 = int(input())
	a = [[0 for i in range(49)] for j in range(49)]
	maxi = [0] * 49
	for l in range(1, n1 + 1):
		(s, e, m) = map(int, input().split())
		a[s][e] = max(a[s][e], m)
	for end in range(49):
		for start in range(end):
			maxi[end] = max(maxi[end], a[start][end] + maxi[start])
	print(maxi[48])


t = int(input())
for _ in range(t):
	n = int(input())
	x = [0] * 49
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort()
	for i in l:
		c = i[0]
		for j in range(c, -1, -1):
			x[i[1]] = max(x[i[1]], x[j] + i[2])
	print(max(x))


def soln(n, arr):
	dp = [[0] * 49 for _ in range(49)]
	for (beg, end, pay) in arr:
		dp[beg][end] = max(dp[beg][end], pay)
	res = [0] * 49
	for end in range(49):
		for beg in range(end):
			res[end] = max(res[end], res[beg] + dp[beg][end])
	return res[-1]
for _ in range(int(input())):
	n = int(input())
	arr = [list(map(int, input().split())) for i in range(n)]
	print(soln(n, arr))


MAX = 49
INF = int(2 ** 64)

def solver():
	T = int(input())
	for _ in range(T):
		solve_one()

def solve_one():
	m = int(input())
	dist = [[0 for i in range(MAX)] for j in range(MAX)]
	for i in range(m):
		(start, end, pay) = map(int, input().split())
		dist[start][end] = max(pay, dist[start][end])
	for k in range(MAX):
		for i in range(MAX):
			for j in range(MAX):
				if i <= k <= j:
					dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])
	ans = 0
	for i in range(len(dist)):
		arr = dist[i]
		for e in arr:
			ans = max(ans, e)
	print(ans)
solver()


INF = 10 ** 9
MAX = 49

def FloydWarshall(dist):
	n = len(dist)
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if i <= k <= j and dist[i][j] < dist[i][k] + dist[k][j]:
					dist[i][j] = dist[i][k] + dist[k][j]
tc = int(input())
for tc in range(1, tc + 1):
	dist = [[0] * MAX for i in range(MAX)]
	n = int(input())
	for i in range(n):
		(s, e, c) = map(int, input().split())
		if c > dist[s][e]:
			dist[s][e] = c
	FloydWarshall(dist)
	print(dist[0][48])


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import numpy as np
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		n = nl()
		max_list = [0 for _ in range(49)]
		a = [[0 for _ in range(49)] for _ in range(48)]
		for i in range(n):
			(s, e, w) = sm()
			if w > a[s][e]:
				a[s][e] = w
		for end in range(1, 49):
			for start in range(end):
				if max_list[start] + a[start][end] > max_list[end]:
					max_list[end] = max_list[start] + a[start][end]
		print(max(max_list))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	eventos = []
	for i in range(n):
		(s, e, c) = map(int, input().split())
		eventos.append((s, e, c))
	eventos.sort(key=lambda x: x[1])
	max_compesacion = [0] * 48
	for evento in eventos:
		(tiempo_inicio, tiempo_final, compensacion) = evento
		max_compesacion_tiempoinicial = 0
		for i in range(tiempo_inicio):
			max_compesacion_tiempoinicial = max(max_compesacion[:tiempo_inicio])
		max_compesacion[tiempo_final - 1] = max(max_compesacion[tiempo_final - 1], max_compesacion_tiempoinicial + compensacion)
	print(max(max_compesacion))


import sys
import math
from time import time
from itertools import permutations, combinations
import collections
import functools
from fractions import gcd, Fraction
import string
import operator
import bisect

class timed(object):

	def __init__(self, func):
		self.func = func

	def __call__(self, *args):
		t1 = time()
		ret = self.func(*args)
		dif_time = time() - t1
		print('%s: returned %s in %f seconds' % (self.func.__name__, ret, dif_time))
		return ret

def comp(f1, f2, *args):
	t1 = time()
	r1 = f1(*args) if f1 is not None else None
	t2 = time()
	r2 = f2(*args) if f2 is not None else None
	t3 = time()
	res = '%5s: %s in %f\n%5s: %s in %f' % (f1.__name__ if f1 is not None else None, r1, t2 - t1, f2.__name__ if f2 is not None else None, r2, t3 - t2)
	if r1 != r2:
		dr = '!! DIFFERENT RESULTS !!'
		res = dr + '\n' + res + '\n' + dr
	print(res)

def bellman_ford(start, end, nb_nodes, get_neighbors, max_path_nodes=None):
	MAX_INT = 9999999
	if max_path_nodes is None:
		max_path_nodes = nb_nodes - 1
	weights = [MAX_INT] * nb_nodes
	weights[start] = 0
	nb = [(u, v, w) for u in range(nb_nodes) for (v, w) in get_neighbors(u)]
	for i in range(max_path_nodes):
		changes = False
		for (u, v, w) in nb:
			if weights[u] + w < weights[v]:
				changes = True
				weights[v] = weights[u] + w
		if not changes:
			break
	return weights

def alg(events):
	events = sorted(((s, e, -c) for (s, e, c) in events))
	length = len(events)
	nb_nodes = length + 2

	def get_neighbors(i):
		if i == 0:
			for (ievent, event) in enumerate(events):
				yield (ievent + 1, event[2])
		elif i == length + 1:
			pass
		else:
			prev_event_end = events[i - 1][1]
			for (inbevent, event) in enumerate(events):
				if event[0] >= prev_event_end:
					yield (inbevent + 1, event[2])
			yield (length + 1, 0)
	return -min(bellman_ford(0, nb_nodes - 1, nb_nodes, get_neighbors))

class memoized(object):

	def __init__(self, func):
		self.func = func
		self.cache = {}

	def __call__(self, *args):
		if not isinstance(args, collections.Hashable):
			return self.func(*args)
		if args in self.cache:
			return self.cache[args]
		else:
			value = self.func(*args)
			self.cache[args] = value
			return value

	def __repr__(self):
		return self.func.__doc__

	def __get__(self, obj, objtype):
		return functools.partial(self.__call__, obj)

def alg2(events):
	C = [list([0] * 49) for _ in range(49)]
	for (s, e, p) in events:
		C[s][e] = max(C[s][e], p)

	@memoized
	def maxC(e_):
		if e_ == 0:
			return 0
		res = 0
		for start in range(0, e_):
			v = maxC(start) + C[start][e_]
			res = max(res, v)
		return res
	return maxC(48)

def main():
	data = sys.stdin
	nb = int(data.readline())
	for icase in range(nb):
		nb_events = int(data.readline().strip())
		events = []
		for e in range(nb_events):
			events.append(list(map(int, data.readline().split())))
		res = alg2(events)
		print(res)
main()


t = int(input())
for x in range(t):
	n = int(input())
	events = []
	for y in range(n):
		l = [int(a) for a in input().split()]
		events.append(l)
	events.sort()
	h = [[0 for i in range(49)] for j in range(n)]
	for i in range(n):
		for j in range(49):
			if i == 0:
				if events[i][1] <= j:
					h[i][j] = events[i][2]
			elif events[i][1] <= j:
				h[i][j] = max(events[i][2] + h[i - 1][events[i][0]], h[i - 1][j])
			else:
				h[i][j] = h[i - 1][j]
	print(h[n - 1][48])


for _ in range(int(input())):
	N = int(input())
	V = [[0 for i in range(49)] for j in range(49)]
	max_list = [0] * 49
	for k in range(1, N + 1):
		(s, e, c) = map(int, input().split())
		V[s][e] = max(V[s][e], c)
	for end in range(49):
		for start in range(end):
			max_list[end] = max(max_list[end], V[start][end] + max_list[start])
	print(max_list[48])


INF = 10 ** 9

def floydWarshall(graph):
	n = len(graph)
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if graph[i][k] + graph[k][j] > graph[i][j]:
					graph[i][j] = graph[i][k] + graph[k][j]

def solve():
	m = int(input())
	n = 49
	graph = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(n):
			if i > j:
				graph[i][j] = -INF
	for i in range(m):
		(u, v, w) = map(int, input().split())
		if graph[u][v] < w:
			graph[u][v] = w
	floydWarshall(graph)
	maxCompensation = 0
	for i in range(n):
		for j in range(n):
			maxCompensation = max(maxCompensation, graph[i][j])
	print(maxCompensation)
t = int(input())
for _ in range(t):
	solve()


INF = float('inf')

def floyd_warshall():
	for k in range(49):
		for i in range(49):
			for j in range(49):
				if dist[i][k] + dist[k][j] > dist[i][j]:
					dist[i][j] = dist[i][k] + dist[k][j]
num_tests = int(input())
for t in range(num_tests):
	num_orders = int(input())
	dist = [[0 if i <= j else -INF for j in range(49)] for i in range(49)]
	last_time = 0
	for o in range(num_orders):
		(s, e, c) = map(int, input().split())
		dist[s][e] = max(c, dist[s][e])
	floyd_warshall()
	print(dist[0][48])


for _ in range(int(input())):
	N = int(input())
	R = [0 for x in range(49)]
	A = []
	for k in range(N):
		st = input().split()
		S = int(st[0])
		E = int(st[1])
		C = int(st[2])
		A.append([S, E, C])
	A.sort()
	for x in A:
		S = x[0]
		E = x[1]
		C = x[2]
		nc = R[S] + C
		if nc > R[E]:
			for k in range(E, 49):
				if nc > R[k]:
					R[k] = nc
	print(R[48])


INF = 10 ** 9
n = 49

def floyd():
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if i <= k <= j:
					dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])
T = int(input())
for _ in range(T):
	dist = [[0] * n for _ in range(n)]
	m = int(input())
	for _ in range(m):
		(u, v, w) = map(int, input().split())
		if dist[u][v] < w:
			dist[u][v] = w
	floyd()
	print(dist[0][48])


import sys
INF = int(1000000000.0)

def floyd_warshall(M, graph):
	dist = [[0] * M for i in range(M)]
	for i in range(M):
		for j in range(M):
			dist[i][j] = graph[i][j]
	for x in range(5):
		for k in range(M):
			for i in range(M):
				for j in range(M):
					if i <= k <= j and dist[i][j] < dist[i][k] + dist[k][j]:
						dist[i][j] = dist[i][k] + dist[k][j]
	max_comp = 0
	for i in range(M):
		for j in range(M):
			if max_comp < dist[i][j]:
				max_comp = dist[i][j]
	return max_comp

def solution():
	T = int(input().strip())
	M = 49
	for i in range(T):
		graph = [[0] * M for x in range(M)]
		N = int(input().strip())
		e_max = 0
		for j in range(N):
			(si, ei, ci) = map(int, input().strip().split())
			if ei > e_max:
				e_max = ei
			if ci > graph[si][ei]:
				graph[si][ei] = ci
		mmax = [0 for x in range(M)]
		for x in range(1, e_max + 1):
			m = 0
			for xx in range(x):
				if m < graph[xx][x] + mmax[xx]:
					m = graph[xx][x] + mmax[xx]
				mmax[x] = m
		print(mmax[e_max])
solution()


H = 49
t = int(input())
for _ in range(t):
	dp = [[0 for _ in range(H)] for _ in range(H)]
	n = int(input())
	for _ in range(n):
		(s, e, c) = (int(x) for x in input().split())
		dp[s][e] = max(dp[s][e], c)
	max_c = [0 for _ in range(H)]
	for e in range(H):
		for s in range(H - 1):
			max_c[e] = max(max_c[e], max_c[s] + dp[s][e])
	print(max_c[48])


for _ in range(int(input())):
	N = int(input())
	events = []
	for i in range(N):
		(s, e, c) = map(int, input().split())
		events.append([s, e, c])
	events.sort()
	plan = [0] * 49
	for i in events:
		check_before = i[0]
		for j in range(check_before, -1, -1):
			plan[i[1]] = max(plan[i[1]], plan[j] + i[2])
	print(max(plan))


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import numpy as np
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def largest_overlapping_indexes(intervals, n):
	p = []
	start_times = [intervals[i][0][0] for i in range(n)]
	finish_times = [intervals[i][0][1] for i in range(n)]
	for i in start_times:
		index = bisect.bisect(finish_times, i)
		p.append(index - 1)
	return p

def compute_opt(index, p, OPT, intervals):
	if index == -1:
		return 0
	elif 0 <= index < len(OPT):
		return OPT[index]
	else:
		return max(intervals[index][1] + compute_opt(p[index], p, OPT, intervals), compute_opt(index - 1, p, OPT, intervals))

def main():
	for _ in tr():
		n = nl()
		intervals = []
		OPT = []
		p = []
		for i in range(n):
			(s, e, w) = sm()
			intervals.append([(s, e), w])
		intervals.sort(key=lambda x: x[0][1])
		p = largest_overlapping_indexes(intervals, n)
		max_weight = 0
		for i in range(n):
			max_weight = compute_opt(i, p, OPT, intervals)
			OPT.append(max_weight)
		print(max(OPT))
main()


for j in range(int(input())):
	(l, out) = ([], 0)
	for i in range(int(input())):
		(s, e, cost) = map(int, input().split())
		out = max(out, e)
		l.append([s, e, cost])
	l.sort()
	p = [0] * (out + 1)
	for i in range(len(l)):
		cost = p[l[i][0]] + l[i][2]
		if cost > p[l[i][1]]:
			for i in range(l[i][1], len(p)):
				if p[i] < cost:
					p[i] = cost
	print(p[len(p) - 1])


import sys

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

def floyWarshall():
	for k in range(50):
		for i in range(50):
			for j in range(50):
				if i <= k <= j and dist[i][j] < dist[i][k] + dist[k][j]:
					dist[i][j] = dist[i][k] + dist[k][j]
n = 0
dist = []
tc = int(input())
while tc > 0:
	tc -= 1
	n = int(input())
	dist = [[0 for j in range(50)] for i in range(50)]
	for i in range(n):
		(s, e, c) = map(int, input().split())
		if c > dist[s][e]:
			dist[s][e] = c
	floyWarshall()
	print(dist[0][48])


def FloydWarshall(distance):
	for k in range(49):
		for i in range(49):
			for j in range(49):
				if i <= k and k <= j and (distance[i][j] < distance[i][k] + distance[k][j]):
					distance[i][j] = distance[i][k] + distance[k][j]
number_of_test_cases = int(input())
for i in range(number_of_test_cases):
	number_of_orders = int(input())
	distance = [[0] * 49 for _ in range(49)]
	for j in range(number_of_orders):
		(start, end, cost) = map(int, input().strip().split(' '))
		distance[start][end] = max(distance[start][end], cost)
	FloydWarshall(distance)
	print(distance[0][48])


INF = 1000000000.0

def FloydWarshall(graph):
	for k in range(49):
		for i in range(49):
			for j in range(49):
				if i <= k <= j and graph[i][j] < graph[i][k] + graph[k][j]:
					graph[i][j] = graph[i][k] + graph[k][j]
t = int(input())
for tc in range(t):
	n = int(input())
	graph = [[0 for i in range(49)] for j in range(49)]
	for i in range(n):
		(s, e, c) = map(int, input().split())
		if c > graph[s][e]:
			graph[s][e] = c
	FloydWarshall(graph)
	print(graph[0][48])


T = int(input())
for _ in range(T):
	N = int(input())
	c = [[0 for _ in range(49)] for _ in range(49)]
	for i in range(N):
		(u, v, w) = map(int, input().split())
		c[u][v] = max(c[u][v], w)
	dp = [0 for _ in range(49)]
	for i in range(49):
		for j in range(i):
			dp[i] = max(dp[i], dp[j] + c[j][i])
	print(dp[48])


t = int(input())
for i in range(t):
	n = int(input())
	r = [0] * 49
	l = []
	for j in range(n):
		(s1, s2, s3) = map(int, input().split())
		l.append([s1, s2, s3])
	l.sort()
	for k in l:
		sa = k[0]
		sb = k[1]
		sc = k[2]
		a = r[sa] + sc
		if a > r[sb]:
			for x in range(sb, 49):
				if a > r[x]:
					r[x] = a
	print(r[48])