The evil forest is guarded by vicious mandragoras. Garnet and her pet must make a journey through.  She starts with $1$ health point ($\boldsymbol{\mathrm{~S~}}$) and $0$ experience points.    

As she encouters each mandragora, her choices are:

Garnet's pet eats mandragora $\boldsymbol{i}$. This increments $\boldsymbol{\mathrm{~S~}}$ by $1$ and defeats mandragora $\boldsymbol{i}$.  
Garnet's pet battles mandragora $\boldsymbol{i}$. This increases $\boldsymbol{p}$ by $s\times H[i]$ experience points and defeats mandragora $\boldsymbol{i}$. 

Once she defeats a mandragora, it is out of play.  Given a list of mandragoras with various health levels, determine the maximum number of experience points she can collect on her journey.  

For example, as always, she starts out with $s=1$ health point and $p=0$ experience points.  Mandragoras have the following health values: $H=[3,2,5]$.  For each of the beings, she has two choices, $\boldsymbol{\mathrm{~e~}}$at or $\boldsymbol{b}$attle.  We have the following permutations of choices and outcomes:

Action  s   p
_______ _   __
e, e, e 4   0
e, e, b 3   15
e, b, b 2   14
b, b, b 1   10
b, b, e 2   10
b, e, e 3   9
b, e, b 2   16
e, b, e 3   6

Working through a couple of rows, first, her pet can eat all three and she does not gain any experience points.  In the second row, her pet eats the first two to have $1+2=3$ health points, then battles the beast with $5$ heatlth points to gain $3*5=15$ experience points.  We see that the best option is to eat the beast with $2$ points and battle the others to achieve $2\times(3+5)=16$ experience points.

Function Description  

Complete the mandragora function in the editor below.  It must return an integer that denotes the maximum number of experience points that Garnet can earn.

mandragora has the following parameter(s):  

H: an array of integers that represents the health values of mandragoras  

Input Format

The first line contains an integer, $\boldsymbol{\boldsymbol{t}}$, denoting the number of test cases. Each test case is described over two lines:

The first line contains a single integer $n$, the number of mandragoras in the forest. 
The second line contains $n$ space-separated integers describing the respective health points for the mandragoras $H[H[1],H[2]...H[n]]$.    

Constraints

$1\leq t\leq10^5$   
$1\leq n\leq10^5$   
$1\leq H[i]\leq10^7$, where $1\leq i\leq n$   
The sum of all $n$s in a single test case is $\leq10^{6}$  

Output Format

For each test case, print a single line with an integer denoting the maximum number of experience points that Garnet can earn.

Sample Input
1
3
3 2 2

Sample Output
10 

Explanation

There are $n=3$ mandragoras having the following health points: $H=[3,2,2]$. Initially, $s=1$ and $p=0$. The following is an optimal sequence of actions for achieving the maximum number of experience points possible:  

Eat the second mandragora ($H[2]=2$). $\boldsymbol{\mathrm{~S~}}$ is increased from $1$ to $2$, and $\boldsymbol{p}$ is still $0$. 
Battle the first mandragora ($H[1]=3$). $\boldsymbol{\mathrm{~S~}}$ remains the same, but $\boldsymbol{p}$ increases by $s\times H[1]=2\times3=6$ experience points. 
Battle the third mandragora ($H[3]=2$). $\boldsymbol{\mathrm{~S~}}$ remains the same, but $\boldsymbol{p}$ increases by $s\times H[3]=2\times2=4$ experience points. 

Garnet earns $p=6+4=10$ experience points.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def main():
	t = int(input())
	while t > 0:
		n = int(input())
		a = list(map(int, input().split()))
		a.sort()
		b = a[:]
		for i in range(n - 2, -1, -1):
			b[i] = a[i] + b[i + 1]
		ans = b[0]
		for i in range(n):
			ans = max(ans, (i + 1) * b[i])
		print(ans)
		t -= 1
main()


t = int(input())
for _ in range(t):
	n = int(input())
	h = sorted((int(x) for x in input().split()))
	s = m = sum(h)
	for (i, hp) in enumerate(h, 2):
		s -= hp
		m = max(m, s * i)
	print(m)


for _ in range(int(input())):
	n = int(input())
	h = sorted(list(map(int, input().split())), reverse=True)
	cumsum = [h[0]]
	for i in range(1, n):
		cumsum.append(cumsum[-1] + h[i])
	r = 0
	for i in range(n):
		r = max(r, cumsum[i] * (n - i))
	print(r)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	h.sort(reverse=True)
	res = 0
	somme = 0
	for (i, hi) in enumerate(h):
		somme += hi
		xp = somme * (n - i)
		if res < xp:
			res = xp
		else:
			break
	print(res)


t = int(input())
for tc in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	h.sort()
	scores = [0] * n
	h_sum = 0
	for i in reversed(range(n)):
		s = i + 1
		h_sum += h[i]
		scores[i] = s * h_sum
	print(max(scores))


def fun(a, n):
	a.sort()
	ans = -1
	s = 0
	for i in range(n - 1, -1, -1):
		s += a[i]
		if (i + 1) * s > ans:
			ans = (i + 1) * s
	return ans
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	a = [int(i) for i in input().split()]
	print(fun(a, n))


from collections import Counter

def line():
	return input().strip()

def intline():
	return int(line())

def aline():
	return line().split(' ')

def aintline():
	return [int(x) for x in aline()]

def solve(h):
	h.sort()
	p = sum(h)
	s = 1
	i = 0
	while True:
		rem = h[i] * s
		newp = (p - rem) // s * (s + 1)
		s = s + 1
		if newp < p:
			return p
		p = newp
		i = i + 1
	raise Exception
t = intline()
for i in range(t):
	n = intline()
	h = aintline()
	print(solve(h))


def ans(arr, n):
	H = sorted(arr)
	s = [sum(H)]
	last = s[0]
	m = last
	for i in range(1, n):
		s.append(s[i - 1] - H[i - 1])
		curr = s[i] * (i + 1)
		if curr > m:
			m = curr
	return m
