The only difference between easy and hard versions is constraints.

Now elections are held in Berland and you want to win them. More precisely, you want everyone to vote for you.

There are $n$ voters, and two ways to convince each of them to vote for you. The first way to convince the $i$-th voter is to pay him $p_i$ coins. The second way is to make $m_i$ other voters vote for you, and the $i$-th voter will vote for free.

Moreover, the process of such voting takes place in several steps. For example, if there are five voters with $m_1 = 1$, $m_2 = 2$, $m_3 = 2$, $m_4 = 4$, $m_5 = 5$, then you can buy the vote of the fifth voter, and eventually everyone will vote for you. Set of people voting for you will change as follows: ${5} \rightarrow {1, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 4, 5}$.

Calculate the minimum number of coins you have to spend so that everyone votes for you.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \le n \le 5000$) — the number of voters.

The next $n$ lines contains the description of voters. $i$-th line contains two integers $m_i$ and $p_i$ ($1 \le p_i \le 10^9, 0 \le m_i < n$).

It is guaranteed that the sum of all $n$ over all test cases does not exceed $5000$.


-----Output-----

For each test case print one integer — the minimum number of coins you have to spend so that everyone votes for you.


-----Example-----
Input
3
3
1 5
2 10
2 8
7
0 1
3 1
1 1
6 1
1 1
4 1
4 1
6
2 6
2 3
2 8
2 7
4 4
5 5

Output
8
0
7



-----Note-----

In the first test case you have to buy vote of the third voter. Then the set of people voting for you will change as follows: ${3} \rightarrow {1, 3} \rightarrow {1, 2, 3}$.

In the second example you don't need to buy votes. The set of people voting for you will change as follows: ${1} \rightarrow {1, 3, 5} \rightarrow {1, 2, 3, 5} \rightarrow {1, 2, 3, 5, 6, 7} \rightarrow {1, 2, 3, 4, 5, 6, 7}$.

In the third test case you have to buy votes of the second and the fifth voters. Then the set of people voting for you will change as follows: ${2, 5} \rightarrow {1, 2, 3, 4, 5} \rightarrow {1, 2, 3, 4, 5, 6}$.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Data structures

Greedy algorithms


Solutions:
import sys
from heapq import heappop, heappush
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
t = int(input())
for _ in range(t):
	n = int(input())
	mp = []
	for i in range(n):
		(mi, pi) = map(int, input().split())
		mp.append((mi, pi))
	mp.sort()
	prices = []
	cost = 0
	bribed = 0
	i = n - 1
	while i >= 0:
		currM = mp[i][0]
		heappush(prices, mp[i][1])
		while i >= 1 and mp[i - 1][0] == currM:
			i -= 1
			heappush(prices, mp[i][1])
		already = i + bribed
		for k in range(max(0, currM - already)):
			cost += heappop(prices)
			bribed += 1
		i -= 1
	print(cost)


import sys
input = sys.stdin.readline
import heapq
from itertools import accumulate
t = int(input())
for test in range(t):
	n = int(input())
	M = [[] for i in range(n)]
	MCOUNT = [0] * n
	for i in range(n):
		(m, p) = list(map(int, input().split()))
		M[m].append(p)
		MCOUNT[m] += 1
	ACC = list(accumulate(MCOUNT))
	HQ = []
	ANS = 0
	use = 0
	for i in range(n - 1, -1, -1):
		for j in M[i]:
			heapq.heappush(HQ, j)
		while ACC[i - 1] + use < i:
			x = heapq.heappop(HQ)
			ANS += x
			use += 1
	print(ANS)


import heapq
for _ in range(int(input())):
	n = int(input())
	voters = []
	for i in range(n):
		(m, p) = list(map(int, input().split()))
		voters.append((m, -p))
	voters.sort()
	for i in range(n):
		voters[i] = (voters[i][0], -voters[i][1])
	ans = 0
	costs = []
	heapq.heapify(costs)
	bought = 0
	for i in range(n - 1, -1, -1):
		buysNeeded = voters[i][0] - i - bought
		heapq.heappush(costs, voters[i][1])
		while buysNeeded > 0 and len(costs) > 0:
			ans += heapq.heappop(costs)
			bought += 1
			buysNeeded -= 1
	print(ans)


import sys
import heapq

def solve(pr, mm):
	omm = []
	n = len(mm)
	for i in range(n + 1):
		omm.append([])
	for i in range(n):
		omm[mm[i]].append(pr[i])
	for i in range(n + 1):
		omm[i] = sorted(omm[i])
	heap = []
	c = 0
	t = n
	p = 0
	for i in range(n, -1, -1):
		for h in omm[i]:
			heapq.heappush(heap, h)
		t -= len(omm[i])
		mn = max(i - c - t, 0)
		c += mn
		for j in range(mn):
			p += heapq.heappop(heap)
	return p

