The Little Elephant from the Zoo of Lviv likes listening to music.
There are N songs, numbered from 1 to N, in his MP3-player. The song i is described by a pair of integers B_{i} and L_{i} - the band (represented as integer) that performed that song and the length of that song in seconds. The Little Elephant is going to listen all the songs exactly once in some order.
The sweetness of the song is equal to the product of the length of that song and the number of different bands listened before (including the current playing song).
Help the Little Elephant to find the order that maximizes the total sweetness of all N songs. Print that sweetness.

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

The first line of the input contains single integer T, denoting the number of test cases. Then T test cases follow. The first line of each test case contains single integer N, denoting the number of the songs. The next N lines describe the songs in the MP3-player. The i-th line contains two space-sparated integers B_{i} and L_{i}.

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

For each test, output the maximum total sweetness.

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

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 100000 (10^{5})$
$1 ≤ B_{i}, L_{i} ≤ 1000000000 (10^{9})$

----- Sample Input 1 ------ 
2
3
1 2
2 2
3 2
3
2 3
1 2
2 4
----- Sample Output 1 ------ 
12
16
----- explanation 1 ------ 
In the first sample: if he listens the songs in given order, thenB1=1, L1=2: the sweetness = 2 * 1 = 2B2=2, L2=2: the sweetness = 2 * 2 = 4B3=3, L3=2: the sweetness = 2 * 3 = 6So the total sweetness is 12. In this case, you can check the total sweetness does not depend on the order of the songs.
In the second sample: if he listens the songs in given order, thenB1=2, L1=3: the sweetness = 3 * 1 = 3B2=1, L2=2: the sweetness = 2 * 2 = 4B3=2, L3=4: the sweetness = 4 * 2 = 8So the total sweetness is 15. However, he listens the song 2 firstly, thenB2=1, L2=2: the sweetness = 2 * 1 = 2B1=2, L1=3: the sweetness = 3 * 2 = 6B3=2, L3=4: the sweetness = 4 * 2 = 8So the total sweetness is 16, and it is the maximum total sweetness.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms


Solutions:
t = int(input())
for _ in range(t):
	songs = []
	n = int(input())
	for _ in range(n):
		(b, l) = map(int, input().split())
		songs.append((b, l))
	songs.sort()
	total = 0
	js = []
	for i in range(n):
		if i == 0 or songs[i - 1][0] < songs[i][0]:
			js.append(songs[i][1])
		else:
			total = total + songs[i][1]
	js.sort()
	ans = 0
	for i in range(1, len(js) + 1):
		ans += i * js[i - 1]
	ans += len(js) * total
	print(ans)


for _ in range(int(input())):
	l = []
	from collections import defaultdict
	n = int(input())
	id = []
	min = {}
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append([a, b])
		if min.get(a, -1) == -1:
			min[a] = b
		elif b < min[a]:
			min[a] = b
	li = [min[a] for a in min]
	li.sort()
	dist = len(li)
	sm = 0
	seen = defaultdict(int)
	l.sort(key=lambda x: x[1])
	for i in range(len(li)):
		sm += li[i] * (i + 1)
	for i in range(n):
		id = l[i][0]
		length = l[i][1]
		if seen[id] == 0:
			seen[id] = 1
		else:
			sm += length * dist
	print(sm)


for _ in range(int(input())):
	n = int(input())
	band = {}
	for i in range(n):
		(b, l) = map(int, input().split())
		if b in band:
			band[b].append(l)
		else:
			band[b] = [l]
	out = 0
	arr = []
	k = len(band)
	for i in band:
		band[i].sort()
		arr.append(band[i].pop(0))
	arr.sort()
	for i in range(k):
		out += (i + 1) * arr[i]
	for i in band:
		for j in band[i]:
			out += k * j
	print(out)


a = int(input())
for _ in range(a):
	aa = int(input())
	kk = []
	table = {}
	for i in range(aa):
		bb = list(map(int, input().split()))
		kk.append((bb[0], bb[1]))
	kk = sorted(kk, key=lambda x: x[1])
	count = 0
	l = 0
	j = 0
	for i in kk:
		if i[0] not in table:
			l += 1
			table[i[0]] = 1
			count += l * i[1]
		else:
			j += i[1]
	print(count + l * j)


