Read problems statements in Russian. 

Chef has prepared a feast with N dishes for you. You like Chef's cooking, and so you want to eat all the dishes he has prepared for you. You are also given an array A of size N, where A_{i} represents the happiness you get by eating the i-th dish.You will eat all the dishes in a series of steps. In each step, you pick a non empty subset of the remaining dishes and eat them. The happiness you get from eating these dishes is the size of the subset multiplied by the sum of the individual happiness from the dishes in the subset. You want to maximize the happiness you get from the entire feast, which is the sum of happiness in each step.

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

The first line contains T, the number of test cases.
The first line of each test case contains a single integer N, denoting the number of dishes prepared by the Chef.
The second line of each test case contains contains N space-separated integers: A_{1}, A_{2}, ..., A_{N} denoting the happiness gained by eating the dishes.

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

Output a single number denoting the maximum happiness you can get from the feast.

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

1 ≤ T ≤ 8
1 ≤ N ≤ 10^{5}
-10^{8} ≤ A_{i} ≤ 10^{8}

------ Subtasks ------ 

Subtask #1: A_{i} ≤ 0 (30 points)
Subtask #2: Original Constraints (70 points) 

----- Sample Input 1 ------ 
1
3
-8 0 -2
----- Sample Output 1 ------ 
-10
----- explanation 1 ------ 
Example case 1. You can eat the first dish in the first step,
the second dish in the second step and the third dish in the third step.
total happiness = 1*(-8) + 1*0 + 1*(-2) = -10

----- Sample Input 2 ------ 
1
3
1 2 3
----- Sample Output 2 ------ 
18
----- explanation 2 ------

Difficulty: MEDIUM_HARD
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
def soln(n, a):
	a.sort(reverse=True)
	maxm = 0
	c = 1
	nv = s = 0
	for i in arr:
		s += i
		if s * c > maxm:
			maxm = s * c
			c += 1
		else:
			nv += i
	return maxm + nv
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(soln(n, arr))


for _ in range(int(input())):
	N = int(input())
	A = sorted(list(map(int, input().split())))
	s = 0
	m = 0
	j = 0
	z = 1
	for i in range(N - 1, -1, -1):
		s += A[i]
		if z * s > m:
			m = z * s
			z += 1
		else:
			j += A[i]
	print(m + j)


t = int(input())
for i in range(t):
	n = int(input())
	a = sorted(map(int, input().split()), reverse=True)
	ans = s = c = 0
	for j in range(n):
		s += a[j]
		if s * (j + 1) > ans:
			ans = s * (j + 1)
			c = j + 1
		else:
			break
	print(ans + sum(a[c:]))


def li():
	return list(map(int, input().split()))

def si():
	return input().split()

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

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	a = li()
	a.sort(reverse=1)
	i = s = ans = f = 0
	while i < n:
		s += a[i]
		ans1 = s * (i + 1)
		if ans1 > ans:
			ans = ans1
		else:
			f = 1
			break
		i += 1
	if f == 1:
		print(ans + sum(a[i:]))
	else:
		print(ans)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	sums = 0
	ans = 0
	flag = 0
	for i in range(len(a)):
		sums += a[i]
		ans1 = sums * (i + 1)
		if ans1 > ans:
			ans = ans1
		else:
			flag = 1
			break
	if flag == 1:
		print(ans + sum(a[i:]))
	else:
		print(ans)
	t -= 1


def inl():
	return list(map(int, input().split()))

def solve():
	(pos_sum, neg_sum) = (0, 0)
	(pos_count, neg_count) = (0, 0)
	for ele in lst:
		if ele >= 0:
			pos_sum += ele
			pos_count += 1
		else:
			neg_sum += ele
			neg_count += 1
	if neg_count == 0:
		print(pos_sum * pos_count)
	elif pos_count == 0:
		print(neg_sum)
	elif pos_sum == 0:
		print(neg_sum)
	else:
		s = 0
		not_include_sum = neg_sum
		to_be_include = 0
		not_include = 0
		ans = not_include_sum + (pos_sum + s) * (to_be_include + pos_count)
		for i in range(neg_count - 1, -1, -1):
			ele = lst[i]
			if ele < 0:
				if abs(s) < pos_sum:
					s += ele
					to_be_include += 1
					not_include_sum -= ele
			ans = max(ans, not_include_sum + (pos_sum + s) * (to_be_include + pos_count))
		print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	lst = inl()
	lst.sort()
	solve()


T = int(input())
for _ in range(T):
	n = int(input())
	Happiness = list(map(int, input().split()))
	Happiness.sort()
	Happiness.reverse()
	sum1 = 0
	ans = 0
	found = False
	for i in range(n):
		sum1 += Happiness[i]
		ans1 = sum1 * (i + 1)
		if ans1 > ans:
			ans = ans1
		else:
			found = True
			break
	if found:
		print(ans + sum(Happiness[i:]))
	else:
		print(ans)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

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)) + '\n')

def main():
	for _ in tr():
		n = nl()
		a = ln()
		positives = []
		negatives = []
		for i in a:
			if i < 0:
				negatives.append(i)
			else:
				positives.append(i)
		negatives.sort(reverse=True)
		pos_len = len(positives)
		pos_sum = sum(positives)
		neg_len = len(negatives)
		neg_sum = sum(negatives)
		result = pos_sum * pos_len + neg_sum
		for i in negatives:
			pos_len += 1
			pos_sum += i
			neg_sum -= i
			new_sum = pos_sum * pos_len + neg_sum
			if new_sum < result:
				break
			else:
				result = new_sum
		print(result)
main()


tc = int(input())
for _ in range(tc):
	n = int(input())
	lst = list(map(int, input().split()))
	neg = []
	pos = []
	for elem in lst:
		if elem >= 0:
			pos.append(elem)
		else:
			neg.append(elem)
	pos_sum = sum(pos)
	pos_len = len(pos)
	neg_sum = sum(neg)
	i = 0
	ans = pos_sum * pos_len + neg_sum
	neg.sort(reverse=True)
	for a in neg:
		pos_len += 1
		pos_sum += a
		neg_sum -= a
		hap = pos_sum * pos_len + neg_sum
		if hap < ans:
			break
		else:
			ans = hap
	print(ans)


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	pos = []
	neg = []
	for i in a:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)
	l = len(pos)
	x = sum(pos)
	y = sum(neg)
	ans = l * x + y
	neg = sorted(neg, reverse=True)
	for i in neg:
		l += 1
		x += i
		y -= i
		ans = max(ans, l * x + y)
	print(ans)