for _ in range(int(input().strip())):
	n = int(input().strip())
	arr = [int(x) for x in input().strip().split()]
	print(ans(arr, n))


T = int(input())
for _ in range(T):
	N = int(input())
	H_s = sorted(map(int, input().split()), reverse=True)
	P = 0
	accum = 0
	for i in range(N):
		accum += H_s[i]
		P = max(P, accum * (N - i))
	print(P)


t = int(input())
for __ in range(t):
	n = int(input())
	ar = sorted(map(int, input().split()))
	remaining = sum(ar)
	s = 1
	for x in ar:
		if s * remaining < (s + 1) * (remaining - x):
			s += 1
			remaining -= x
			continue
		else:
			print(s * remaining)
			break


from sys import stderr

def readlist(f):
	return [f(x) for x in input().split()]
T = int(input())
for t in range(T):
	N = int(input())
	H = readlist(int)
	S = 1
	P = 0
	Hs = sorted(H)
	Hr = sum(H)
	for h in Hs:
		eat = Hr - h
		battle = S * h
		if eat < battle:
			P += battle
		else:
			S += 1
		Hr -= h
	print(P)


T = int(input())
for t in range(T):
	n = int(input())
	h = list(map(int, input().split()))
	h.sort()
	if n == 1:
		res = max(2, h[0])
	else:
		res = 0
		s = 0
		for i in range(n, 0, -1):
			if s > h[i - 1] * i:
				res = s * (i + 1)
				break
			s += h[i - 1]
	print(res)


def main():
	t = int(input().strip())
	for _ in range(t):
		n = int(input().strip())
		l = sorted([int(i) for i in input().strip().split()])
		sum = l[:]
		for i in range(1, n):
			sum[i] += sum[i - 1]
		ans = sum[n - 1]
		for i in range(n):
			temp = (i + 2) * (sum[n - 1] - sum[i])
			ans = max(ans, temp)
		print(ans)
main()


T = int(input())
for j in range(T):
	N = int(input())
	nums = [int(Bk) for Bk in input().split()]
	nums.sort()
	for i in range(len(nums) - 2, -1, -1):
		nums[i] = nums[i] + nums[i + 1]
	S = 1
	product = 0
	for i in range(len(nums)):
		prod = S * nums[i]
		S = S + 1
		if product < prod:
			product = prod
	print(product)


T = int(input())
for t in range(T):
	N = int(input())
	h = [int(x) for x in input().split()]
	h.sort()
	i = N
	s = h[N - 1]
	p = 0
	while i * s > p:
		p = i * s
		i -= 1
		s += h[i - 1]
	print(p)


T = int(input())
for i in range(T):
	N = int(input())
	H = [int(a) for a in input().split()]
	S = 1
	P = 0
	H = sorted(H)
	sumH = sum(H)
	for i in range(len(H)):
		if sumH * S < (sumH - H[i]) * (S + 1):
			S += 1
		else:
			P = sumH * S
			break
		sumH -= H[i]
	print(P)


import sys

def solve(ns):
	lns = len(ns)
	result = []
	ns.sort()
	ns.reverse()
	s = 0
	for (i, n) in enumerate(ns):
		s += n
		result.append(s * (lns - i))
	return max(result)
t = int(next(sys.stdin))
for i in range(t):
	n = int(next(sys.stdin))
	ns = [int(x) for x in next(sys.stdin).split()]
	print(solve(ns))


T = int(input())
for i in range(T):
	input()
	H = sorted(list(map(lambda x: int(x), input().split(' '))))
	cumsum = [H[-1]]
	for j in range(-2, -(len(H) + 1), -1):
		cumsum.append(cumsum[-1] + H[j])
	cumsum.reverse()
	prod = map(lambda x, y: x * y, cumsum, range(1, len(H) + 1))
	print(max(prod))


import sys
from collections import Counter
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	H = [int(q_temp) for q_temp in input().strip().split(' ')]
	h = H.copy()
	h.sort()
	hsize = len(h)
	S = 1
	P = 0
	max_score = 0
	battle = 0
	for i in range(hsize):
		cut = hsize - 1 - i
		battle += h[cut]
		score = battle * (1 + cut)
		if score > max_score:
			max_score = score
	print(max_score)


def mkarray(n):
	return [0] * n

def solve(n, h):
	h.sort()
	m = [0] * n
	m[0] = h[-1]
	for i in range(1, n):
		m[i] = m[i - 1] + h[-i - 1]
	p = 0
	for i in range(n):
		t = m[i] * (n - i)
		if t < p:
			break
		p = t
	print(p)
for _ in range(int(input())):
	solve(int(input()), [int(x) for x in input().split(' ')])


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	su = sum(a)
	b = [a[0]]
	for i in range(1, n):
		b.append(b[i - 1] + a[i])
	p = 0
	s = 1
	for i in range(n):
		if s * a[i] > su - b[i]:
			p += s * a[i]
		else:
			s += 1
	print(p)


for _ in range(int(input())):
	N = int(input())
	H = input().split()
	H = [int(H[i]) for i in range(N)]
	H = sorted(H)
	P = 0
	S = 1
	if N == 1:
		print(H[0])
	else:
		cummSumH = [0 for i in range(N)]
		cummSumH[-1] = H[-1]
		for i in range(N - 2, -1, -1):
			cummSumH[i] = cummSumH[i + 1] + H[i]
		for i in range(N - 1):
			if H[i] * S < cummSumH[i + 1]:
				S += 1
			else:
				P += S * cummSumH[i]
				break
		if P == 0:
			print(S * H[-1])
		else:
			print(P)


from functools import reduce
from operator import add

def max_score(N, H):
	H_s = sorted(H)
	tots = [0] * N
	tots[0] = H_s[0]
	for x in range(1, N):
		tots[x] = tots[x - 1] + H_s[x]
	best = H_s[0]
	for x in range(1, N):
		best = max(best, (tots[N - 1] - tots[x - 1]) * (x + 1))
	return best