def __starting_point():
	t = int(input().strip())
	for i in range(t):
		n = int(input().strip())
		ms = []
		ps = []
		for j in range(n):
			arr = [int(v) for v in input().strip().split(' ')]
			ms.append(arr[0])
			ps.append(arr[1])
		print(solve(ps, ms))
__starting_point()


import sys
input = sys.stdin.readline
import heapq as hq
t = int(input())
for _ in range(t):
	n = int(input())
	vt = [list(map(int, input().split())) for i in range(n)]
	vt.sort(reverse=True)
	q = []
	hq.heapify(q)
	ans = 0
	cnt = 0
	for i in range(n):
		hq.heappush(q, vt[i][1])
		if vt[i][0] >= n - i + cnt:
			ans += hq.heappop(q)
			cnt += 1
	print(ans)


import sys
from heapq import *
t = int(input())
for ti in range(t):
	n = int(input())
	a = []
	for i in range(n):
		(mi, pi) = map(int, input().split())
		a.append((mi, -pi))
	a.sort()
	c = 0
	h = []
	res = 0
	for i in reversed(range(n)):
		heappush(h, -a[i][1])
		while c + i < a[i][0]:
			res += heappop(h)
			c += 1
	print(res)


import sys
import heapq as hq
readline = sys.stdin.readline
read = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	n = ni()
	vot = [tuple(nm()) for _ in range(n)]
	vot.sort(key=lambda x: (-x[0], x[1]))
	q = list()
	c = 0
	cost = 0
	for i in range(n):
		hq.heappush(q, vot[i][1])
		while n - i - 1 + c < vot[i][0]:
			cost += hq.heappop(q)
			c += 1
	print(cost)
	return
T = ni()
for _ in range(T):
	solve()


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	from collections import defaultdict
	from heapq import heappop, heappush
	t = int(input())
	ans = [''] * t
	for ti in range(t):
		n = int(input())
		dd: Tp.Dict[int, Tp.List[int]] = defaultdict(list)
		costs = [0] * n
		for i in range(n):
			(mi, pi) = map(int, input().split())
			dd[mi].append(i)
			costs[i] = pi
		hq = []
		for cnt in range(n):
			for x in dd[cnt]:
				heappush(hq, -costs[x])
			if hq:
				heappop(hq)
		ans[ti] = str(-sum(hq))
	sys.stdout.buffer.write(('\n'.join(ans) + '\n').encode('utf-8'))
main()


import sys
from heapq import *
t = int(sys.stdin.readline())
for ti in range(t):
	n = int(sys.stdin.readline())
	a = [tuple(map(int, sys.stdin.readline().split())) for i in range(n)]
	a.sort(key=lambda x: (x[0], -x[1]))
	c = 0
	h = []
	res = 0
	for i in range(n - 1, -1, -1):
		heappush(h, a[i][1])
		while c + i < a[i][0]:
			res += heappop(h)
			c += 1
	print(res)


import heapq
t = int(input())
for _ in range(t):
	n = int(input())
	info = [list(map(int, input().split())) for i in range(n)]
	info = sorted(info)
	cnt = [0] * n
	for i in range(n):
		ind = info[i][0]
		cnt[ind] += 1
	ruiseki_cnt = [0] * (n + 1)
	for i in range(n):
		ruiseki_cnt[i + 1] = ruiseki_cnt[i] + cnt[i]
	need = [0] * n
	for i in range(1, n):
		if cnt[i] != 0 and i > ruiseki_cnt[i]:
			need[i] = min(i - ruiseki_cnt[i], i)
	info = sorted(info, reverse=True)
	num = n - 1
	pos = 0
	q = []
	used_cnt = 0
	ans = 0
	while True:
		if num == -1:
			break
		while True:
			if pos < n and info[pos][0] >= num:
				heapq.heappush(q, info[pos][1])
				pos += 1
			else:
				break
		if need[num] - used_cnt > 0:
			tmp = need[num] - used_cnt
			for _ in range(tmp):
				ans += heapq.heappop(q)
			used_cnt += tmp
		num -= 1
	print(ans)


q = int(input())
for _ in range(q):
	n = int(input())
	lr = []
	for i in range(n):
		lr.append(list(map(int, input().split(' '))))
	lr.sort(key=lambda x: x[1], reverse=True)
	lr.sort(key=lambda x: x[0])
	cnt = [0] * n
	for i in range(n):
		if lr[i][0] > i:
			if lr[i][0] - i > cnt[lr[i][0]]:
				cnt[lr[i][0]] = lr[i][0] - i
	i = n - 1
	tmp = 0
	ans = 0
	lst = []
	while i >= 0:
		if i > 0 and lr[i][0] == lr[i - 1][0]:
			lst.append(lr[i][1])
			i = i - 1
		else:
			lst.append(lr[i][1])
			if cnt[lr[i][0]] > tmp:
				lst.sort()
				for _ in range(tmp, cnt[lr[i][0]]):
					ans = ans + lst.pop(0)
				tmp = cnt[lr[i][0]]
			i = i - 1
	print(ans)