def max_happiness(arr):
	pos = []
	neg = []
	for y in arr:
		if y > 0:
			pos.append(y)
		else:
			neg.append(y)
	if len(pos) == len(arr):
		return sum(pos) * len(pos)
	elif len(neg) == len(arr):
		return sum(neg)
	else:
		arr.sort()
		arr.reverse()
		i = 0
		s = arr[i]
		current = arr[i]
		j = 1
		while j < len(arr):
			current += arr[j]
			happiness = current * (j - i + 1)
			if happiness >= s:
				s = happiness
				j += 1
			else:
				return s + sum(arr[j:len(arr)])
		return s
test_cases = int(input())
while test_cases != 0:
	data = input()
	data2 = list(map(int, input().split()))
	print(max_happiness(data2))
	test_cases -= 1


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A = sorted(A)[::-1]
	left = 0
	summ = sum(A)
	right = summ
	ans = -float('inf')
	for i in range(n):
		left += A[i]
		right -= A[i]
		ans = max(ans, (i + 1) * left + right)
	print(ans)


def solve(arr: 'list[int]') -> 'int':
	pos = 0
	pos_size = 0
	neg = 0
	neg_li = []
	for ele in arr:
		if ele >= 0:
			pos += ele
			pos_size += 1
		else:
			neg_li.append(ele)
			neg += ele
	if pos == 0:
		return sum(neg_li)
	elif neg == 0:
		ans = pos * pos_size
		return ans
	neg_li.sort(reverse=True)
	(mx, k, it) = (0, 0, 0)
	for neg_el in neg_li:
		it += neg_el
		k += 1
		val = (pos + it) * (pos_size + k) + (neg - it)
		if val > mx:
			mx = val
	return max(pos * pos_size + it, mx)
for _ in range(int(input())):
	a = int(input())
	x = [int(i) for i in input().strip().split()]
	print(solve(x))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	posSum = 0
	negSum = 0
	no = 0
	neg = []
	for x in a:
		if x <= 0:
			negSum += x
			neg.append(x)
		else:
			posSum += x
			no += 1
	ans = posSum * no + negSum
	neg = sorted(neg, reverse=True)
	for x in neg:
		no += 1
		posSum += x
		negSum -= x
		curr = posSum * no + negSum
		if curr >= 0:
			ans = max(ans, curr)
		else:
			break
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = sorted(list(map(int, input().split())))[::-1]
	ans = -float('inf')
	total = sum(arr)
	left = 0
	right = total
	for i in range(n):
		left += arr[i]
		right -= arr[i]
		ans = max(ans, (i + 1) * left + right)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	pos = []
	neg = []
	for i in arr:
		if i < 0:
			neg.append(i)
		else:
			pos.append(i)
	length = len(pos)
	max_sum = sum(pos) * length + sum(neg)
	if len(neg) > 0:
		pos_sum = sum(pos)
		neg_sum = sum(neg)
		neg = sorted(neg, reverse=True)
		curr_sum = 0
		for i in range(len(neg)):
			if curr_sum >= 0:
				length += 1
				pos_sum = pos_sum + neg[i]
				neg_sum = neg_sum - neg[i]
				curr_sum = pos_sum * length + neg_sum
				max_sum = max(curr_sum, max_sum)
	print(max_sum)


for _ in range(int(input())):
	n = int(input())
	arr = sorted(map(int, input().split()), reverse=True)
	negative_arr = tuple((i for i in arr if i < 0))
	positive_arr = tuple((i for i in arr if i >= 0))
	temp_len = len(positive_arr)
	positive_sum = sum(positive_arr)
	ans = positive_sum * temp_len
	if not negative_arr:
		print(ans)
	elif not positive_arr:
		print(sum(negative_arr))
	else:
		neg = 0
		for i in negative_arr:
			temp_ans = (positive_sum + i) * (temp_len + 1)
			if temp_ans >= ans:
				ans = temp_ans
				positive_sum += i
				temp_len += 1
			else:
				neg += i
		print(ans + neg)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	pos_sum = 0
	pos_cnt = 0
	neg_sum = 0
	neg_li = []
	for i in l:
		if i >= 0:
			pos_sum += i
			pos_cnt += 1
		else:
			neg_sum += i
			neg_li.append(i)
	if len(neg_li) == n or sum((i > 0 for i in l)) == 0:
		print(neg_sum)
	elif pos_cnt == 0:
		print(neg_sum)
	elif pos_cnt == n:
		print(pos_sum * n)
	else:
		neg_li.sort(reverse=True)
		mx = 0
		extra = 0
		extra_sum = 0
		for neg_el in neg_li:
			extra_sum += neg_el
			extra += 1
			curr = (pos_sum + extra_sum) * (pos_cnt + extra) + neg_sum - extra_sum
			if curr > mx:
				mx = curr
		print(max(mx, pos_cnt * pos_cnt + neg_sum))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	pos = 0
	pos_size = 0
	neg = 0
	neg_li = []
	for it in arr:
		if it >= 0:
			pos += it
			pos_size += 1
		else:
			neg_li.append(it)
			neg += it
	if pos == 0:
		print(sum(neg_li))
	elif len(neg_li) == 0:
		ans = pos * pos_size
		print(ans)
	else:
		neg_li.sort(reverse=True)
		(mx, k, it) = (0, 0, 0)
		for neg_el in neg_li:
			it += neg_el
			k += 1
			val = (pos + it) * (pos_size + k) + (neg - it)
			if val > mx:
				mx = val
		print(max(pos * pos_size + it, mx))


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	possum = 0
	negsum = 0
	pos = []
	neg = []
	for j in range(len(a)):
		if a[j] >= 0:
			pos.append(a[j])
			possum += a[j]
		else:
			neg.append(a[j])
			negsum += a[j]
	ans = len(pos) * possum + negsum
	neg.sort(reverse=True)
	poslen = len(pos)
	for i in range(len(neg)):
		possum += neg[i]
		negsum -= neg[i]
		newans = possum * (poslen + 1 + i) + negsum
		if newans > ans:
			ans = newans
		else:
			break
	print(ans)


t = int(input())
while t > 0:
	l = []
	n = int(input())
	l = input().split()
	c = 0
	sump = sumn = 0
	for i in range(n):
		l[i] = int(l[i])
	l.sort()
	s = sum(l)
	i = 0
	max = s * n
	v = []
	s1 = 0
	while i < n:
		s -= l[i]
		s1 += l[i]
		pdt = s * (n - i - 1) + s1
		if pdt > max:
			max = pdt
		else:
			break
		i += 1
	print(max)
	t -= 1