T = int(input())
for _ in range(T):
	N = int(input())
	H = list(map(int, input().strip().split()))
	print(max_score(N, H))


T = int(input())
for _ in range(T):
	N = int(input())
	H_s = sorted(map(int, input().split()), reverse=True)
	P = 0
	accum = 0
	for i in range(N):
		accum += H_s[i]
		P = max(P, accum * (N - i))
	print(P)


T = int(input())
for _ in range(T):
	N = int(input())
	H_s = sorted(map(int, input().split()), reverse=True)
	P = 0
	accum = 0
	for i in range(N):
		accum += H_s[i]
		P = max(P, accum * (N - i))
	print(P)


t = int(input())
for t_ in range(t):
	n = int(input())
	H = [int(x) for x in input().split()]
	H.sort(reverse=True)
	S = [H[0]]
	for x in H[1:]:
		S.append(S[-1] + x)
	S = S[::-1]
	H = H[::-1]
	print(max([S[i] * (i + 1) for i in range(n)]))


T = int(input())
for t in range(T):
	N = int(input())
	S = [int(x) for x in input().split()]
	tot = sum(S)
	best = tot
	S.sort()
	for i in range(N):
		tot -= S[i]
		pts = tot * (i + 2)
		if pts > best:
			best = pts
	print(best)


T = int(input())
for _ in range(T):
	N = int(input())
	H = [int(x) for x in input().split()]
	H.sort(key=lambda x: -x)
	base_P = sum(H)
	S = 1
	while True:
		h = H[-1]
		new_P = base_P - h
		if new_P * (S + 1) <= base_P * S:
			break
		H.pop()
		S += 1
		base_P = new_P
	print(base_P * S)


import heapq
for k in range(int(input())):
	n = int(input())
	mandra = [int(hp) for hp in input().split()]
	bestScore = sum(mandra)
	heapq.heapify(mandra)
	k = 2
	remaining = bestScore - heapq.heappop(mandra)
	otherScore = k * sum(mandra)
	while otherScore > bestScore:
		bestScore = otherScore
		k += 1
		remaining -= heapq.heappop(mandra)
		otherScore = k * remaining
	print(bestScore)


def calculateOptimalExp(arr):
	s = 1
	arr.sort()
	exp = sum(arr)
	for i in range(len(arr)):
		newExp = (int(exp / s) - arr[i]) * (s + 1)
		if newExp > exp:
			s += 1
			exp = newExp
		else:
			break
	return int(exp)

def main():
	t = int(input())
	for case in range(t):
		n = input()
		arr = [int(i) for i in input().split()]
		print(calculateOptimalExp(arr))
main()


def experience(m):
	n = len(m)
	if n == 1:
		return m[0]
	elif n == 2:
		return max(sum(m), 2 * m[1])
	elif n == 3:
		return max(sum(m), 2 * (m[1] + m[2]), 3 * m[2])
	else:
		left = 0
		right = n
		mid = int((left + right) / 2)
		while 1:
			mid_value = (mid + 1) * sum(m[mid:n])
			prev_value = mid * sum(m[mid - 1:n])
			next_value = (mid + 2) * sum(m[mid + 1:n])
			if next_value < mid_value and prev_value <= mid_value:
				return mid_value
			elif next_value >= mid_value:
				left = mid
				mid = int((left + right) / 2)
			elif prev_value >= mid_value:
				right = mid
				mid = int((left + right) / 2)
t = int(input())
for i in range(0, t):
	n = int(input())
	m = [int(mi) for mi in input().split()]
	m = sorted(m)
	print(experience(m))


def get_max_score(mandragoras):
	experience = 0
	strength = 1
	sorted_hp_list = sorted(mandragoras)
	hp_sum = sum(mandragoras)
	for i in range(len(sorted_hp_list)):
		kill_sum = strength * hp_sum
		eat_sum = (strength + 1) * (hp_sum - sorted_hp_list[i])
		if eat_sum > kill_sum:
			strength += 1
			hp_sum -= sorted_hp_list[i]
		else:
			experience = strength * hp_sum
			return experience
t = int(input())
for i in range(t):
	n_mandragoras = int(input())
	mandragoras = [int(x) for x in input().split()]
	print(get_max_score(mandragoras))


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	H = [int(x) for x in input().split()]
	H_sorted = sorted(H)
	s = 1
	max_xp = 0
	H_sum = sum(H)
	for i in range(0, len(H)):
		max_xp = max(s * H_sum, max_xp)
		s += 1
		H_sum -= H_sorted[i]
	print(max_xp)


t = int(input())
for _ in range(t):
	exp = 0
	n = int(input())
	hp = []
	hp.extend(map(int, input().split()))
	hp.sort()
	for i in reversed(range(n - 1)):
		hp[i] += hp[i + 1]
	for i in range(n):
		hp[i] *= i + 1
		exp = max(exp, hp[i])
	print(str(exp))


T = int(input().strip())
for ti in range(T):
	N = int(input().strip())
	H = [int(inp) for inp in input().strip().split(' ')]
	H.sort(reverse=True)
	S = [0]
	for Hi in H:
		S.append(S[-1] + Hi)
	S.reverse()
	print(max(map(int.__mul__, range(1, N + 2), S)))


T = int(input())
for tc in range(T):
	n = int(input())
	h = list(map(int, input().split()))
	h.sort()
	s = 1
	sm = sum(h)
	P = 0
	for i in range(n):
		if s * sm > (s + 1) * (sm - h[i]):
			P += s * h[i]
		else:
			s += 1
		sm -= h[i]
	print(P)


t = int(input())
for time in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	prev = 0
	h.sort()
	for i in range(n)[::-1]:
		h[i] = prev + h[i]
		prev = h[i]
	s = 1
	p = 0
	ans = 0
	for i in range(n)[::-1]:
		p = h[i]
		ans = max(ans, p * (i + 1))
	print(ans)