for _ in range(int(input())):
	n = int(input())
	l = [0] * n
	b = [0] * n
	q = []
	for i in range(n):
		q.append(list(map(int, input().split())))
	q = sorted(q, key=lambda x: x[1])
	prod = 0
	count = 0
	dict = {}
	t = 0
	for i in q:
		if i[0] not in dict.keys():
			dict[i[0]] = 1
			count += 1
			prod += count * i[1]
		else:
			t += i[1]
	prod += t * count
	print(prod)


for _ in range(int(input())):
	ls = []
	s = set()
	ans = 0
	temp = []
	cnt = 0
	for i in range(int(input())):
		(b, l) = list(map(int, input().split()))
		ls.append([l, b])
	ls.sort()
	for i in range(len(ls)):
		if ls[i][1] not in s:
			s.add(ls[i][1])
			cnt += 1
			ans += cnt * ls[i][0]
		else:
			temp.append(ls[i][0])
	for i in range(len(temp)):
		ans += cnt * temp[i]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for i in range(n):
		(b, l) = [int(x) for x in input().strip().split()]
		arr.append((b, l))
	arr = sorted(arr, key=lambda x: x[1])
	band = {}
	for i in range(n):
		band[arr[i][0]] = 0
	k = 0
	uniqueval = 0
	repeatedval = 0
	for i in range(n):
		if band[arr[i][0]] == 0:
			k += 1
			band[arr[i][0]] = 1
			uniqueval += arr[i][1] * k
		else:
			repeatedval += arr[i][1]
	print(uniqueval + repeatedval * k)


from sys import stdin
t = int(stdin.readline())
for i in range(t):
	n = int(stdin.readline())
	count = 0
	uniq = set()
	final = []
	sum1 = 0
	list1 = []
	for j in range(n):
		(b, l) = list(map(int, stdin.readline().split()))
		list1.append((b, l))
	list1.sort(key=lambda x: x[1])
	for j in range(n):
		if list1[j][0] not in uniq:
			count += 1
			uniq.add(list1[j][0])
			sum1 += count * list1[j][1]
		else:
			final.append(list1[j][1])
	len1 = len(uniq)
	print(sum1 + len1 * sum(final))


for _ in range(int(input())):
	a = int(input())
	yu = []
	pussy = set()
	count = 0
	ans = 0
	temp = 0
	for _ in range(a):
		yu.append(list(map(int, input().split())))
	ty = sorted(yu, key=lambda x: x[1])
	for i in ty:
		if i[0] not in pussy:
			pussy.add(i[0])
			count += 1
			ans += count * i[1]
		else:
			temp += i[1]
	ans += temp * count
	print(ans)


t = int(input())
from itertools import permutations as p
for _ in range(t):
	n = int(input())
	l1 = []
	l2 = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l1.append([b, a])
		l2.append([a, b])
	d = {}
	for i in l1:
		try:
			d[i[0]].append(i[1])
		except:
			d[i[0]] = [i[1]]
	x = list(d.keys())
	x.sort()
	ans = 0
	e = {}
	f = 0
	for i in x:
		for j in d[i]:
			try:
				m = e[j]
				f += i
			except:
				e[j] = 0
				ans += len(e) * i
	ans += f * len(e)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	songs = []
	counted = {}
	bands_done = 0
	for _ in range(n):
		songs.append(tuple(map(int, input().split())))
	songs.sort(key=lambda x: x[1])
	ans = 0
	left_length = 0
	while len(songs) > 0:
		current = songs.pop(0)
		if current[0] not in counted:
			counted[current[0]] = 1
			bands_done += 1
			ans += bands_done * current[1]
		else:
			left_length += current[1]
	ans += bands_done * left_length
	print(ans)


def maxBandLength(bands, n):
	bands.sort(key=lambda x: x[1])
	list2 = []
	len_set = set()
	count = 0
	for item in bands:
		if item[0] not in len_set:
			len_set.add(item[0])
			count += len(len_set) * item[1]
		else:
			list2.append(item[1])
	for length in list2:
		count += length * len(len_set)
	return count
t = int(input())
for i in range(t):
	bands = []
	n = int(input())
	for j in range(n):
		bands.append(tuple(map(int, input().split())))
	print(maxBandLength(bands, n))


