in Chefland, there is a very famous street where $N$ types of street food (numbered $1$ through $N$) are offered. For each valid $i$, there are $S_i$ stores that offer food of the $i$-th type, the price of one piece of food of this type is $V_i$ (the same in each of these stores) and each day, $P_i$ people come to buy it; each of these people wants to buy one piece of food of the $i$-th type.
Chef is planning to open a new store at this street, where he would offer food of one of these $N$ types. Chef assumes that the people who want to buy the type of food he'd offer will split equally among all stores that offer it, and if this is impossible, i.e. the number of these people $p$ is not divisible by the number of these stores $s$, then only $\left\lfloor\frac{p}{s}\right\rfloor$ people will buy food from Chef.
Chef wants to maximise his daily profit. Help Chef choose which type of food to offer and find the maximum daily profit he can make.

-----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$ lines follow. For each $i$ ($1 \le i \le N$), the $i$-th of these lines contains three space-separated integers $S_i$, $P_i$ and $V_i$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum profit.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 100$
- $1 \le S_i, V_i, P_i \le 10,000$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
3
4 6 8
2 6 6
1 4 3
1
7 7 4

-----Example Output-----
12
0

-----Explanation-----
Example case 1: Chef should offer food of the second type. On each day, two people would buy from him, so his daily profit would be $12$.
Example case 2: Chef has no option other than to offer the only type of food, but he does not expect anyone to buy from him anyway, so his daily profit is $0$.

Difficulty: EASY
Tags: Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	m = 0
	for i in range(n):
		(s, p, v) = list(map(int, input().split(' ')))
		z = p // (s + 1)
		z *= v
		if z > m:
			m = z
	print(m)


t = int(input())
for T in range(t):
	n = int(input())
	count = 0
	maxi = 0
	for i in range(n):
		param = list(map(int, input().split()))
		(s, p, v) = (param[0], param[1], param[2])
		s = s + 1
		p = int(p / s)
		profit = v * p
		if maxi < profit:
			maxi = profit
			count = i + 1
	print(maxi)


for tc in range(int(input())):
	n = int(input())
	max_income = 0
	for i in range(n):
		(s, p, pr) = map(int, input().split())
		people_per_store = p // (s + 1)
		income = people_per_store * pr
		if income > max_income:
			max_income = income
	print(max_income)


for _ in range(int(input())):
	n = int(input())
	profit = 0
	for i in range(n):
		(x, y, z) = map(int, input().split())
		b = y // (x + 1) * z
		profit = max(profit, b)
	print(profit)


import math
t = int(input())
while t > 0:
	n = int(input())
	maxProfit = -1
	for i in range(n):
		val = str(input()).split(' ')
		profit = math.floor(int(val[1]) / (int(val[0]) + 1)) * int(val[2])
		if profit > maxProfit:
			maxProfit = profit
	print(maxProfit)
	t -= 1


for _ in range(int(input())):
	f = int(input())
	d = 0
	for _ in range(f):
		(m, p, v) = map(int, input().split())
		if p // (m + 1) * v > d:
			d = p // (m + 1) * v
	print(d)


ujju = int(input())
for jyo in range(ujju):
	pl = -1
	frp = int(input())
	for y in range(frp):
		(r, p, s) = map(int, input().split())
		rtd = p // (r + 1) * s
		if rtd > pl:
			pl = rtd
	print(pl)


a = int(input(''))
for i in range(a):
	x = int(input(''))
	l = 0
	for j in range(x):
		(S, P, V) = [int(x) for x in input('').split()]
		g = P // (S + 1) * V
		l = max(g, l)
	print(l)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(s, p, v) = [int(i) for i in input().split()]
		cp = p // (s + 1)
		l.append(cp * v)
	print(max(l))


t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	for j in range(n):
		(s, p, v) = map(int, input().split())
		l = p // (s + 1) * v
		if l > count:
			count = l
	print(count)


t = input()
for c in range(0, int(t)):
	b = int(input())
	c = 0
	for _ in range(b):
		(m, p, k) = map(int, input().split())
		if p // (m + 1) * k > c:
			c = p // (m + 1) * k
	print(c)