def sum_arr(m):
	summed = [0]
	for (i, num) in enumerate(m):
		summed.append(summed[i] + num)
	return summed

def maximize(m):
	summed = sum_arr(m)
	strength = 1
	curr_delta = summed[-1]
	delta = 0
	while True:
		strength += 1
		delta = strength * (summed[-1] - summed[strength - 1])
		if curr_delta < delta:
			curr_delta = delta
		else:
			return curr_delta

def main():
	n_cases = int(input())
	for _ in range(n_cases):
		_ = input()
		mandragoras_sorted = sorted([int(h) for h in input().split()])
		print(maximize(mandragoras_sorted))
main()


for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	A.sort()
	maxi = A[-1] * n
	s = A[-1]
	for i in range(2, n + 1):
		s = s + A[-i]
		if (n + 1 - i) * s > maxi:
			maxi = (n + 1 - i) * s
	print(maxi)


T = int(input())
for t in range(T):
	input()
	arr = [int(i) for i in input().strip().split()]
	arr.sort()
	strength = 1
	consumed_health_points = sum(arr)
	experience = strength * consumed_health_points
	for health_point in arr:
		strength += 1
		consumed_health_points -= health_point
		temp_experience = strength * consumed_health_points
		if temp_experience > experience:
			experience = temp_experience
		else:
			break
	print(experience)


def solve(H):
	H.sort(reverse=True)
	(best, total, nb) = (0, 0, len(H) + 1)
	for h in H:
		total += h
		nb -= 1
		if nb * total > best:
			best = nb * total
	return best
T = int(input())
for _ in range(T):
	N = int(input())
	H = list(map(int, input().split()))
	print(solve(H))


import heapq
for _ in range(int(input())):
	input()
	h = [int(x) for x in input().split()]
	heapq.heapify(h)
	(s, p) = (1, 0)
	hsum = sum(h)
	while h:
		m = heapq.heappop(h)
		if hsum * s < (hsum - m) * (s + 1):
			hsum -= m
			s += 1
		else:
			break
	p += hsum * s
	print(p)


def findMaxPoints(data, n, i, S, P):
	max_sum = 0
	sum_data = 0
	for i in range(n):
		sum_data += data[i]
		max_sum = max((n - i) * sum_data, max_sum)
	return max_sum
cases = int(input())
for i in range(cases):
	n = int(input())
	data = list(map(int, input().split(' ')))
	data = sorted(data, reverse=True)
	print(findMaxPoints(data, n, 0, 1, 0))


T = int(input())
for case in range(T):
	global s
	N = int(input())
	a = [int(i) for i in input().split(' ')]
	a = sorted(a)
	s = 0

	def p(i):
		global s
		s += a[i]
		return (i + 1) * s
	print(max([p(i) for i in range(N - 1, -1, -1)]))


cases = int(input())

def solve(array):
	nsum = sum(array)
	array.sort()
	maxp = nsum
	for (i, h) in enumerate(array):
		nsum -= array[i]
		p = nsum * (i + 2)
		if p > maxp:
			maxp = p
	return maxp
for i in range(cases):
	N = int(input())
	array = list(map(int, input().split()))
	print(solve(array))


def solve(m, hi):
	s = 1
	sorted_hi = sorted(hi)
	left_mandragogas = sum(sorted_hi)
	p = left_mandragogas * s
	for i in range(m):
		s += 1
		left_mandragogas -= sorted_hi[i]
		if p < s * left_mandragogas:
			p = s * left_mandragogas
	print(p)

def get_input():
	for t in range(int(input())):
		m = int(input())
		hi = list(map(int, input().split()))
		solve(m, hi)
get_input()


T = int(input())
for i in range(0, T):
	N = int(input())
	H = [int(x) for x in input().split()]
	H.sort()
	xp = sum(H)
	maxxp = xp
	S = 2
	for k in range(0, len(H)):
		xp -= int((S - 1) * H[k])
		xp = xp // max(1, S - 1)
		xp = int(xp * S)
		S += 1
		if xp > maxxp:
			maxxp = xp
	print('%i' % maxxp)


def runTest():
	N = int(input())
	health = sorted([int(x) for x in input().split()], reverse=True)
	cumsum = health.copy()
	for i in range(1, N):
		cumsum[i] = cumsum[i - 1] + health[i]
	print(max(((i + 1) * cumsum[-i - 1] for i in range(N))))
T = int(input())
for i in range(T):
	runTest()


for testCase in range(int(input())):
	input()
	mandragores = sorted(map(int, input().split()))
	result = [sum(mandragores)]
	for health in mandragores:
		result.append(result[-1] - health)
	maxResult = 0
	for i in range(len(result)):
		result[i] *= i + 1
		if result[i] <= maxResult:
			print(maxResult)
			break
		else:
			maxResult = result[i]


T = int(input())
for t in range(T):
	N = int(input())
	H = [int(x) for x in input().split()]
	H.sort()
	S = 1
	P = 0
	s = sum(H)
	for i in range(N):
		s -= H[i]
		if S * H[i] < s:
			S += 1
		else:
			P += S * H[i]
	print(P)


t = int(input())
for _ in range(t):
	n = int(input())
	m = [int(el) for el in input().split()]
	sum = 0
	for el in m:
		sum += el
	s = 1
	m.sort()
	maxp = sum
	for i in range(n):
		sum -= m[i]
		s += 1
		maxp = max(maxp, s * sum)
	print(maxp)


import sys
T = int(next(sys.stdin))
for i in range(T):
	N = int(next(sys.stdin))
	H = sorted((int(x) for (j, x) in enumerate(next(sys.stdin).split())))
	assert len(H) == N
	greatest = sum(H)
	sum_so_far = greatest
	for (j, h) in enumerate(H):
		sum_so_far -= h
		P = (j + 2) * sum_so_far
		if P > greatest:
			greatest = P
	assert sum_so_far == 0
	print(greatest)


import sys