t = int(input())
while t:
	songs = []
	res = 0
	n = int(input())
	unique_bands = {}
	for _ in range(n):
		b_l = [int(i) for i in input().split()]
		songs.append({'band': b_l[0], 'length': b_l[1], 'visited': 0})
	songs = sorted(songs, key=lambda k: k['length'])
	for song in range(len(songs)):
		if songs[song]['band'] not in unique_bands.keys() and (not songs[song]['visited']):
			unique_bands[songs[song]['band']] = songs[song]['length']
			i = len(unique_bands)
			res += songs[song]['length'] * i
			songs[song]['visited'] = 1
	for song in range(len(songs)):
		if not songs[song]['visited']:
			res += songs[song]['length'] * i
	print(res)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(bi, li) = map(int, input().split())
		l.append((bi, li))
	l.sort()
	d = dict()
	co = 0
	cb = 0
	ms = []
	for (i, j) in l:
		try:
			d[i]
			co += j
		except KeyError:
			d[i] = 1
			cb += 1
			ms.append(j)
	ms.sort()
	co *= cb
	for i in range(cb):
		co += (i + 1) * ms[i]
	print(co)


for _ in range(int(input().strip())):
	n = int(input().strip())
	l = []
	for i in range(n):
		(p, q) = map(int, input().strip().split())
		l.append([q, p])
	l.sort()
	d = {}
	ans = 0
	ans1 = 0
	j = 1
	for i in l:
		if i[1] not in d:
			d[i[1]] = 1
			ans += i[0] * j
			j += 1
		else:
			ans1 += i[0]
	ans += ans1 * (j - 1)
	print(ans)


for T in range(int(input())):
	N = int(input())
	dic = {}
	no_band = 0
	for i in range(N):
		(B, L) = map(int, input().split())
		try:
			if L < dic[B][0]:
				dic[B].insert(0, L)
			else:
				dic[B].append(L)
		except KeyError:
			no_band += 1
			dic[B] = [L]
	li_min = [li.pop(0) for li in dic.values()]
	li_min.sort()
	sumi = 0
	for i in range(len(li_min)):
		sumi += (i + 1) * li_min[i]
	total_sumi = 0
	for li in dic.values():
		total_sumi += sum(li)
	print(sumi + total_sumi * no_band)


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		(a, b) = map(int, input().split())
		arr.append([b, a])
	arr.sort()
	total = 0
	j = 1
	ans = 0
	su = {}
	for i in arr:
		if i[1] not in su:
			su[i[1]] = 1
			ans += i[0] * j
			j += 1
		else:
			total += i[0]
	ans += total * (j - 1)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	nl = []
	for i in range(n):
		nl.append([int(x) for x in input().split()])
	nl.sort(key=lambda x: x[1])
	ans = 0
	vis = [False] * len(nl)
	bp = {}
	bb = 0
	for i in range(n):
		if nl[i][0] not in bp:
			bp[nl[i][0]] = True
			bb += 1
			ans += bb * nl[i][1]
			vis[i] = True
	for i in range(n):
		if not vis[i]:
			ans += bb * nl[i][1]
	print(ans)


for _ in range(int(input())):
	num_songs = int(input())
	songs_list = []
	for i in range(num_songs):
		songs_list.append(tuple(map(int, input().split())))
	songs_list.sort(key=lambda x: x[1])
	played_list = [False] * num_songs
	previously_palyed = {}
	sweetness = 0
	for i in range(len(songs_list)):
		song = songs_list[i]
		if song[0] not in previously_palyed:
			previously_palyed[song[0]] = True
			sweetness += song[1] * len(previously_palyed)
			played_list[i] = True
	for i in range(len(songs_list)):
		song = songs_list[i]
		if not played_list[i]:
			sweetness += song[1] * len(previously_palyed)
	print(sweetness)


T = int(input())
for i in range(T):
	n = int(input())
	li = []
	for h in range(n):
		(a, b) = map(int, input().split())
		li.append([b, a])
	li.sort()
	m = {}
	a = 0
	j = 1
	tot = 0
	for i in li:
		if i[1] not in m:
			m[i[1]] = 1
			a += i[0] * j
			j += 1
		else:
			tot += i[0]
	a += tot * (j - 1)
	print(a)


