def main():
    t=int(input())
    r=[]
    for _ in range(t):
        s=int(input())
        wt=[]
        val=[]
        for _ in range(s):
            m,n=map(int,input().split())
            wt.append(m)
            val.append(n)
        n=s
        w=s
        dp=[]
        for i in range(n+1):
            dp.append([None]*(w+1))
        for i in range(n + 1):
            for j in range(w + 1):
                if i==0 or j==0:
                    dp[i][j]=0
        for i in range(1, n + 1):
            for j in range(1, w + 1):
                if wt[i-1]<=j:
                    dp[i][j] =  max((val[i-1]+dp[i-1][j-wt[i-1]]), dp[i-1][j])
                else:
                    dp[i][j]=dp[i-1][j]
      
        res=dp[n][w]
        for i in range(n, 0, -1): 
            if res <= 0: 
                break
            if res == dp[i - 1][w]: 
                continue
            else: 
                r.append(val[i - 1])
                res = res - val[i - 1] 
                w = w - wt[i - 1] 
    sum=0
    for i in range(len(r)):
        if (i+1)%10==0:
            sum+=2*r[i]
        else:
            sum+=r[i]
    print(sum)
main()