#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<vector>#include<set>#include<map>#include<queue>#include<sstream>#include<string>#include<bitset>using namespace std;typedef long long LL;const LL LINF = (1LL <<63);const int INF = 1 << 31;const int NS = 810;const int MS = 19;const LL MOD = 1000000007;struct node{ int a, b; bool operator < (const node & y) const { return b > y.b; }} p[NS];int n;int dp[NS][NS];bool vis[NS];int main(){ int T; scanf("%d", &T); while(T --) { scanf("%d", &n); for(int i=1; i<=n; i++) { scanf("%d %d",&p[i].a, &p[i].b); } sort(p + 1, p + n + 1); memset(dp, 0, sizeof(dp)); for(int i=1; i<=n; i++) { for(int j=1; 2*j<=i; j++) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+p[i].a); } } printf("%dn", dp[n][n >> 1]); }}