T = int(input())
for i in range(T):
	N = int(input())
	BL = []
	for j in range(N):
		BL.append(list(map(int, input().split())))
	BL = sorted(BL)
	BL_new = [0] * len(BL)
	BL_new[0] = BL[0]
	count1 = 0
	count2 = 0
	for k in range(len(BL) - 1):
		if BL[k][0] == BL[k + 1][0]:
			count1 -= 1
			BL_new[count1] = BL[k + 1]
		else:
			count2 += 1
			BL_new[count2] = BL[k + 1]
	temp = []
	for i in range(len(BL_new)):
		temp.append(BL_new[i][0])
	temp_len = len(set(temp))
	temp2 = []
	for i in range(temp_len):
		temp2.append(BL_new[i][1])
	temp2.sort()
	sweetness = 0
	for j in range(1, temp_len + 1):
		sweetness += j * temp2[j - 1]
	for k in range(temp_len, len(BL_new)):
		sweetness += temp_len * BL_new[k][1]
	print(sweetness)


for _ in range(int(input().strip())):
	n = int(input().strip())
	lst = []
	for idx in range(n):
		lst.append(list(map(int, input().strip().split())))
	lst.sort()
	distinct_song_dict = {}
	first_songs = []
	for song in lst:
		(band_no, song_length) = (song[0], song[1])
		if band_no not in distinct_song_dict:
			distinct_song_dict[band_no] = []
			first_songs.append(song_length)
		else:
			distinct_song_dict[band_no].append(song_length)
	first_songs.sort()
	total_sum = 0
	idx = 0
	while idx < len(first_songs):
		idx += 1
		total_sum += idx * first_songs[idx - 1]
	for band_no in distinct_song_dict:
		total_sum += idx * sum(distinct_song_dict[band_no])
	print(total_sum)


t = int(input())
for i in range(t):
	n = int(input())
	l = [list(map(int, input().split())) for j in range(n)]
	l = sorted(l, key=lambda x: x[1])
	k = set()
	f = 0
	prev = 0
	sweetness = 0
	for i in l:
		if i[0] in k:
			continue
		sweetness += (f + 1) * i[1]
		k.add(i[0])
		f += 1
	l = sorted(l)
	for i in l:
		if i[0] in k:
			if prev == i[0]:
				sweetness += f * i[1]
		prev = i[0]
	print(sweetness)


import time
start = time.time()
t = int(input())
for i in range(t):
	n = int(input())
	a = []
	a1 = {}
	sum1 = 0
	lt = 0
	for j in range(n):
		(b, l) = map(int, input().split())
		a.append([l, b])
	a.sort()
	c = 0
	for k in a:
		if k[1] in a1:
			lt += k[0]
		else:
			c += 1
			sum1 += c * k[0]
			a1[k[1]] = 1
	sum1 += c * lt
	print(sum1)
end = time.time()


for u in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort(key=lambda x: x[1])
	s = 0
	c = 0
	x = 0
	d = {}
	for i in l:
		if i[0] not in d:
			d[i[0]] = 1
			c += 1
			s += c * i[1]
		else:
			x += i[1]
	s += x * c
	print(s)


t = int(input())
for i in range(0, t):
	n = int(input())
	li = []
	for j in range(0, n):
		(b, l) = map(int, input().split())
		li.append([l, b])
	li.sort()
	m = {}
	total = 0
	cn = 1
	ans = 0
	for x in li:
		if x[1] not in m:
			m[x[1]] = 1
			ans = ans + x[0] * cn
			cn += 1
		else:
			total = total + x[0]
	print(ans + (cn - 1) * total)


for _ in range(int(input())):
	n = int(input())
	s = set()
	ls = list()
	arr = list()
	for i in range(n):
		(b, l) = map(int, input().split())
		ls.append([l, b])
	ans = Count = 0
	ls.sort()
	for i in range(n):
		if ls[i][1] not in s:
			Count += 1
			ans += Count * ls[i][0]
			s.add(ls[i][1])
		else:
			arr.append(ls[i][0])
	for i in range(len(arr)):
		ans += Count * arr[i]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	songs = []
	for _ in range(n):
		songs.append(tuple(map(int, input().split())))
	songs.sort(key=lambda x: x[1])
	d = dict()
	unique = []
	common = []
	for (i, j) in songs:
		if i not in d:
			d[i] = 1
			unique.append((i, j))
		else:
			common.append((i, j))
	songs = unique + common
	d = dict()
	dt = 0
	ans = 0
	for (i, j) in songs:
		if i not in d:
			d[i] = 1
			dt += 1
		ans += j * dt
	print(ans)


