AC code:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=2200;
const int inf=1000000000;

int n,lim,ans;
int f[maxn][maxn];

struct Book
{
       int w,h;
       bool operator <(const Book &rhs)const
       {
            return h>rhs.h;
       }
}B[100];

int get()
{
    int f=0,v=0; char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') break;
    if(ch=='-') f=1; else v=ch-48;
    while(isdigit(ch=getchar())) v=v*10+ch-48;
    if(f) return -v; else return v;
}

void init()
{
     int sum=0,h,w;
     n=get();
     for(int i=1;i<=n;i++)
     {
         B[i].h=get(); B[i].w=get();
         sum+=B[i].w;
     }
     lim=min(sum/2+90,sum);
     sort(B+1,B+n+1);
     for(int i=0;i<=sum;i++)
	     for(int j=0;j<=sum;j++) f[i][j]=inf;
}

void work()
{
     int sum=0,w,h; f[0][0]=0;
     for(int k=2;k<=n;k++)
     {
         w=B[k].w; h=B[k].h; sum+=w;
         int smax=min(sum,lim);
         for(int i=smax;i>w;i--)//(i>w j>w)
             for(int j=min(smax,sum-i);j>=i;j--)
             {
                 f[i][j]=min(f[i][j],f[i-w][j]);
                 f[i][j]=min(f[i][j],min(f[i][j-w],f[j-w][i]));
             }
         for(int j=min(smax,sum-w);j>=w;j--)//(i==w j>=w)
             f[w][j]=min(f[w][j],f[0][j]+h);
         for(int i=w-1;i>=0;i--)
         {
             for(int j=min(smax,sum-i);j>w;j--)//(i<w j>w)
                 f[i][j]=min(f[i][j],min(f[i][j-w],f[j-w][i]));
             f[i][w]=min(f[i][w],f[0][i]+h);//(i<w j==w)
         }
     }
	 sum+=B[1].w; ans=inf;
     for(int i=1;i+i<sum;i++)
         for(int j=i;i+j<sum;j++)
         {
             w=max(i,max(j,sum-i-j));
             if(f[i][j]<inf) ans=min(ans,w*(f[i][j]+B[1].h));
         }
     printf("%d\n",ans);
}

int main()
{
    int TT=get();
    for(int i=1;i<=TT;i++)
    {
        init();
        work();
    }
    return 0;
}