t = int(input())
for ni in range(t):
	n = int(input())
	pr = 0
	for nj in range(n):
		(s, p, v) = map(int, input().split())
		pr = max(pr, p // (s + 1) * v)
	print(pr)


for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(s, p, v) = map(int, input().split())
		s = s + 1
		l.append(p // s * v)
	print(max(l))


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		count = 0
		maxi = 0
		for i in range(n):
			param = list(map(int, input().split()))
			(s, p, v) = (param[0], param[1], param[2])
			s = s + 1
			p = int(p / s)
			profit = v * p
			if maxi < profit:
				maxi = profit
				count = i + 1
		print(maxi)
except:
	pass


import math as math
t = int(input())
for case in range(t):
	n = int(input())
	resource = []
	for line in range(n):
		info = input().split()
		resource.append(info)

	def calcmoney(index):
		moneylist.append(math.floor(int(resource[index][1]) / (int(resource[index][0]) + 1)) * int(resource[index][2]))
	moneylist = []
	for i in range(n):
		calcmoney(i)
	print(int(max(moneylist)))


for _ in range(int(input())):
	N = int(input())
	C = []
	for i in range(N):
		(S, P, V) = map(int, input().split())
		if S < P:
			C.append(P // (S + 1) * V)
	print(max(C) if C else 0)


for _ in range(int(input())):
	n = int(input())
	l = []
	import math
	for i in range(n):
		(a, b, c) = map(int, input().split())
		x = c * math.floor(b / (a + 1))
		l.append(x)
	print(max(l))


import math
T = int(input())
for _ in range(T):
	n = int(input())
	m = -1
	for i in range(n):
		(si, pi, vi) = map(int, input().split())
		si = si + 1
		dailyProfit = vi * math.floor(pi / si)
		if dailyProfit > m:
			m = dailyProfit
	print(m)


for _ in range(int(input())):
	N = int(input())
	profit = []
	for __ in range(N):
		(s, p, v) = map(int, input().split())
		profit.append(p // (s + 1) * v)
	print(max(profit))


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	rev = 0
	for _ in range(n):
		(si, pi, vi) = map(int, input().split())
		rev = max(pi // (si + 1) * vi, rev)
	print(rev)


for t in range(int(input())):
	n = int(input())
	k = []
	for i in range(n):
		(s, p, v) = map(int, input().split())
		k.append(p // (s + 1) * v)
	print(max(k))


t = int(input())
while t:
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	m = []
	for i in l:
		m.append(i[1] // (i[0] + 1) * i[2])
	res = max(m)
	print(res)
	t = t - 1


import math
t = int(input())
for t in range(t):
	n = int(input())
	maximumIs = []
	for i in range(n):
		(s, p, v) = map(int, input().split())
		k = v * math.floor(p / (s + 1))
		maximumIs.append(k)
	print(max(maximumIs))


for _ in range(int(input())):
	n = int(input())
	ans = 0
	for _ in range(n):
		(s, p, v) = map(int, input().split())
		ans = max(ans, v * (p // (s + 1)))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	profit = 0
	for i in range(n):
		(s, p, v) = map(int, input().split())
		if p % (s + 1) == 0:
			r = p // (s + 1) * v
			profit = max(profit, r)
		else:
			s = int(p // (s + 1)) * v
			profit = max(profit, s)
	print(profit)


t = int(input())
for i in range(t):
	s = int(input())
	r = 0
	for j in range(s):
		(x, y, z) = map(int, input().split())
		w = y // (x + 1) * z
		r = max(r, w)
	print(r)


for _ in range(int(input())):
	k = int(input())
	ans = -1
	for i in range(k):
		(s, p, v) = map(int, input().split())
		if p // (s + 1) * v > ans:
			ans = p // (s + 1) * v
	print(ans)


for jj in range(int(input())):
	n = int(input())
	profit = 0
	for j in range(n):
		(a, b, c) = map(int, input().split())
		profit = max(b // (a + 1) * c, profit)
	print(profit)


for _ in range(int(input())):
	n = int(input())
	(s, p, v) = list(map(int, input().split()))
	maxm = p // (s + 1) * v
	for i in range(n - 1):
		(s, p, v) = list(map(int, input().split()))
		prof = p // (s + 1) * v
		if prof > maxm:
			maxm = prof
	print(maxm)


import math
t = int(input())
for i in range(t):
	n = int(input())
	m = [0]
	for i in range(n):
		(s, p, v) = map(int, input().split())
		m.append(p // (s + 1) * v)
	print(max(m))


T = int(input())
for i in range(T):
	n = int(input())
	a = []
	for j in range(n):
		(s, p, v) = map(int, input().split())
		a.append(v * (p // (s + 1)))
	if n == 1:
		print('0')
	else:
		print(int(max(a)))


t = int(input())
for _ in range(t):
	n = int(input())
	maxi = 0
	for i in range(n):
		(s, p, v) = [int(x) for x in input().split()]
		temp = p // (s + 1)
		temp = temp * v
		if maxi < temp:
			maxi = temp
	print(maxi)


t = int(input())
while t != 0:
	n = int(input())
	pf = 0
	while n != 0:
		(s, p, v) = map(int, input().split())
		pr = v * (p // (s + 1))
		if pr > pf:
			pf = pr
		n -= 1
	print(pf)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append([int(i) for i in input().split()])
	p = []
	r = 0
	for i in arr:
		r = i[1] // (i[0] + 1) * i[2]
		p.append(r)
	p.sort()
	print(p[-1])


test_case = int(input(''))
for _ in range(test_case):
	k = int(input())
	count = 0
	for j in range(k):
		(s, p, v) = map(int, input().split())
		var = p // (s + 1) * v
		if var > count:
			count = var
	print(count)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	maxi = 0
	for i in range(n):
		(s, p, v) = map(int, input().split())
		h = math.floor(p / (s + 1))
		profit = h * v
		maxi = max(maxi, profit)
	print(maxi)


for _ in range(int(input())):
	l = []
	for _ in range(int(input())):
		(s, p, v) = map(int, input().split())
		l.append(p // (s + 1) * v)
	print(max(l))


import math
for t in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(n):
		[s, p, v] = [int(i) for i in input().split(' ')]
		ans = max(ans, v * math.floor(p / (s + 1)))
	print(ans)


t = int(input())
for i in range(t):
	N = int(input())
	if N == 1:
		print(0)
	else:
		k = 0
		for i in range(N):
			(s, p, v) = list(map(int, input().split()))
			h = p // (s + 1) * v
			if h > k:
				k = h
		print(int(k))


n = int(input())
for i in range(n):
	shops = int(input())
	max_p = 0
	for j in range(shops):
		inp = input()
		l = inp.split()
		for i in range(3):
			l[i] = int(l[i])
		profit = l[1] // (l[0] + 1) * l[2]
		if profit > max_p:
			max_p = profit
	print(max_p)


for k in range(int(input())):
	l = []
	n = int(input())
	for j in range(n):
		(s, p, v) = map(int, input().split())
		profit = p // (s + 1) * v
		l.append(profit)
	print(max(l))


n = int(input())
for i in range(n):
	N = int(input())
	L = 0
	for j in range(N):
		(x, y, z) = map(int, input().split())
		f = y // (x + 1) * z
		L = max(L, f)
	print(L)


try:
	from debug import debug, timer
except ImportError:
	pass
from sys import stdin
input = stdin.readline

def rii():
	return range(int(input().strip()))

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

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

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())

def getvals():
	while True:
		yield from input().split()

def profit(stores, people, price):
	return people // (stores + 1) * price

def do_codechef():
	for t in rii():
		n = ii()
		ans = 0
		for _ in range(n):
			(s, p, v) = mii()
			ans = max(ans, profit(s, p, v))
		print(ans)
do_codechef()
exit()


tests = int(input())
for i in range(tests):
	length = int(input())
	max_profit = 0
	for j in range(length):
		(s, p, v) = map(int, input().split())
		max_profit = max(max_profit, p // (s + 1) * v)
	print(max_profit)


for _ in range(int(input())):
	n = int(input())
	c = 0
	for _ in range(n):
		(s, p, v) = map(int, input().split())
		if p // (s + 1) * v > c:
			c = p // (s + 1) * v
	print(c)


t = int(input(''))
for i in range(t):
	k = int(input())
	count = 0
	for j in range(k):
		(s, p, v) = map(int, input().split())
		var = p // (s + 1) * v
		if var > count:
			count = var
	print(count)


for _ in range(int(input())):
	m = 0
	for __ in range(int(input())):
		(a, b, c) = map(int, input().split())
		m = max(m, b // (a + 1) * c)
	print(m)


for _ in range(int(input())):
	N = int(input())
	S = []
	V = []
	P = []
	for i in range(N):
		(x, y, z) = map(int, input().split())
		S.append(x)
		P.append(y)
		V.append(z)
	B = []
	i = 0
	while i < N:
		B.append(P[i] // (S[i] + 1) * V[i])
		i += 1
	print(max(B))


for i in range(int(input())):
	n = int(input())
	x = 0
	for j in range(n):
		(a, b, c) = map(int, input().split())
		d = b // (a + 1) * c
		x = max(x, d)
	print(x)


t = int(input())
for tc in range(t):
	n = int(input())
	a = []
	for j in range(n):
		(s, p, v) = map(int, input().split())
		a.append(p // (s + 1) * v)
	print(max(a))


for _ in range(int(input())):
	n = int(input())
	m = -1
	for i in range(n):
		(a, b, c) = map(int, input().split())
		a += 1
		m = max(m, b // a * c)
	print(m)


T = int(input())
for i in range(T):
	n = int(input())
	max_prof = 0
	for j in range(n):
		(s, v, p) = map(int, input().split())
		prof = v // (s + 1) * p
		if prof > max_prof:
			max_prof = prof
	print(int(max_prof))


t = int(input())
while t > 0:
	t -= 1
	v1 = []
	v1.clear()
	n = int(input())
	a = 0
	b = 0
	while n > 0:
		n -= 1
		(s, p, v) = map(int, input().split())
		if p % (s + 1) == 0:
			a = p // (s + 1)
			a = a * v
			v1.append(a)
		else:
			b = p // (s + 1)
			b = b * v
			v1.append(b)
	print(max(v1))


T = int(input())
for _ in range(T):
	n = int(input())
	p1 = 0
	for i in range(n):
		(a, b, c) = map(int, input().split())
		p2 = b // (a + 1) * c
		if p2 > p1:
			p1 = p2
	print(p1)


for _ in range(int(input())):
	m = int(input())
	n = 0
	for _ in range(m):
		(x, y, z) = map(int, input().split())
		n = max(n, y // (x + 1) * z)
	print(n)


for _ in range(int(input())):
	n = int(input())
	best = 0
	for i in range(n):
		(s, p, v) = map(int, input().split())
		best = max(best, p // (s + 1) * v)
	print(best)


for _ in range(int(input())):
	n = int(input())
	l = []
	for w in range(n):
		(s, p, v) = map(int, input().split())
		r = int(p / (s + 1)) * v
		l.append(r)
	print(max(l))


for _ in range(int(input())):
	n = int(input())
	maxi = 0
	for i in range(n):
		(s, p, v) = map(int, input().split())
		a = int(p / (s + 1))
		b = a * v
		maxi = max(maxi, b)
	print(maxi)


from math import floor
for _ in range(int(input())):
	l = []
	for _ in range(int(input())):
		(s, p, v) = map(int, input().split())
		l.append(p // (s + 1) * v)
	print(max(l))


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for i in range(n):
		(s, p, v) = map(int, input().split())
		b = math.floor(p / (s + 1))
		c = b * v
		a.append(c)
	print(max(a))


from sys import stdin
rl = stdin.readline

def read(func=int):
	return map(func, rl().strip().split())
for _ in range(int(rl())):
	n = int(rl())
	profit = []
	for _ in range(n):
		(s, p, v) = read()
		if s < p:
			profit.append(p // (s + 1) * v)
	print(max(profit)) if len(profit) > 1 else print(0)


for i in range(int(input())):
	n = int(input())
	c = []
	for j in range(n):
		(S, P, V) = map(int, input().split())
		if S < P:
			c.append(P // (S + 1) * V)
	if c:
		print(max(c))
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	mx = 0
	for i in range(n):
		(s, v, p) = map(int, input().split())
		x = v // (s + 1)
		m = x * p
		mx = max(mx, m)
	print(mx)