for t in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	total = 0
	pos = []
	neg = []
	for i in a:
		if i >= 0:
			pos.append(i)
		else:
			neg.append(i)
	neg.sort(reverse=True)
	s = sum(pos)
	l = len(pos)
	for i in neg:
		if s + i * (l + 1) >= 0:
			s += i
			l += 1
		else:
			total += i
	total += s * l
	print(total)


T = int(input())
for testCase in range(T):
	N = int(input())
	A = input().split()
	sumNegatives = 0
	sumPositives = 0
	countPositives = 0
	listNegatives = []
	for i in range(N):
		A[i] = int(A[i])
		if A[i] >= 0:
			sumPositives += A[i]
			countPositives += 1
		else:
			sumNegatives += A[i]
			listNegatives.append(A[i])
	listNegatives.sort(reverse=True)
	ans = sumPositives * countPositives + sumNegatives
	posNegatives = 0
	for i in range(N - countPositives):
		sumPositives += listNegatives[i]
		countPositives += 1
		sumNegatives -= listNegatives[i]
		newAns = sumPositives * countPositives + sumNegatives
		if newAns < ans:
			break
		else:
			ans = newAns
	print(ans)


tc = int(input())
for t in range(tc):
	n = int(input())
	happiness = list(map(int, input().strip().split(' ')))
	happiness.sort(reverse=True)
	totalpos = 0
	poslen = 0
	negative_list = []
	i = 0
	while i < n and happiness[i] >= 0:
		totalpos += happiness[i]
		poslen += 1
		i += 1
	if i < n:
		while i < n:
			if (totalpos + happiness[i]) * (poslen + 1) > totalpos * poslen:
				totalpos += happiness[i]
				poslen += 1
			else:
				negative_list.append(happiness[i])
			i += 1
	print(totalpos * poslen + sum(negative_list))


for _ in range(int(input())):
	n = int(input())
	s = sorted(list(map(int, input().split())), reverse=True)
	(negatives, positives) = (s[:], s[:])
	negatives = list((x for x in s if x < 0))
	positives = list((x for x in s if x >= 0))
	nlen = len(negatives)
	plen = len(positives)
	finalSum = sum(positives)
	tn = []
	for item in negatives:
		if (finalSum + item) * (plen + 1) > plen * finalSum:
			finalSum += item
			plen += 1
		else:
			tn.append(item)
	print(sum(tn) + finalSum * plen)


test = int(input())
SUM = [0]
for i in range(1, 100000 + 1):
	SUM.append(0)
while test != 0:
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort()
	for i in range(1, n + 1):
		SUM[i] = ar[i - 1] + SUM[i - 1]
	ans = SUM[n] * n
	for i in range(1, n + 1):
		if ans < SUM[i] + (n - i) * (SUM[n] - SUM[i]):
			ans = SUM[i] + (n - i) * (SUM[n] - SUM[i])
	print(ans)
	test -= 1


for z in range(int(input())):
	N = int(input())
	inputs = list(map(int, input().split()))
	inputs.sort(reverse=True)
	positive = list(filter(lambda x: x >= 0, inputs))
	negative = list(filter(lambda x: x < 0, inputs))
	final_negative_list = []
	total = sum(positive)
	counts = len(positive)
	for item in negative:
		if (total + item) * (counts + 1) > total * counts:
			total += item
			counts += 1
		else:
			final_negative_list.append(item)
	print(total * counts + sum(final_negative_list))


t = int(input())
for i in range(t):
	l = int(input())
	seq = list(map(int, input().split()))
	seq.sort(reverse=True)
	lensubset = 0
	total = 0
	negtotal = 0
	posum = 0
	for j in range(l):
		if seq[j] >= 0:
			posum += seq[j]
			lensubset += 1
		elif posum >= (j + 2) * abs(seq[j]):
			posum += seq[j]
			lensubset += 1
		else:
			negtotal = sum(seq[j:])
			break
	total = posum * lensubset + negtotal
	print(total)


t = int(input())
for _ in range(t):
	(n, sum1, sum2, cnt) = (int(input()), 0, 0, 0)
	arr = [int(i) for i in input().split()]
	arr.sort(reverse=True)
	for i in arr:
		if sum1 * cnt + i <= (sum1 + i) * (cnt + 1):
			(sum1, cnt) = (sum1 + i, cnt + 1)
		else:
			sum2 += i
	print(sum2 + sum1 * cnt)


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	num.sort()
	ans = 0
	s = sum(num)
	for i in range(n):
		if num[i] + (n - 1 - i) * (s - num[i]) > s * (n - i):
			ans += num[i]
			s -= num[i]
		else:
			ans += s * (n - i)
			break
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	x = s = c = 0
	for ai in reversed(a):
		if (s + ai) * (c + 1) > s * c:
			s += ai
			c += 1
		else:
			x += ai
	print(s * c + x)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sumx = 0
	count = 0
	sumd = 0
	l.sort(reverse=True)
	for i in l:
		if (sumx + i) * (count + 1) + sumd >= sumx * count + (sumd + i):
			sumx += i
			count += 1
		else:
			sumd += i
	print(sumx * count + sumd)


times = int(input().strip(' '))
while times > 0:
	n = int(input().strip(' '))
	A = list(map(int, input().strip(' ').split(' ')))
	A.sort()
	B = []
	summ = 0
	length = 0
	for i in A:
		if i < 0:
			B.append(i)
		else:
			summ += i
			length += 1
	product = summ * length
	sub = 0
	B.sort(reverse=True)
	for i in B:
		if product <= (summ + i) * (length + 1):
			summ += i
			length += 1
			product = summ * length
		else:
			sub += i
	product += sub
	print(int(product))
	times -= 1


t = int(input())
while t:
	n = int(input())
	hpns = [int(x) for x in input().split()]
	sumt = sum(hpns)
	po_sum = 0
	count = 0
	neg_sum = 0
	neg_count = 0
	neg_list = []
	for num in hpns:
		if num >= 0:
			po_sum += num
			count += 1
		else:
			neg_sum += num
			neg_list.append(num)
	neg_list.sort(reverse=True)
	ans = neg_sum + count * po_sum
	for i in neg_list:
		neg_count += 1
		if (po_sum + i) * (count + neg_count) + (neg_sum - i) > ans:
			ans = (po_sum + i) * (count + neg_count) + (neg_sum - i)
			po_sum += i
			neg_sum -= i
		else:
			break
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	l = int(input())
	seq = list(map(int, input().split()))
	seq.sort(reverse=True)
	counter = 0
	negsum = 0
	posum = 0
	for j in seq:
		if j >= 0:
			posum += j
			counter += 1
		elif posum >= (counter + 1) * abs(j):
			posum += j
			counter += 1
		else:
			negsum += j
	print(posum * counter + negsum)