def solve(arr):
	bands = {}
	for (b, l) in arr:
		if b not in bands:
			bands[b] = l
		bands[b] = min(l, bands[b])
	t = sum((l * i for (i, l) in enumerate(sorted(bands.values()), 1)))
	for (b, l) in arr:
		if l == bands[b]:
			bands[b] = -1
			continue
		t += l * len(bands)
	return t

def main():
	for _ in range(int(input())):
		N = int(input())
		arr = [[int(val) for val in input().split()] for _ in range(N)]
		result = solve(arr)
		print(result)
main()


def sweet(sweet, n):
	n_keys = 0
	first_m = []
	for (k, v) in sweet.items():
		sweet[k] = sorted(v, reverse=True)
		n_keys += 1
		first_m.append(sweet[k][-1])
		sweet[k].pop()
	first_m = sorted(first_m)
	total = 0
	for i in range(n_keys):
		total += (i + 1) * first_m[i]
	for k in sweet.keys():
		total += sum(sweet[k]) * n_keys
	return total
for _ in range(int(input())):
	songs = dict()
	n = int(input())
	for i in range(n):
		(b, l) = map(int, input().split())
		if b in songs:
			songs[b].append(l)
		else:
			songs[b] = [l]
	out = sweet(songs, n)
	print(out)


from collections import Counter
t = int(input())
for w in range(t):
	n = int(input())
	l = []
	typ = []
	c = Counter(typ)
	min_dict = Counter(typ)
	for j in range(n):
		inp = list(map(int, input().split()))
		if c[inp[0]] == 0:
			c[inp[0]] = 1
		if min_dict[inp[0]] == 0:
			min_dict[inp[0]] = inp[1]
		elif inp[1] < min_dict[inp[0]]:
			min_dict[inp[0]] = inp[1]
		l.append(tuple(inp))
	l.sort(key=lambda x: x[0])
	k = list(min_dict.values())
	k.sort()
	p = len(k)
	ans = 0
	for item in l:
		ans += item[1] * p
	diff = 1
	for i in range(len(k)):
		ans -= p * k[i]
		ans += k[i] * diff
		diff += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = []
	dp = {}
	cnt = 0
	sweetness = 0
	visited = [False] * n
	for _ in range(n):
		s.append([int(x) for x in input().split()])
	s.sort(key=lambda x: x[1])
	for i in range(n):
		if s[i][0] not in dp:
			dp[s[i][0]] = True
			cnt += 1
			sweetness += cnt * s[i][1]
			visited[i] = True
	for i in range(n):
		if not visited[i]:
			sweetness += cnt * s[i][1]
	print(sweetness)


from sys import stdin
data = stdin.readlines()
d = 0
T = int(data[d])
d += 1
for t in range(T):
	pairs = {}
	rem = 0
	N = int(data[d])
	d += 1
	length = 0
	for n in range(N):
		(b, l) = map(int, data[d].split(' '))
		d += 1
		if b not in pairs:
			pairs[b] = l
			length += 1
		elif pairs[b] < l:
			rem += l
		else:
			rem += pairs[b]
			pairs[b] = l
	a = []
	a = pairs.values()
	a = list(a)
	a.sort()
	total = 0
	j = 1
	for i in a:
		total += j * i
		j += 1
	total += length * rem
	print(total)


test_cases = int(input())
for _ in range(test_cases):
	nsongs = int(input())
	pairs = []
	for _ in range(nsongs):
		(temp_b, temp_l) = map(int, input().split())
		pairs.append([temp_b, temp_l])
	pairs.sort()
	total = 0
	minSongs = []
	for i in range(nsongs):
		if i == 0 or pairs[i - 1][0] < pairs[i][0]:
			minSongs.append(pairs[i][1])
		else:
			total += pairs[i][1]
	minSongs.sort()
	answer = 0
	m = len(minSongs)
	for i in range(m):
		answer += (i + 1) * minSongs[i]
	answer += m * total
	print(answer)