import sys
import heapq

def solve(pr, mm):
	omm = []
	n = len(mm)
	for i in range(n + 1):
		omm.append([])
	for i in range(n):
		omm[mm[i]].append(pr[i])
	heap = []
	c = 0
	t = n
	p = 0
	for i in range(n, -1, -1):
		for h in omm[i]:
			heapq.heappush(heap, h)
		t -= len(omm[i])
		mn = max(i - c - t, 0)
		c += mn
		for j in range(mn):
			p += heapq.heappop(heap)
	return p
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	ms = []
	ps = []
	for j in range(n):
		arr = [int(v) for v in input().strip().split(' ')]
		ms.append(arr[0])
		ps.append(arr[1])
	print(solve(ps, ms))


from sys import stdin, stdout
import heapq

class MyHeap(object):

	def __init__(self, initial=None, key=lambda x: x):
		self.key = key
		if initial:
			self._data = [(key(item), item) for item in initial]
			heapq.heapify(self._data)
		else:
			self._data = []

	def push(self, item):
		heapq.heappush(self._data, (self.key(item), item))

	def pop(self):
		return heapq.heappop(self._data)[1]

	def print(self):
		for hd in self._data:
			print(hd)
		print('-------------------------------')

def getminnumerofcoins(n, mpa):
	res = 0
	mpa.sort(key=lambda x: (x[0], -x[1]))
	gap = []
	cur = 0
	for i in range(len(mpa)):
		mp = mpa[i]
		if mp[0] > cur:
			t = [i, mp[0] - cur]
			gap.append(t)
		cur += 1
	if len(gap) == 0:
		return 0
	hp = MyHeap(key=lambda x: x[1])
	gp = gap.pop()
	lidx = gp[0]
	remaing = gp[1]
	for i in range(lidx, len(mpa)):
		ci = [i, mpa[i][1]]
		hp.push(ci)
	cur = 0
	offset = 0
	for i in range(len(mpa)):
		mp = mpa[i]
		need = mp[0] - cur
		if need > 0:
			for j in range(need):
				if (remaing == 0 or len(hp._data) == 0) and len(gap) > 0:
					lg = gap.pop()
					while len(gap) > 0 and lg[1] - offset <= 0:
						lg = gap.pop()
					for k in range(lg[0], lidx):
						ci = [k, mpa[k][1]]
						hp.push(ci)
					lidx = lg[0]
					remaing = lg[1] - offset
				c = hp.pop()
				if c[0] == i:
					c = hp.pop()
				res += c[1]
				cur += 1
				offset += 1
				remaing -= 1
		cur += 1
	return res
t = int(stdin.readline())
for i in range(t):
	n = int(stdin.readline())
	mpa = []
	for j in range(n):
		mp = list(map(int, stdin.readline().split()))
		mpa.append(mp)
	res = getminnumerofcoins(n, mpa)
	stdout.write(str(res) + '\n')


import sys

def I():
	return sys.stdin.readline().rstrip()

class Heap:

	def __init__(self):
		self.l = [-1]
		self.n = 0

	def n(self):
		return self.n

	def top(self):
		return self.l[1]

	def ins(self, x):
		self.l.append(x)
		n = len(self.l) - 1
		i = n
		while i > 1:
			j = i // 2
			if self.l[j] > self.l[i]:
				(self.l[j], self.l[i]) = (self.l[i], self.l[j])
				i = j
			else:
				break

	def pop(self):
		r = self.l[1]
		l = self.l.pop()
		n = len(self.l) - 1
		if n:
			self.l[1] = l
			i = 1
			while True:
				j = i * 2
				k = j + 1
				if k < len(self.l) and self.l[i] > max(self.l[j], self.l[k]):
					if self.l[j] == min(self.l[j], self.l[k]):
						(self.l[i], self.l[j]) = (self.l[j], self.l[i])
						i = j
					else:
						(self.l[i], self.l[k]) = (self.l[k], self.l[i])
						i = k
				elif k < len(self.l) and self.l[i] > self.l[k]:
					(self.l[i], self.l[k]) = (self.l[k], self.l[i])
					i = k
				elif j < len(self.l) and self.l[i] > self.l[j]:
					(self.l[i], self.l[j]) = (self.l[j], self.l[i])
					i = j
				else:
					break
		return r
t = int(I())
for _ in range(t):
	n = int(I())
	voter = [list(map(int, I().split())) for _ in range(n)]
	h = Heap()
	d = {}
	for (m, p) in voter:
		if m not in d:
			d[m] = []
		d[m].append(p)
	need = {}
	c = 0
	sk = sorted(d.keys())
	for m in sk:
		need[m] = max(0, m - c)
		c += len(d[m])
	c = 0
	ans = 0
	for m in sk[::-1]:
		for p in d[m]:
			h.ins(p)
		while c < need[m]:
			c += 1
			ans += h.pop()
	print(ans)