def f(a):
	a = sorted(a, reverse=True)
	mul = len(a)
	if mul == 0:
		return 0
	acc = a[0]
	max = acc * mul
	for v in a[1:]:
		mul -= 1
		acc += v
		val = acc * mul
		if val > max:
			max = val
		else:
			break
	return max
n = int(input().strip())
for i in range(n):
	input()
	c = [int(c_temp) for c_temp in input().strip().split(' ')]
	print(f(c))


Ntests = int(input().strip())
for _ in range(Ntests):
	Nmandragoras = int(input().strip())
	Health = list(map(int, input().strip().split()))
	Health.sort()
	S = Nmandragoras
	P = 0
	health_sum = [0] * (Nmandragoras + 1)
	for i in range(1, Nmandragoras + 1):
		health_sum[i] = health_sum[i - 1] + Health[Nmandragoras - (i - 1) - 1]
	eaten = Nmandragoras
	battled = 0

	def opt_func(i):
		return (Nmandragoras - i) * health_sum[i + 1]
	left = 0
	right = Nmandragoras - 1

	def findmax():
		left = 0
		right = Nmandragoras - 1
		if left == right:
			return opt_func(left)
		while True:
			if opt_func(left) >= opt_func(left + 1):
				return opt_func(left)
			elif opt_func(right) >= opt_func(right - 1):
				return opt_func(right)
			mid = (left + right) // 2
			if opt_func(mid) > opt_func(mid - 1):
				left = mid
			if opt_func(mid + 1) < opt_func(mid):
				right = mid
	print(findmax())


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	h = sorted(h)
	m = n - 1
	done = False
	P = 0
	total = h[m]
	while not done:
		hm = (m + 1) * total
		if hm > P:
			P = hm
			m -= 1
			total += h[m]
		else:
			done = True
		if m < 0:
			done = True
	print(P)


from sys import stderr

def read(f):
	return map(f, input().split())

def readlist(f):
	return [f(x) for x in input().split()]
(T,) = read(int)
for t in range(T):
	(N,) = read(int)
	H = readlist(int)
	H.sort()
	P = 0
	S = 1
	Hsum = sum(H)
	for Hi in H:
		if Hsum <= Hi * (S + 1):
			break
		Hsum -= Hi
		S += 1
	P = S * Hsum
	print(P)


nb_cases = int(input())
for case in range(nb_cases):
	nb_mand = int(input())
	data = [int(x) for x in input().split(' ')]
	data.sort()
	s = 1
	raw_xp = sum(data)
	max_xp = raw_xp
	iter_sum = 0
	for m in data:
		iter_sum += m
		remaining = raw_xp - iter_sum
		s += 1
		tmp_max_xp = remaining * s
		if tmp_max_xp >= max_xp:
			max_xp = tmp_max_xp
		else:
			break
	print(max_xp)


T = int(input())
for t in range(T):
	n = int(input())
	h = [int(x) for x in input().split()]
	h.sort()
	c = h[n - 1]
	m = n * c
	for i in range(n - 2, -1, -1):
		c += h[i]
		m = max(m, (i + 1) * c)
	print(m)


for _ in range(int(input())):
	N = int(input())
	A = sorted([int(x) for x in input().strip().split()])
	partial_sums = [0] * N
	partial_sums[-1] = A[-1]
	for i in range(N - 2, -1, -1):
		partial_sums[i] = A[i] + partial_sums[i + 1]
	ans = max([(i + 1) * partial_sums[i] for i in range(N)])
	print(ans)


test_cases = int(input())
for t in range(test_cases):
	n = int(input())
	h = [int(i) for i in input().split()]
	h.sort()
	ans = 0
	p = 0
	for k in range(n)[::-1]:
		p += h[k]
		ans = max(ans, p * (k + 1))
	print(ans)


from itertools import accumulate

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		healths = [int(h) for h in input().split()]
		result = max_experience(healths)
		print(result)

def max_experience(healths):
	health_sums = list(accumulate(reversed(sorted(healths))))
	strengths = reversed(range(1, len(healths) + 1))
	possibilities = [strength * health_sum for (strength, health_sum) in zip(strengths, health_sums)]
	return max(possibilities)
main()


from itertools import accumulate

def row(fn):
	return list(map(fn, input().strip().split()))
for t in range(int(input())):
	(S, P) = (1, 0)
	n = int(input())
	H = sorted(row(int))
	rest = list(reversed(list(accumulate(reversed(H)))))
	for (i, h) in enumerate(H):
		if i == n - 1 or S * h > rest[i + 1]:
			P += S * rest[i]
			break
		else:
			S += 1
	print(P)


t = int(input())
while t:
	t += -1
	n = int(input())
	health = [int(x) for x in input().split()]
	health.sort()
	(s, p) = (1, 0)
	total = sum(health)
	m = s * total
	ans = s * total
	for i in range(0, n):
		s = s + 1
		total = total - health[i]
		m = s * total
		if m > ans:
			ans = m
	print(ans)


def init():
	t = int(input())
	for i in range(t):
		global s, p, h, n
		n = int(input())
		h = [int(a) for a in input().split(' ')]
		h.sort()
		s = 1
		p = 0
		if n >= 3:
			main()
		else:
			k = []
			for i in range(n):
				k.append(compute(i))
			print(max(k))

def greed(a, b):
	m = a + int((b - a) / 2)
	mid = compute(m)
	mid_plus = compute(m + 1)
	mid_minus = compute(m - 1)
	if mid >= mid_plus:
		if mid >= mid_minus:
			print(mid)
		else:
			greed(a, m)
	else:
		greed(m, b)

def main():
	global n
	greed(0, n)

def compute(g):
	global n, h
	s = g + 1
	p = 0
	for i in range(g, n):
		p += s * h[i]
	return p
init()


num_tests = int(input())
for i in range(num_tests):
	input()
	ds = sorted((int(d) for d in input().split()))
	n = len(ds)
	m = 0
	total_health = sum(ds)
	for eaten in range(n):
		new_m = (eaten + 1) * total_health
		if new_m < m:
			break
		else:
			total_health -= ds[eaten]
		m = new_m
	print(m)


