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}$.

Difficulty: interview

Starter code:

Solutions:
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)


'''
Created on 2019. 9. 21.

@author: kkhh88
'''
#q = int(input())
#x, y = map(int,input().split(' '))

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 (cnt, lr)
    print (ans)

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 )


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]
    # print(cnt)
    # print(ruiseki_cnt)
    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)
    # print(need)
    info = sorted(info, reverse = True)
    #print(info)

    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)

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

    #print(M)
    #print(MCOUNT)

    ACC=list(accumulate(MCOUNT))

    #print(ACC)
    HQ=[]
    ANS=0
    use=0

    for i in range(n-1,-1,-1):
        for j in M[i]:
            heapq.heappush(HQ,j)

        #print(HQ)
            
        while ACC[i-1]+use<i:
            x=heapq.heappop(HQ)
            ANS+=x
            use+=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 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
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 = list(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 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
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


# solve()

T = ni()
for _ in range(T):
    solve()


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


#sys.stdout.write('YES\n')
#sys.stdout.write(f'{res}\n')
#sys.stdout.write(f'{y1} {x1} {y2} {x2}\n')