for _ in range(int(input())):
	n = int(input())
	b = []
	l = []
	for i in range(n):
		(bi, li) = map(int, input().split())
		b.append(bi)
		l.append(li)
	d = dict()
	e = dict()
	arr = []
	count = 0
	sm = 0
	for i in range(n):
		if b[i] in d:
			cur = d[b[i]]
			if cur > l[i]:
				sm += cur
				d[b[i]] = l[i]
				arr[e[b[i]]] = l[i]
			else:
				sm += l[i]
		else:
			d[b[i]] = l[i]
			arr.append(l[i])
			e[b[i]] = count
			count += 1
	arr.sort()
	ans = 0
	for i in range(1, count + 1):
		ans += arr[i - 1] * i
	if sm > 0:
		ans += sm * count
	print(ans)


try:
	for _ in range(int(input())):
		N = int(input())
		cell = {}
		variables = []
		space = []
		score = 0
		variable = 0
		for __ in range(N):
			(a, b) = map(int, input().split())
			if a not in cell:
				cell[a] = b
			elif cell[a] >= b:
				cache = cell[a]
				cell[a] = b
				space.append(cache)
			else:
				space.append(b)
		cc = list(cell.values())
		cc.sort()
		for items in cc:
			variable += 1
			score += variable * items
		if len(space) > 0:
			score += variable * sum(space)
		print(score)
except:
	pass


from operator import itemgetter
t = int(input())
for i in range(t):
	n = int(input())
	arr = []
	for j in range(n):
		a = list(map(int, input().strip().split()))
		arr.append(a)
	arr.sort(key=lambda x: (x[0], x[1]))
	arr1 = []
	arr1.append(arr[0])
	total = 0
	m = 1
	for j in range(1, len(arr)):
		if arr[j][0] > arr[j - 1][0]:
			arr1.append(arr[j])
			m += 1
		else:
			total += arr[j][1]
	ans = m * total
	arr1.sort(key=lambda x: x[1])
	k = 1
	for j in arr1:
		ans += k * j[1]
		k += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	playList = []
	for index in range(n):
		(band, songLen) = map(int, input().split())
		playList.append([band, songLen])
	playList.sort(reverse=False)
	smallestSongs = []
	total = 0
	for index in range(n):
		if index == 0 or playList[index - 1][0] < playList[index][0]:
			smallestSongs.append(playList[index][1])
		else:
			total += playList[index][1]
	M = len(smallestSongs)
	smallestSongs.sort(reverse=False)
	answer = 0
	for index in range(M):
		answer += (index + 1) * smallestSongs[index]
	answer += M * total
	print(answer)


t = int(input())
for _ in range(t):
	hash = {}
	n = int(input())
	rem = []
	for i in range(n):
		(a, b) = map(int, input().split())
		if a in hash:
			if hash[a] > b:
				rem.append(hash[a])
				hash[a] = b
			else:
				rem.append(b)
		else:
			hash[a] = b
	rem.sort()
	c = [hash[i] for i in hash.keys()]
	c.sort()
	ans = 0
	for i in range(len(c)):
		ans += (i + 1) * c[i]
	m = len(c)
	ans += m * sum(rem)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = []
	while n > 0:
		n -= 1
		(a, b) = map(int, input().split())
		x = (b, a)
		arr.append(x)
	arr = sorted(arr)
	song = {}
	total = 0
	k = 1
	ans = 0
	for i in arr:
		if i[1] not in song:
			song[i[1]] = 1
			ans += i[0] * k
			k += 1
		else:
			total += i[0]
	ans += total * (k - 1)
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	songs = []
	for _ in range(N):
		songs.append(list(map(int, input().split())))
	sweetness = 0
	played = set()
	play_later = []
	songs.sort(key=lambda x: x[1])
	for i in songs:
		if i[0] not in played:
			played.add(i[0])
			sweetness += len(played) * i[1]
		else:
			play_later.append(i)
	for i in play_later:
		sweetness += len(played) * i[1]
	print(sweetness)


for T in range(int(input())):
	n = int(input())
	a = []
	b = []
	d = {}
	ind = {}
	visited = [True for x in range(n)]
	for i in range(n):
		(x, y) = map(int, input().split())
		a.append(x)
		b.append(y)
		if x not in d:
			d[x] = []
		d[x].append(y)
		if x not in ind:
			ind[x] = {}
		if y not in ind[x]:
			ind[x][y] = []
		ind[x][y].append(i)
	mins = []
	for keys in d:
		y = min(d[keys])
		mins.append(y)
		visited[ind[keys][y][0]] = False
	mins.sort()
	sweetness = 0
	unique = 0
	for i in range(len(mins)):
		sweetness += mins[i] * (i + 1)
		unique += 1
	for i in range(n):
		if visited[i]:
			sweetness += b[i] * unique
	print(sweetness)