for test in range(int(input())):
	n = int(input())
	l = sorted([int(x) for x in input().split()])
	ans = [0 for x in range(n)]
	s = n
	d = 0
	m = 0
	d = 0
	a = 0
	for i in range(n - 1, -1, -1):
		ans[i] = s * l[i]
		t = ans[i]
		ans[i] += d
		if ans[i] > a:
			a = ans[i]
		s -= 1
		m += l[i]
		d += t
		d -= m
	print(a)


T = int(input())
for t in range(T):
	N = int(input())
	H = sorted([int(h) for h in input().split(' ')], reverse=True)
	x = 0
	opt = 0
	for (i, h) in enumerate(H):
		x += h
		opt = max(opt, x * (N - i))
	print(opt)


import sys
import math
__author__ = 'GlukAlex'
is_Debug_Mode = False
test_Cases_T = int(input().strip())
print('test_Cases_T:{}'.format(test_Cases_T), file=sys.stderr) if is_Debug_Mode else None
for t_Index in range(0, test_Cases_T, 1):
	mandragoras_Total_N = int(input().strip())
	health_Points_List = list(map(int, input().strip().split(' ')))
	if False or is_Debug_Mode:
		print('health_Points_List({}):{}'.format(len(health_Points_List), health_Points_List), file=sys.stderr)
	health_Points_List.sort()
	if False or is_Debug_Mode:
		print('health_Points_Sorted({}):{}'.format(len(health_Points_List), health_Points_List), file=sys.stderr)
	if False and True:
		total_Health = sum(health_Points_List)
		if False or is_Debug_Mode:
			print('total_Health:{}'.format(total_Health), file=sys.stderr)
		split_Index = mandragoras_Total_N // 2
		experience_Points_P = 0
		for i in range(0, mandragoras_Total_N - 1, 1):
			subOptimal_P = total_Health * (i + 1)
			total_Health -= health_Points_List[i]
			if experience_Points_P < subOptimal_P:
				experience_Points_P = subOptimal_P
			elif experience_Points_P == subOptimal_P:
				pass
			else:
				pass
	if False or True:
		experience_Points_P = 0
		total_Health = 0
		for i in range(mandragoras_Total_N - 1, -1, -1):
			total_Health += health_Points_List[i]
			subOptimal_P = total_Health * (i + 1)
			if False and True:
				subOptimal_P = 0
				for h in health_Points_List[i:]:
					subOptimal_P += (i + 1) * h
			if experience_Points_P < subOptimal_P:
				experience_Points_P = subOptimal_P
			else:
				break
	if False and True:
		split_Index = mandragoras_Total_N // 2
		l = health_Points_List
		experience_Points_P = max((sum(map(lambda v: v * (i + 1), l[i:])) for i in range(len(l) - 1, split_Index - 1, -1)))
	if False and True:
		split_Index = mandragoras_Total_N // 2
		lesser_Half = health_Points_List[:split_Index]
		bigger_Half = health_Points_List[split_Index:]
		strength_Points_S = 1
		experience_Points_P = 0
		strength_Points_S += len(lesser_Half)
		if False and True:
			for h in bigger_Half:
				experience_Points_P += strength_Points_S * h
		experience_Points_P = sum(bigger_Half) * strength_Points_S
		if False or is_Debug_Mode:
			print('strength_Points_S:{}, experience_Points_P[{}]:{}'.format(strength_Points_S, split_Index, experience_Points_P), file=sys.stderr)
		for i in range(split_Index - 1, -1, -1):
			subOptimal_P = sum(lesser_Half[:i]) * (i + 1 + 1)
			if experience_Points_P < subOptimal_P:
				experience_Points_P = subOptimal_P
			elif experience_Points_P == subOptimal_P:
				pass
			else:
				break
		if False or is_Debug_Mode:
			print('experience_Points_P(down):{}'.format(experience_Points_P), file=sys.stderr)
		for i in range(split_Index + 1, mandragoras_Total_N - 1, 1):
			subOptimal_P = sum(bigger_Half[i:]) * (i + 1 + 1)
			if experience_Points_P < subOptimal_P:
				experience_Points_P = subOptimal_P
			elif experience_Points_P == subOptimal_P:
				pass
			else:
				break
	print(experience_Points_P)


import sys

def solve_bf(hh):
	maxp = 0
	stack = [(1, 0, hh)]
	while stack:
		(s, p, hh) = stack.pop()
		maxp = max(p, maxp)
		for (i, h) in enumerate(hh):
			new_hh = hh[:i] + hh[i + 1:]
			stack.append((s + 1, p, new_hh))
			stack.append((s, p + s * h, new_hh))
	return maxp