t = int(input())
for _ in range(t):
	summ = 0
	count = 0
	sneg = 0
	ncount = 0
	x = int(input())
	f = list(map(int, input().split()))
	for d in f:
		z = d
		if z >= 0:
			summ += z
			count += 1
		else:
			sneg += z
			ncount += 1
	f = sorted(f)
	f = f[::-1]
	p = count
	for y in range(p, x):
		if (summ + f[y]) * (count + 1) >= summ * count:
			count += 1
			summ += f[y]
			sneg -= f[y]
		else:
			break
	print(count * summ + sneg)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	A = input().split()
	A = list(map(int, A))
	A.sort(reverse=True)
	counti = 0
	s = 0
	H = 0
	for i in A:
		if (s + i) * (counti + 1) >= s * counti + i:
			s += i
			counti += 1
			H = s * counti
		else:
			H += i
	print(H)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	p = 0
	l = 0
	res = 0
	ng = []
	for j in range(len(a)):
		if a[j] < 0:
			ng.append(a[j])
		else:
			p += a[j]
			l += 1
	ng.sort()
	for k in ng[::-1]:
		if (p + k) * (l + 1) >= p * l:
			p += k
			l += 1
		else:
			res += k
	print(res + p * l)


T = int(input())
while T > 0:
	dishes = int(input())
	numbers = list(map(int, input().split()))
	happiness = 0
	count = 0
	total = 0
	steps = 0
	numbers.sort(reverse=True)
	for i in numbers:
		if i >= 0:
			count = count + i
			total = total + 1
		elif count + (total + 1) * i > 0:
			count = count + i
			total = total + 1
		else:
			steps = steps + i
	happiness = steps + count * total
	print(happiness)
	T = T - 1


for _ in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	c = 0
	total = 0
	subtotal = 0
	a.sort(reverse=True)
	for i in a:
		if i < 0:
			if subtotal * c > (subtotal + i) * (c + 1):
				total += subtotal * c + i
				subtotal = 0
				c = 0
			else:
				subtotal += i
				c += 1
		else:
			subtotal += i
			c += 1
	total += subtotal * c
	print(total)


for _ in range(int(input())):
	input()
	num = sorted(list(map(int, input().split())))
	s = n = 0
	while num:
		if s + n * num[-1] >= 0:
			n += 1
			s += num.pop()
		else:
			break
	print(s * n + sum(num))


t = int(input())
while t:
	n = int(input())
	li = [int(i) for i in input().strip().split()]
	(res, s, m) = (0, 0, 0)
	neg = []
	for i in li:
		if i < 0:
			neg += [i]
		else:
			s += i
			m += 1
	neg.sort()
	for i in neg[::-1]:
		if (s + i) * (m + 1) >= s * m + i:
			s += i
			m += 1
		else:
			res += i
	res += s * m
	print(res)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	pos = []
	neg = []
	arr = []
	l = input()
	for j in l.split():
		if int(j) < 0:
			neg.append(int(j))
		else:
			pos.append(int(j))
		arr.append(int(j))
	neg.sort(reverse=True)
	a = sum(pos)
	m = len(pos)
	s = a * m
	r = 0
	for q in range(len(neg)):
		if (a + neg[q]) * (m + 1) >= s:
			s = (a + neg[q]) * (m + 1)
			a = a + neg[q]
			m = m + 1
		else:
			r = r + neg[q]
	s = s + r
	print(s)


t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	arr = list(map(int, input().strip().split(' ')))
	arr.sort()
	ans = sum(arr) * n
	sumArray = [0] * (n + 1)
	for i in range(n):
		s = ans - sumArray[i]
		s = s // n
		s -= arr[i]
		s = s * (n - 1 if n > 2 else 1)
		s += arr[i] + sumArray[i]
		sumArray[i + 1] = arr[i] + sumArray[i]
		if s > ans:
			ans = s
			n -= 1
	print(ans)


t = int(input().strip())

def partition(a, p):
	j = -1
	(a[p], a[-1]) = (a[-1], a[p])
	pivot = a[-1]
	for i in range(len(a) - 1):
		if a[i] < pivot or (a[i] == pivot and pivot < 0):
			j += 1
			(a[i], a[j]) = (a[j], a[i])
	(a[j + 1], a[-1]) = (a[-1], a[j + 1])
	return j + 1

def closeToZero(a):
	ctz = 0
	if a[ctz] == 0:
		return ctz
	for i in range(1, len(a)):
		if a[i] == 0:
			ctz = i
			break
		if abs(a[i]) < abs(a[ctz]):
			ctz = i
	return ctz
while t:
	n = int(input().strip())
	a = [int(x) for x in input().split()]
	s = 0
	part = closeToZero(a)
	part = partition(a, part)
	neg = -1
	if a[part] >= 0 and part > 0:
		neg = part - 1
	elif a[part] < 0:
		neg = part
	if neg != -1:
		a[0:neg + 1] = sorted(a[0:neg + 1])
	flag = False
	for i in a:
		if i > 0:
			flag = True
			break
	if flag == False:
		s = sum(a[:neg + 1])
	else:
		ss = sum(a[neg + 1:])
		ll = len(a[neg + 1:])
		dd = sum(a[0:neg + 1])
		best = ll * ss + dd
		while neg >= 0:
			ll += 1
			ss += a[neg]
			dd -= a[neg]
			b = ll * ss + dd
			if b > best:
				best = b
			neg -= 1
		s = best
	print(s)
	t -= 1