from sys import stdin
tc = int(stdin.readline())
for i in range(tc):
	n = int(stdin.readline())
	list1 = []
	for j in range(n):
		(b, l) = map(int, stdin.readline().split())
		list1.append((l, b))
	list1.sort()
	distinct = set()
	total = 0
	to_add = []
	for each in list1:
		if each[1] not in distinct:
			distinct.add(each[1])
			sweet = len(distinct)
			total += sweet * each[0]
		else:
			to_add.append(each[0])
	print(total + len(distinct) * sum(to_add))


tc = int(input())
for _ in range(tc):
	n = int(input())
	mp = {}
	for i in range(n):
		(b, l) = map(int, input().split())
		if b in mp:
			mp[b].append(l)
		else:
			mp[b] = [l]
	lst = []
	for b in mp.values():
		b.sort()
		lst.append(b[0])
	bands = len(lst)
	lst.sort()
	ans = 0
	for i in range(bands):
		ans += (i + 1) * lst[i]
	for b in mp.values():
		l = len(b)
		for i in range(1, l):
			ans += bands * b[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for j in range(n):
		(x, y) = map(int, input().split())
		a.append([x, y])
	a.sort()
	c = 0
	m = []
	for k in range(n):
		if k == 0 or a[k - 1][0] < a[k][0]:
			m.append(a[k][1])
		else:
			c += a[k][1]
	m.sort()
	ans = 0
	u = len(m)
	for z in range(u):
		ans += (z + 1) * m[z]
	ans += u * c
	print(ans)


T = int(input())
for z in range(T):
	N = int(input())
	dct = {}
	min_dct = {}
	for i in range(N):
		(band, song) = map(int, input().split())
		if band in dct:
			if song < min_dct[band]:
				dct[band].append(min_dct[band])
				min_dct[band] = song
			else:
				dct[band].append(song)
		else:
			min_dct[band] = song
			dct[band] = []
	min_lst = []
	lst = []
	for elem in min_dct.values():
		min_lst.append(elem)
	for elem in dct.values():
		lst += elem
	min_lst.sort()
	lst.sort()
	l = len(min_lst)
	ans = 0
	for i in range(l):
		ans += min_lst[i] * (i + 1)
	ans += l * sum(lst)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = {}
	ld = 0
	for i in range(n):
		(x, y) = map(int, input().split())
		if x not in l:
			l[x] = y
		elif l.get(x) > y:
			ld += l.get(x)
			l[x] = y
		else:
			ld += y
	sorted_l = sorted(l.items(), key=lambda x: x[1])
	s = 0
	k = 0
	for i in sorted_l:
		k += 1
		s = s + i[1] * k
	s = s + ld * k
	print(s)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 0
	s = 0
	d = defaultdict(list)
	for i in range(n):
		(b, l1) = [int(k) for k in input().split()]
		d[b].append(l1)
		d[b].sort()
	l1 = list(d.values())
	l1.sort()
	j = 1
	for i in l1:
		ans += j * i[0]
		s += sum(i) - i[0]
		j += 1
	ans += s * (j - 1)
	print(ans)


t = int(input())
for T in range(t):
	n = int(input())
	val = []
	s = set()
	for i in range(n):
		val.append([int(x) for x in input().split()][::-1])
	val.sort()
	c = 0
	c1 = 0
	ans = 0
	for i in range(n):
		if val[i][1] not in s:
			s.add(val[i][1])
			c += 1
			ans += c * val[i][0]
		else:
			c1 += val[i][0]
	ans += c * c1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		(a, b) = map(int, input().split())
		arr.append((b, a))
	arr.sort()
	band = set()
	play_last = []
	res = 0
	for (l, b) in arr:
		if b not in band:
			band.add(b)
			res += l * len(band)
		else:
			play_last.append((l, b))
	for (l, b) in play_last:
		res += l * len(band)
	print(res)


from collections import defaultdict
cases = int(input())
for _ in range(cases):
	n = int(input())
	count = ans = 0
	hmap = defaultdict(list)
	for i in range(n):
		(b, l) = tuple(map(int, input().split()))
		hmap[b].append(l)
	check = {}
	for i in hmap:
		check[i] = min(hmap[i])
	tmp = sorted(list(check.values()))
	for i in range(len(tmp)):
		ans += (i + 1) * tmp[i]
	for i in hmap:
		sm = sum(hmap[i]) - check[i]
		ans += sm * len(hmap)
	print(ans)


import sys
import math

class Student:

	def __init__(self, B, L):
		self.B = B
		self.L = L

	def __repr__(self):
		return repr((self.B, self.L))
t = int(sys.stdin.readline())
for i in range(t):
	N = int(sys.stdin.readline())
	stuobj = []
	for j in range(N):
		(b, l) = [int(x) for x in sys.stdin.readline().split()]
		stuobj.append(Student(b, l))
	stuobj.sort(key=lambda student: student.L)
	distinct_band = set()
	counter = 0
	mysum = 0
	for eachstu in stuobj:
		if eachstu.B not in distinct_band:
			counter = counter + 1
			distinct_band.add(eachstu.B)
			mysum = mysum + counter * eachstu.L
			eachstu.L = 0
	for eachstu in stuobj:
		mysum = mysum + counter * eachstu.L
	print(mysum, end='\n')


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	songs = []
	for i in range(n):
		songs.append(tuple(map(int, input().split())))
	unique = []
	common = []
	d = defaultdict(lambda : 0)
	songs.sort(key=lambda x: x[1])
	for (i, j) in songs:
		if d[i] == 0:
			d[i] = 1
			unique.append((i, j))
		else:
			common.append((i, j))
	songs = unique + common
	d = defaultdict(lambda : 0)
	ans = bands = 0
	for (i, j) in songs:
		if d[i] == 0:
			bands += 1
			d[i] = 1
		ans += j * bands
	print(ans)


from sys import *
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	l = []
	d = set()
	ans = 0
	new = []
	for _ in range(n):
		(a, b) = map(int, stdin.readline().split())
		l.append([b, a])
	l.sort()
	for j in l:
		if j[1] not in d:
			d.add(j[1])
			ans += j[0] * len(d)
		else:
			new.append(j[0])
	print(ans + len(d) * sum(new))


from collections import defaultdict as df
for q in range(int(input())):
	n = int(input())
	m = df(list)
	for i in range(n):
		(p, r) = [int(e) for e in input().split()]
		m[p].append(r)
	l = []
	c = 0
	for i in m:
		x = min(m[i])
		l.append(x)
		c += sum(m[i]) - x
	l.sort()
	p = len(l)
	c *= p
	for i in range(p):
		c += (i + 1) * l[i]
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	data = []
	total_swt = 0
	for _ in range(n):
		data.append(list(map(int, input().split())))
	data.sort()
	initials = []
	left_out_song_lengths = 0
	for i in range(n):
		if i == 0 or data[i - 1][0] < data[i][0]:
			initials.append(data[i][1])
		else:
			left_out_song_lengths += data[i][1]
	used_bands = len(initials)
	initials.sort()
	for i in range(used_bands):
		total_swt += (i + 1) * initials[i]
	total_swt += used_bands * left_out_song_lengths
	print(total_swt)


def calc_sweetness(l, sweetness):
	length = 0
	songs.append(l[0][1])
	for i in range(len(l) - 1):
		if l[i][0] < l[i + 1][0]:
			songs.append(l[i + 1][1])
		else:
			length = length + l[i + 1][1]
	songs.sort()
	for i in range(1, len(songs) + 1):
		sweetness = sweetness + i * songs[i - 1]
	return (sweetness, length)
no_test_cases = int(input())
while no_test_cases > 0:
	songs = []
	li = []
	no_songs = int(input())
	sweetness = 0
	while no_songs > 0:
		s = input()
		(b, l) = s.split()
		t = (int(b), int(l))
		li.append(t)
		no_songs = no_songs - 1
	li.sort()
	(sweetness, length) = calc_sweetness(li, sweetness)
	sweetness = sweetness + len(songs) * length
	print(sweetness)
	no_test_cases = no_test_cases - 1