def solve(hh, debug=0):
	hh.sort()
	if debug > 0:
		print(hh, file=sys.stderr)
	(s, p) = (1, sum(hh))
	mx = p
	for (i, h) in enumerate(hh):
		mx = max(mx, p)
		if debug > 0:
			print('i=%d s=%d p=%d mx=%d' % (i, s, p, mx), file=sys.stderr)
		new_s = s + 1
		new_p = (p // s - h) * new_s
		(s, p) = (new_s, new_p)
	if debug > 0:
		print('i=%d s=%d p=%d mx=%d' % (i, s, p, mx), file=sys.stderr)
	return mx
debug = 0
t = int(input())
for _ in range(t):
	_ = int(input())
	hh = list(map(int, input().split()))
	print(solve(hh, debug))


z = int(input().strip())
for j in range(0, z):
	n = int(input().strip())
	sm = input().strip().split(' ')
	str1 = []
	for i in sm:
		str1.append(int(i))
	str1.sort()
	sum1 = sum(str1)
	s = 1
	p = 0
	for i in str1:
		x = sum1 * s
		if x > p:
			p = x
		sum1 = sum1 - i
		s += 1
	print(p)


def fdp(h):
	h = list(sorted(h))
	suffixes = []
	sm = 0
	for i in reversed(h):
		sm += i
		suffixes.append(sm)
	suffixes = list(reversed(suffixes))
	mx = 0
	for i in range(len(h)):
		mx = max(mx, (i + 1) * suffixes[i])
	return mx
for _ in range(int(input())):
	input()
	bs = [int(b) for b in input().strip().split(' ')]
	print(fdp(bs))


T = int(input())
for Ti in range(T):
	N = int(input())
	H = list(sorted((int(v) for v in input().split())))
	health = sum(H)
	strength = 1
	exp = health * strength
	for Hi in H:
		strength += 1
		health -= Hi
		exp = max(exp, health * strength)
	print(exp)


t = int(input())
for i in range(t):
	n = int(input())
	m = [int(a) for a in input().split(' ')]
	m.sort()
	xpLeft = sum(m)
	(p, s) = (0, 1)
	for i in range(len(m)):
		if xpLeft * s < (xpLeft - m[i]) * (s + 1):
			s += 1
			xpLeft -= m[i]
		else:
			p += s * m[i]
			xpLeft -= m[i]
	print(p)


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

def read_ints():
	return [int(x) for x in input().strip().split(' ')]

def compute_experience_points(Hs):
	Hs.sort()
	S = 1
	sum_rem_Hs = sum(Hs)
	max_p = sum_rem_Hs
	for h in Hs:
		S += 1
		sum_rem_Hs -= h
		P = S * sum_rem_Hs
		if P > max_p:
			max_p = P
	return max_p
T = read_int()
for t in range(T):
	N = read_int()
	Hs = read_ints()
	ep = compute_experience_points(Hs)
	print(ep)


def maximizeProductSum(l, s=1, p=0):
	l = sorted(l)
	p = sum(l)
	p_minus_h = p
	for h in l:
		p_minus_h -= h
		s += 1
		p = max(p, p_minus_h * s)
	return int(p)
t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	print(maximizeProductSum(l))


N = int(input())
for n in range(N):
	input()
	hps = sorted(list(map(int, input().split())))
	s = 1
	total = sum(hps)
	for hp in hps:
		if (s + 1) * (total - hp) <= s * total:
			break
		s += 1
		total -= hp
	print(s * total)


t = int(input().strip())
for test in range(t):
	n = int(input().strip())
	a = [int(s) for s in input().strip().split()]
	a.sort(reverse=True)
	c = 0
	o = 0
	for v in a:
		c += v
		p = c * n
		if p < o:
			break
		o = p
		n -= 1
	print(o)


def mandragora(hvec):
	N = len(hvec)
	hvec.sort()
	diff = [0] * N
	i = N - 1
	hcum = hvec[-1]
	while i > 0:
		diff[i] = hcum - i * hvec[i - 1]
		i -= 1
		hcum += hvec[i]
	diff[0] = hcum - 1
	pk = 1
	max_so_far = 1
	for i in range(N):
		pk += diff[i]
		max_so_far = max(max_so_far, pk)
	print(max_so_far)
T = int(input())
while T:
	n = int(input())
	arr = [int(s) for s in input().split()]
	mandragora(arr)
	T -= 1


T = int(input())
for i in range(T):
	N = int(input())
	H = sorted(map(int, input().split(' ')))
	for j in range(1, N):
		H[j] += H[j - 1]
	res = H[N - 1]
	for j in range(1, N):
		res = max(res, (j + 1) * (H[N - 1] - H[j - 1]))
	print(res)


t = int(input().strip())
for _t in range(t):
	n = int(input().strip())
	h = sorted([int(x) for x in input().split()], reverse=True)
	sumNums = 0
	s = 1
	p = 0
	maxExp = 0
	for i in range(n):
		sumNums += h[i]
		maxExp = max(maxExp, sumNums * (1 + n - 1 - i))
	print(maxExp)


t = int(input())
for test in range(t):
	n = int(input())
	h = [int(a_t) for a_t in input().split()]
	h = sorted(h)
	s = 1
	p = 1
	total_h = sum(h)
	i = 0
	while i < len(h) and total_h * s < (s + 1) * (total_h - h[i]):
		s += 1
		total_h -= h[i]
		i += 1
	print(total_h * s)


def best_xp(healths):
	best = 0
	sum_uneaten = sum(healths)
	for num_eaten in range(0, len(healths)):
		final_P = (num_eaten + 1) * sum_uneaten
		if best > final_P:
			return best
		else:
			best = final_P
			sum_uneaten -= healths[num_eaten]
	return best
num_cases = int(input())
for i in range(0, num_cases):
	input()
	print(best_xp(sorted([int(n) for n in input().split()])))


def max_experience(mandragoras, N):
	if N == 1:
		return mandragoras[0]
	mandragoras.sort()
	S = 1
	H = sum(mandragoras)
	index = 0
	curr_score = S * H
	while index < N:
		S += 1
		H -= mandragoras[index]
		index += 1
		prospective_score = S * H
		if prospective_score <= curr_score:
			return curr_score
		curr_score = prospective_score
	return curr_score
T = int(input())
for _ in range(T):
	N = int(input())
	mandragoras = [int(x) for x in input().strip().split()]
	print(max_experience(mandragoras, N))


test_cases = int(input())
for test_case in range(test_cases):
	size = int(input())
	mandragoras = list(map(int, input().strip().split(' ')))
	mandragoras.sort()
	current_sum = sum(mandragoras)
	current_multiplier = 1
	best_score = 0
	for i in range(len(mandragoras)):
		current_score = current_sum * current_multiplier
		if current_score > best_score:
			best_score = current_score
		current_mandragoras = mandragoras[i]
		next_sum = current_sum - current_mandragoras
		next_multiplier = current_multiplier + 1
		current_sum = next_sum
		current_multiplier = next_multiplier
	print(best_score)


for _ in range(int(input())):
	n = int(input())
	m = list(sorted(map(int, input().split())))
	best = sum(m)
	cur = best
	temp = best
	s = 1
	for h in m:
		cur -= s * h
		temp -= h
		cur += temp
		s += 1
		best = max(best, cur)
	print(best)


import sys
test_cases = int(sys.stdin.readline())
for _ in range(test_cases):
	num_mand = int(sys.stdin.readline())
	hp = sorted(list(map(int, sys.stdin.readline().split())))
	sum_hp = sum(hp)
	eat_hp = 1
	local_opt = sum_hp
	for i in hp:
		sum_hp -= i
		eat_hp += 1
		new_local_opt = eat_hp * sum_hp
		if local_opt > new_local_opt:
			break
		else:
			local_opt = new_local_opt
	print(local_opt)


num_tests = int(input())
for each_test in range(num_tests):
	n = int(input())
	healths = [int(i) for i in input().split()]
	healths.sort()
	health_sum = sum(healths)
	eaten = 1
	for health in healths:
		if eaten * health_sum < (eaten + 1) * (health_sum - health):
			eaten += 1
			health_sum -= health
	print(eaten * health_sum)


test_cases = int(input())
for t in range(test_cases):
	n = int(input())
	h = [int(i) for i in input().split()]
	h.sort()
	ans = 0
	p = 0
	for k in range(n)[::-1]:
		p += h[k]
		ans = max(ans, p * (k + 1))
	print(ans)


def optimal(health):
	health.sort()
	S = 1
	total = sum(health)
	max_P = total
	for i in range(len(health)):
		S += 1
		total -= health[i]
		P = S * total
		if P > max_P:
			max_P = P
		elif P < max_P:
			return max_P
	return max_P
num_tests = int(input())
for _ in range(num_tests):
	input()
	health = [int(c) for c in input().split()]
	print(optimal(health))


def fn(a, N, s, h):
	S = [0 for i in range(0, N)]
	i = N - 1
	while i >= 0:
		if i == N - 1:
			S[N - 1] = a[N - 1]
		else:
			S[i] = a[i] + S[i + 1]
		i = i - 1
	for i in range(0, N):
		if i == N - 1:
			h = h + s * a[i]
		elif s * a[i] >= S[i + 1]:
			h = h + s * a[i]
		else:
			s = s + 1
	return h

def main():
	T = int(input())
	for i in range(0, T):
		N = int(input())
		s = input()
		a = []
		for item in s.split(' '):
			a.append(int(item))
		a.sort()
		s = 1
		h = 0
		print(fn(a, N, s, h))
main()


num_tests = int(input())
for test_id in range(num_tests):
	n = int(input())
	health = sorted(list(map(int, input().strip().split(' '))))
	running_sum = sum(health)
	s = 1
	p = 0
	for i in range(n):
		if i != 0:
			running_sum -= health[i - 1]
		s = 1 + i
		p_temp = s * running_sum
		if p_temp - p < 0:
			break
		p = max(p, p_temp)
	print(p)


import sys

def main():
	for i in range(int(sys.stdin.readline())):
		N = int(sys.stdin.readline())
		H = sorted(list(map(int, sys.stdin.readline().split())))
		max_xp = 0
		health_sum = sum(H)
		for i in range(len(H)):
			xp = (i + 1) * health_sum
			if xp > max_xp:
				max_xp = xp
			else:
				break
			health_sum -= H[i]
		print(max_xp)
main()


def max_exp(arr, N):
	(total, exp) = (0, 0)
	for i in range(N):
		total = total - arr[i - 1] if i > 0 else sum(arr)
		temp = (i + 1) * total
		if temp < exp:
			break
		else:
			exp = temp
	return exp
for _ in range(int(input())):
	N = int(input())
	arr = sorted([int(x) for x in input().split()])
	print(max_exp(arr, N))


test_cases = int(input())
for t in range(test_cases):
	n = int(input())
	h = [int(i) for i in input().split()]
	h.sort()
	ans = 0
	p = 0
	for k in range(n)[::-1]:
		p += h[k]
		ans = max(ans, p * (k + 1))
	print(ans)


T = int(input())
for testcase in range(T):
	best = []
	N = input()
	H = sorted(list(map(int, input().split(' '))))
	curSum = 0
	for element in H:
		curSum += element
	S = 1
	for i in H:
		eatCurrent = (S + 1) * (curSum - i)
		battleRest = S * curSum
		if battleRest >= eatCurrent:
			break
		S += 1
		curSum = curSum - i
	print(S * curSum)


t = int(input())
for i in range(0, t):
	n = int(input())
	arr = input().split(' ')
	arr2 = [int(j) for j in arr]
	sum2 = 0
	for j in range(0, n):
		sum2 = sum2 + arr2[j]
	maxi = sum2
	s = 1
	p = 0
	arr2 = sorted(arr2)
	for j in range(0, n):
		s = s + 1
		sum2 = sum2 - arr2[j]
		if sum2 * s > maxi:
			maxi = sum2 * s
	print(maxi)


t = int(input())
for ii in range(t):
	n = int(input())
	l = []
	for x in input().split():
		l.append(int(x))
	l = sorted(l)
	sum = 0
	ans = 0
	for i in range(n - 1, -1, -1):
		sum += l[i]
		if ans > sum * (i + 1):
			break
		else:
			ans = sum * (i + 1)
	print(ans)


out = []
for i in range(int(input())):
	n = int(input())
	arr = sorted([int(i) for i in input().split()])
	(t, s, p) = (sum(arr), 1, 0)
	for i in arr:
		if s * t < (s + 1) * (t - i):
			s += 1
			t -= i
		else:
			out.append(str(s * t))
			break
print('\n'.join(out))


t = int(input())
for _ in range(t):
	n = int(input())
	s = 1
	p = 0
	a = sorted((int(x) for x in input().split()))
	su = sum(a)
	res = a[-1]
	for i in range(n):
		s += 1
		su -= a[i]
		res = max(su * s, res)
	print(res)