for _ in range(int(input())):
	input()
	a = sorted((int(x) for x in input().split()))
	n = s = 0
	while a:
		if s + n * a[-1] >= 0:
			n += 1
			x = a.pop()
			s += x
		else:
			break
	print(s * n + sum(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(list(map(int, input().strip().split())))
	pos = 0
	while pos < n and a[pos] < 0:
		pos += 1
	if pos == n:
		print(sum(a))
		continue
	suma = sum(a[pos:])
	lena = len(a[pos:])
	sumb = sum(a[:pos])
	prev = suma * lena + sumb
	if pos > 0:
		pos -= 1
		sumb -= a[pos]
		lena += 1
		suma += a[pos]
		next = suma * lena + sumb
	else:
		next = prev
	while pos > 0 and next > prev:
		prev = next
		pos -= 1
		sumb -= a[pos]
		lena += 1
		suma += a[pos]
		next = suma * lena + sumb
	print(prev)


t = int(input())
for e in range(t):
	(a, ng, ps, c) = ([], 0, 0, 0)
	(x, y) = ([], [])
	n = int(input())
	a = list(map(int, input().split()))
	for i in a:
		if i >= 0:
			ps += i
			c += 1
			x.append(i)
		else:
			y.append(i)
			ng += i
	ans = ps * c + ng
	if ps == 0:
		print(ans)
		continue
	sumy = 0
	y.sort(reverse=True)
	for i in y:
		c += 1
		ps += i
		ng -= i
		ans = max(ans, ps * c + ng)
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	t -= 1
	list1 = list(map(int, input().split()))
	c = 0
	neglist = []
	maxi = -1
	sum1 = 0
	for x in list1:
		if x >= 0:
			sum1 += x
			c += 1
			maxi = max(maxi, sum1 * c)
		else:
			neglist.append(x)
	ans = maxi
	if maxi < 0:
		maxi = 0
	neglist.sort()
	neglist.reverse()
	for x in neglist:
		sum1 += x
		tot = sum1 * (c + 1)
		if maxi < max(tot, maxi):
			c += 1
			maxi = max(tot, maxi)
		else:
			maxi += x
	print(maxi)


from itertools import repeat
for _ in repeat(None, int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort(reverse=True)
	count = 0
	positive = 0
	negative = 0
	for i in a:
		if i >= 0:
			count += 1
			positive += i
		elif (count + 1) * (positive + i) > count * positive + i:
			count += 1
			positive += i
		else:
			negative += i
	print(count * positive + negative)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = sorted(arr, reverse=True)
	sump = 0
	sumn = 0
	dell = 0
	cntn = 0
	cntp = 0
	neg = -1
	for j in range(n):
		if arr[j] >= 0:
			sump += arr[j]
			cntp += 1
		else:
			sumn = sumn + arr[j]
			if neg == -1:
				neg = j
	cntn = n - cntp
	mulp = cntp * sump
	muln = sumn
	maxmul = mulp
	ans = 0
	if neg != -1:
		for j in range(neg, n):
			if mulp < (cntp + 1) * (sump + arr[j]):
				sump += arr[j]
				cntp += 1
				sumn -= arr[j]
				mulp = cntp * sump
			else:
				ans = mulp + sumn
	else:
		ans = cntp * sump
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	result = 0
	if a[0] <= 0:
		result = sum(a)
	else:
		current_max = 0
		_sum = 0
		i = 0
		for x in a:
			i += 1
			_sum += x
			if current_max > _sum * i:
				result = current_max + sum(a[i - 1:])
				break
			current_max = _sum * i
		else:
			result = current_max
	print(result)


T = eval(input())
for i in range(T):
	X = eval(input())
	c = 0
	sum1 = 0
	A = list(map(eval, input().split()))
	A.sort()
	j = X - 1
	while j >= 0:
		if (sum1 + A[j]) * (c + 1) >= sum1 * c:
			sum1 = sum1 + A[j]
			j = j - 1
			c = c + 1
		else:
			break
	sum1 = sum1 * c
	while j >= 0:
		sum1 = sum1 + A[j]
		j = j - 1
	print(sum1)


t = int(input())
while t > 0:
	t1 = int(input())
	numbers = list(map(int, input().split()))
	sum = 0
	plusnum = 0
	tot = 0
	nsum = 0
	numbers.sort(reverse=True)
	for n in numbers:
		if n >= 0:
			plusnum = plusnum + n
			tot = tot + 1
		elif plusnum + (tot + 1) * n > 0:
			plusnum = plusnum + n
			tot = tot + 1
		else:
			nsum = nsum + n
	sum = nsum + plusnum * tot
	print(sum)
	t = t - 1


T = int(input())
for case in range(T):
	N = int(input())
	A = [int(ai) for ai in input().split()]
	npos = 0
	pos = 0
	nA = []
	for ai in A:
		if ai >= 0:
			pos = pos + ai
			npos += 1
		else:
			nA.append(-ai)
	nA.sort()
	if npos == 0:
		hap = -sum(nA)
	else:
		i = 0
		while i < len(nA):
			if nA[i] < pos / npos:
				pos = pos - nA[i]
				npos += 1
				i += 1
			else:
				break
		hap = pos * npos - sum(nA[i:])
	print(hap)


import math

def findjustsmall(val, arr):
	low = 0
	high = len(arr)
	mid = 0
	while low <= high:
		mid = int((high + low) / 2)
		if arr[mid] < val:
			if low == high - 1:
				return mid
			low = mid
		else:
			if low == high - 1:
				break
			high = mid
	return -1

def findjustgreat(val, arr):
	low = 0
	high = len(arr) - 1
	mid = 0
	while low <= high:
		mid = int((high + low) / 2)
		if arr[mid] >= val:
			if low == high:
				return mid
			high = mid
		elif low == high - 1:
			low = high
		elif low == high:
			break
		else:
			low = mid
	return -1
t = int(input())
for T in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	neglast = findjustsmall(0, a)
	posfirst = findjustgreat(0, a)
	tpos = 0
	tneg = 0
	for x in a:
		if x >= 0:
			tpos += x
		else:
			tneg += x
	if posfirst == len(a) - 1:
		print(tneg)
	else:
		cursum = tpos
		curn = n - posfirst
		j = neglast
		x = a[j]
		while cursum > abs(curn * x) and j >= 0:
			cursum += x
			tneg = tneg - x
			curn += 1
			j = j - 1
			if j >= 0:
				x = a[j]
		ans = cursum * curn + tneg
		print(ans)


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	arr = []
	neg = []
	pos = []
	ans = 0
	copy = 0
	arr = [int(x) for x in input().split(' ')]
	for i in range(n):
		if arr[i] < 0:
			neg.append(arr[i])
		else:
			pos.append(arr[i])
	copy = ans = sum(pos)
	n_terms = len(pos)
	ans *= n_terms
	neg.sort(reverse=True)
	if n_terms == 0:
		ans = sum(neg)
	else:
		for i in range(len(neg)):
			if (copy + neg[i]) * (n_terms + 1) >= ans:
				n_terms = n_terms + 1
				copy = copy + neg[i]
				ans = copy * n_terms
			else:
				break
		for j in range(i, len(neg)):
			ans += neg[j]
	print(ans)


for _ in range(int(input())):
	size = int(input())
	dishes = sorted(list(map(int, input().split())))[::-1]
	(positivessum, negativessum) = (0, 0)
	(positives, negatives) = (list(), list())
	for i in range(size):
		if dishes[i] >= 0:
			positives.append(dishes[i])
			positivessum += dishes[i]
		else:
			negatives.append(dishes[i])
			negativessum += dishes[i]
	(lenp, lenn) = (len(positives), len(negatives))
	index = 0
	posans = lenp * positivessum
	negans = negativessum
	count = lenp
	flag = 0
	for i in range(lenn):
		subans = (negatives[i] + positivessum) * (count + 1)
		if subans > posans:
			posans = subans
			positivessum += negatives[i]
			count += 1
			index = i
		elif count == lenp:
			flag = 1
			break
		else:
			break
	if flag == 0:
		print(posans + sum(negatives[index + 1:]))
	else:
		print(posans + negativessum)


varTest = int(input('\n'))
for j in range(0, varTest):
	arraylength = int(input('\n'))
	array = list(map(int, input().split()))
	array.sort(key=None, reverse=False)
	length = int(len(array))
	sum = int(0)
	startingindex = int(-1)
	for i in range(0, length, 1):
		if int(array[i]) >= 0:
			if startingindex == int(-1):
				startingindex = int(i)
			sum = sum + int(array[i])
	answer = int(0)
	if startingindex != int(-1):
		leng = int(length - startingindex)
		answer = int(sum * leng)
	sum2 = answer
	if startingindex != int(0):
		if startingindex == -1:
			for i in range(0, arraylength):
				answer = answer + int(array[i])
		else:
			j = startingindex
			for i in range(1, startingindex + 1, 1):
				if sum2 >= answer:
					answer = sum2
					sum = sum + array[startingindex - i]
					sum2 = sum
					sum2 = sum2 * (length - startingindex + i)
					j = startingindex - i
			for i in range(0, j + 1):
				answer = answer + int(array[i])
	print(answer, end='\n')


n = int(input().strip())
for a0 in range(n):
	num = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	a = sorted(a)
	a = a[::-1]
	sec = []
	s = 0
	c = 0
	sep = 0
	for x in a:
		if x >= 0:
			s = s + x
			c = c + 1
		else:
			sec.append(x)
	for y in sec:
		if (s + y) * (c + 1) >= s * c:
			s = s + y
			c = c + 1
		else:
			sep = sep + y
	print(s * c + sep)


t = int(input())
for y in range(t):
	n = int(input())
	k = list(input().split())
	k = [int(X) for X in k]
	k.sort()
	r = 0
	s = 0
	for i in range(n):
		if k[i] < 0:
			e = i
			s = s + k[i]
		else:
			r = r + k[i]
	if r == 0:
		print(s)
	elif s == 0:
		print(r * n)
	else:
		re = r * (n - 1 - e) + s
		k.reverse()
		d = r
		h = n - e
		for j in range(n - 1 - e, n):
			d = d + k[j]
			s = s + -1 * k[j]
			g = d * h + s
			h = h + 1
			if re < g:
				re = g
		print(re)


import itertools
T = int(input())
for case in range(T):
	n = int(input())
	xs = list(map(int, input().split()))
	xs.sort()
	sl = list(itertools.accumulate(xs))
	ans = sum(xs) * len(xs)
	s = sum(xs)
	for (i, x) in enumerate(xs):
		ans = max(ans, sl[i] + (s - sl[i]) * (n - i - 1))
	print(ans)


tc = int(input())
while tc:
	n = int(input())
	no = list(map(int, input().split()))
	neg = []
	pos = []
	ncnt = 0
	pcnt = 0
	psum = 0
	nsum = 0
	for x in range(n):
		temp = no[x]
		if temp < 0:
			neg.append(temp)
			ncnt = ncnt + 1
			nsum = nsum + temp
		else:
			pos.append(temp)
			pcnt = pcnt + 1
			psum = psum + temp
	neg = sorted(neg, reverse=True)
	ans = nsum + psum * pcnt
	for x in range(ncnt):
		nsum = nsum - neg[x]
		ncnt = ncnt - 1
		pcnt = pcnt + 1
		psum = psum + neg[x]
		tans = nsum + psum * pcnt
		if tans > ans:
			ans = tans
		else:
			break
	print(ans)
	tc = tc - 1


def binary_search(arr, start, end, key):
	if start > end:
		return -1
	mid = (start + end) // 2
	if arr[mid] == key:
		return mid
	if arr[mid] > key:
		return binary_search(arr, start, mid - 1, key)
	else:
		return binary_search(arr, mid + 1, end, key)
t = int(input())
for i in range(t):
	n = int(input())
	arr = input()
	arr = arr.split()
	minpos = 10 ** 9
	for i in range(len(arr)):
		arr[i] = int(arr[i])
		if arr[i] > 0 and minpos > arr[i]:
			minpos = arr[i]
	arr = sorted(arr)
	index = binary_search(arr, 0, n - 1, minpos)
	start = 0
	if index == -1:
		start = n - 1
	else:
		start = index - 1
	sumpos = 0
	for i in range(start + 1, n):
		sumpos += arr[i]
	npos = n - 1 - start
	tmp = start
	sumneg = 0
	nneg = 0
	cumarr = [arr[0]]
	for j in range(1, tmp + 1):
		cumarr.append(cumarr[j - 1] + arr[j])
	maxhappiness = 0
	if tmp >= 0:
		maxhappiness = npos * sumpos + cumarr[tmp]
	else:
		maxhappiness = npos * sumpos
	for j in range(tmp, -1, -1):
		sumneg = 0
		restsum = 0
		if j == 0:
			sumneg = cumarr[start]
			restsum = 0
		else:
			sumneg = cumarr[start] - cumarr[j - 1]
			restsum = cumarr[j - 1]
		nneg = start - j + 1
		if (npos + nneg) * (sumpos + sumneg) + restsum > maxhappiness:
			maxhappiness = (npos + nneg) * (sumpos + sumneg) + restsum
	print(maxhappiness)


t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a, reverse=True)
	ans = 0
	curr_sum = 0
	for i in range(n):
		curr_sum += a[i]
		if curr_sum * (i + 1) > ans:
			ans = curr_sum * (i + 1)
		else:
			ans += a[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	A = input().split(' ')
	A = [int(a) for a in A]
	A.sort()
	i = 0
	flag = False
	while i < n:
		if A[i] < 0:
			i += 1
		else:
			flag = True
			break
	neg = A[:i][::-1]
	pos = A[i:][::-1]
	comb = []
	out = []
	minLen = min(len(pos), len(neg))
	currSum = sum(pos)
	for i in range(len(neg)):
		withNeg = (currSum + neg[i]) * (len(pos) + 1)
		if withNeg > currSum * len(pos):
			pos.append(neg[i])
			currSum += neg[i]
		else:
			out.append(neg[i])
	res = sum(pos) * len(pos) + sum(out)
	print(str(res))


t = int(input())
for test in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	ans = 0
	A.sort(reverse=True)
	sumA = [0]
	revSumA = [0]
	index = 0
	for j in A:
		sumA.append(j + sumA[index])
		index += 1
	index = 0
	for j in range(n - 1, -1, -1):
		revSumA.append(A[j] + revSumA[index])
		index += 1
	ans = sum(A)
	for i in range(2, n + 1):
		tmp = sumA[i] * i + revSumA[n - i]
		if tmp > ans:
			ans = tmp
		else:
			break
	print(ans)


import sys

def set_input():
	t = int(input())
	inp = []
	sum = []
	for i in range(t):
		n = int(input())
		inp = list(map(int, input().split()))
		sum.append(solve(n, inp))
	for i in sum:
		print(i)

def solve(n, inp):
	neg_sum = 0
	pos_sum = 0
	neg = []
	pos = []
	for i in inp:
		if i < 0:
			neg.append(i)
		elif i >= 0:
			pos.append(i)
	len_pos = len(pos)
	pos_sum = sum(pos)
	neg_sum = sum(neg)
	sorted1 = sorted(neg, reverse=True)
	old_sum = len_pos * pos_sum + neg_sum
	count = 0
	sum1 = 0
	if inp.count(0) + len(neg) == len(inp) or len(neg) == len(inp):
		return neg_sum
	elif len_pos == len(inp):
		return len_pos * pos_sum
	else:
		for i in sorted1:
			count += 1
			new_sum = sum1
			sum1 = (len_pos + count) * (pos_sum + i) + (neg_sum - i)
			if sum1 > new_sum:
				neg_sum = neg_sum - i
				pos_sum = pos_sum + i
			else:
				break
		return max(len_pos * pos_sum + neg_sum, new_sum)
set_input()


t = int(input())
for i in range(t):
	n = int(input())
	array = list(map(int, input().rstrip().split(' ')))
	array.sort()
	cum_sum = [array[0]]
	for j in range(1, n):
		cum_sum.append(cum_sum[j - 1] + array[j])
	total_sum = cum_sum[n - 1]
	prev_sum = total_sum * n
	printed = False
	for j in range(n):
		new_sum = (total_sum - cum_sum[j]) * (n - (j + 1)) + cum_sum[j]
		if new_sum < prev_sum:
			print(prev_sum)
			printed = True
			break
		else:
			prev_sum = new_sum
	if not printed:
		print(new_sum)


from sys import stdin
t = int(stdin.readline())
while t:
	n = int(stdin.readline())
	l = list(map(int, stdin.readline().split()))
	ans = 0
	s = 0
	count = 0
	l.sort(reverse=True)
	temp = 0
	for i in range(0, len(l)):
		if (s + l[i]) * (count + 1) >= temp:
			count += 1
			s += l[i]
			temp = s * count
		else:
			ans += l[i]
	print(s * count + ans)
	t -= 1


t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = input().split()
	a = [int(x) for x in a]
	count_negative = sum((x < 0 for x in a))
	count_only_neg = sum((x <= 0 for x in a))
	if count_only_neg == n:
		print(sum(a))
	elif count_negative == 0:
		print(n * sum(a))
	elif count_negative == n:
		print(sum(a))
	else:
		count_positive = n - count_negative
		positive_list = [i for i in a if i > 0]
		negative_list = [i for i in a if i < 0]
		sum_positive = sum(positive_list)
		sum_negative = sum(negative_list)
		first_sum = sum_negative + sum_positive * count_positive
		second_sum = n * sum(a)
		negative_list.sort(reverse=True)
		counts = 0
		new_sum = 0
		pre_sum = sum_positive
		pre_neg = sum_negative
		for i in negative_list:
			counts = counts + 1
			old_sum = new_sum
			new_sum = (pre_sum + i) * (count_positive + counts) + (pre_neg - i)
			pre_sum = pre_sum + i
			pre_neg = pre_neg - i
			if old_sum > new_sum:
				break
		print(max(first_sum, second_sum, old_sum))


for t in range(int(input())):
	n = int(input())
	x = list(map(int, input().split(' ')))
	x.sort(reverse=True)
	s = x[0]
	mul = 1
	res = 0
	for i in range(1, len(x)):
		prev = s * mul
		s += x[i]
		mul += 1
		if s * mul < prev and s * mul < prev + x[i]:
			res += prev
			s = x[i]
			mul = 1
	res += s * mul
	print(res)


for ti in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	m.sort(reverse=True)
	r = 0
	s = m[0]
	c = 1
	for i in range(1, n):
		if (s + m[i]) * (c + 1) >= s * c + m[i]:
			s = s + m[i]
			c = c + 1
		else:
			r = r + s * c
			s = m[i]
			c = 1
	r = r + s * c
	print(r)


from sys import setrecursionlimit, exit, stdin
from math import ceil, floor, acos, pi, factorial
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from collections import Counter
import itertools
setrecursionlimit(10 ** 7)
RI = lambda x=' ': list(map(int, input().split(x)))
RS = lambda x=' ': input().rstrip().split(x)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
mod = int(1000000000.0 + 7)
eps = 1e-06
MAX = 10 ** 5 + 10
T = RI()[0]
for _ in range(T):
	N = RI()[0]
	A = RI()
	ans = 0
	(i, s, c) = (0, 0, 0)
	A.sort(reverse=True)
	while i < N and (s + A[i]) * (c + 1) > s * c:
		s += A[i]
		c += 1
		i += 1
	ans = s * c
	while i < N:
		ans += A[i]
		i += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	count = 0
	negatives = []
	for x in arr:
		if x >= 0:
			count += 1
			ans += x
		else:
			negatives.append(x)
	if len(negatives) == 0:
		print(ans * count)
		continue
	negatives.sort()
	temp = sum(negatives)
	res = ans * count + temp
	z = ans
	for j in range(len(negatives) - 1, 0, -1):
		z += negatives[j]
		count += 1
		temp -= negatives[j]
		res = max(res, z * count + temp)
	print(res)


for i in range(int(input())):
	amd = int(input())
	array = list(map(int, input().split()))
	array.sort()
	mke = len(array) - 1
	for k in range(len(array)):
		if array[k] >= 0:
			mke = k
			break
	total = sum(array) * len(array)
	sum1 = sum(array)
	r = len(array)
	rmd = 0
	for j in range(mke):
		sum1 = sum1 - array[j]
		r -= 1
		rmd += array[j]
		newsum = sum1 * r + rmd
		if total > newsum:
			break
		else:
			total = newsum
	print(total)


__author__ = ['vjn4006(Vaibhav Nagda)']

def main():
	t = int(input().strip())
	for _ in range(t):
		n = int(input().strip())
		s = sorted(list(map(int, input().strip().split(' '))))
		grt_cnt = 0
		grt_sum = 0
		happiness = 0
		smaller = []
		for i in s:
			if i >= 0:
				grt_cnt += 1
				grt_sum += i
			else:
				smaller.append(i)
		happiness = grt_sum * grt_cnt
		smaller = sorted(smaller)
		smaller = list(reversed(smaller))
		start = 0
		grt_cnt += 1
		for i in range(len(smaller)):
			if grt_cnt * (grt_sum + smaller[i]) >= happiness:
				grt_sum += smaller[i]
				happiness = grt_sum * grt_cnt
				grt_cnt += 1
			else:
				start = i
				break
		for i in range(start, len(smaller)):
			happiness += smaller[i]
		print(happiness)
	return
main()


for _ in range(int(input())):
	input()
	happiness_array = list(map(int, input().split()))
	displeasurables = sorted(filter(lambda x: x < 0, happiness_array), reverse=True)
	pleasurables = [x for x in happiness_array if x >= 0]
	sum_displeasure = sum(displeasurables)
	sum_pleasure = sum(pleasurables)
	len_pleasure = len(pleasurables)
	max_pleasure = sum_pleasure * len_pleasure + sum_displeasure
	for item in displeasurables:
		len_pleasure += 1
		sum_pleasure += item
		sum_displeasure -= item
		temp = sum_pleasure * len_pleasure + sum_displeasure
		if temp > max_pleasure:
			max_pleasure = temp
		else:
			break
	print(max_pleasure)


for _ in range(int(input())):
	n = int(input())
	(*a,) = map(int, input().split())
	c = [i for i in a if i >= 0]
	d = [i for i in a if i < 0]
	s = sum(c)
	l = len(c)
	ans = s * l + sum(d)
	for i in reversed(sorted(d)):
		if i * l + s > 0:
			ans += i * l + s
			s += i
			l += 1
	print(ans)


numTests = int(input())
for test in range(numTests):
	numDishes = int(input())
	happy = map(int, input().split())
	sumPos = 0
	countPos = 0
	negNums = []
	for h in happy:
		if h > -1:
			sumPos += h
			countPos += 1
		else:
			negNums.append(-h)
	negNums.sort()
	done = negNums == []
	while not done:
		done = negNums[0] * (countPos + 1) > sumPos
		if not done:
			sumPos -= negNums.pop(0)
			countPos += 1
			done = negNums == []
	print(int(sumPos * countPos - sum(negNums)))


T = int(input())
for i in range(T):
	N = int(input())
	A = input().split(' ')
	for i in range(N):
		A[i] = int(A[i])
	A.sort()
	result1 = 0
	result2 = 0
	pos = N - 1
	for i in range(N):
		if A[i] >= 0:
			pos = i - 1
			break
	result1 = sum(A[:pos + 1])
	factor2 = N - pos - 1
	sum2 = sum(A[pos + 1:])
	result2 = factor2 * sum2
	result = result1 + result2
	if sum2 - abs(A[pos]) <= abs(A[pos]) * (N - pos - 1):
		print(result)
		continue
	else:
		while sum2 - abs(A[pos]) > abs(A[pos]) * (N - pos - 1):
			sum2 -= abs(A[pos])
			pos -= 1
		result1 = sum(A[:pos + 1])
		result2 = (N - pos - 1) * sum2
	result = result1 + result2
	print(result)


count = int(input())
for step in range(count):
	size = int(input())
	dishes = [int(x) for x in input().split()]
	dishes.sort(reverse=True)
	happiness = 0
	counter = 0
	negative = 0
	top = 0
	for mrinal in dishes:
		if top <= (happiness + mrinal) * (counter + 1):
			top = (happiness + mrinal) * (counter + 1)
			happiness += mrinal
			counter += 1
		else:
			negative += mrinal
	happiness *= counter
	happiness += negative
	print(happiness)


import array
t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split(' ')]
	l.sort()
	if l[0] >= 0:
		print(sum(l) * len(l))
	elif l[len(l) - 1] <= 0:
		print(sum(l))
	else:
		l_1 = l
		l_2 = l
		l11 = filter(lambda x: x >= 0, l_1)
		l2 = filter(lambda x: x < 0, l_2)
		l2 = list(tuple(l2))
		l11 = list(tuple(l11))
		l2.sort()
		sum1 = sum(l11)
		l1 = len(l11)
		sum2 = sum1 * l1
		prev = sum2
		k = 1
		length = len(l2) - 1
		while length >= 0:
			sum1 = sum1 + l2[length]
			l22 = l1 + k
			sum2 = sum1 * l22
			if prev >= sum2:
				sum2 = prev
				break
			prev = sum2
			k += 1
			length -= 1
		print(sum2 + sum(l2[0:length + 1]))
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	a.extend(map(int, input().split()))
	a.sort(reverse=True)
	c = 0
	s = a[0]
	while (s + a[c + 1]) * (c + 2) >= s * (c + 1):
		s += a[c + 1]
		c += 1
		if c >= n - 1:
			break
	s *= c + 1
	for i in range(c + 1, n):
		s += a[i]
	print(s)


test = int(input())
for t in range(test):
	n = int(input())
	count = 0
	res = 0
	exclude = 0
	for number in sorted(map(int, input().split()))[::-1]:
		including_cur = (res + number) * (count + 1)
		excluding_cur = res * count + number
		if including_cur >= excluding_cur:
			res += number
			count += 1
		else:
			exclude += number
	print(res * count + exclude)


cases = int(input())
for case_i in range(cases):
	n = int(input())
	arr = [int(k) for k in input().split(' ')]
	arr.sort(reverse=True)
	pos_sum = 0
	pos_total = 0
	total_sum = 0
	i = 0
	while i < n and (arr[i] >= 0 or (pos_sum + arr[i]) * (pos_total + 1) >= pos_sum * i):
		pos_sum += arr[i]
		pos_total += 1
		i += 1
	print(pos_sum * pos_total + sum(arr[i:]))


T = int(input())
i = 0
while i < T:
	N = int(input())
	negs = []
	sump = 0
	ns = input().split()
	for e in ns:
		e = int(e)
		if e < 0:
			negs.append(e)
		else:
			sump += e
	negs.sort(reverse=True)
	nump = N - len(negs)
	j = 0
	for e in negs:
		contn = -(nump + 1) * e
		diff = sump
		if contn <= sump:
			sump += e
			nump += 1
			j += 1
		else:
			break
	sump = sump * nump
	negs = negs[j:]
	for e in negs:
		sump += e
	print(sump)
	i += 1