#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=8*123;
int dp[maxn][maxn];
int n;
struct he
{
    int id, x,y;
} Sky[maxn];
bool cmp(he a,he b)
{
    return a.y>b.y;
}
void init()
{   scanf("%d",&n);
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&Sky[i].x,&Sky[i].y);
        Sky[i].id=i;
    }
    sort(Sky+1,Sky+1+n,cmp);
}
void play()
{
    dp[1][0]=0;
    for(int i=2; i<=n; i++)
    {
        int x=Sky[i].x;
        int y=Sky[i].y;
        for(int j=1; j<i; j++)
        {
            int le=j;
            int ri=i-j-1;
            if(le<ri)continue;
            dp[le+1][ri]=dp[le][ri];
        }
        for(int j=1; j<i; j++)
        {
            int le=j;
            int ri=i-j-1;
            if(le<=ri)continue;
            dp[le][ri+1]=max(dp[le][ri]+x,dp[le][ri+1]);
        }
    }
    printf("%d\n",dp[n/2][n/2]);
}
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//   cout << "Hello world!" << endl;
    return 0;
}