Problem Description

There are $n$ courses in the course selection system of Marjar University. The $i$-th course is described by two values: happiness $Hi$ and credit $Ci$. If a student selects $m$ courses $x1$, $x2$, ..., $xm$, then his comfort level of the semester can be defined as follows:
$$(\sum^m_{i=1}H_{x_i})^2-(\sum^m_{i=1}H_{x_i})\times (\sum^m_{i=1}C_{x_i})-(\sum^m_{i=1}C_{x_i})^2$$
Edward, a student in Marjar University, wants to select some courses (also he can select no courses, then his comfort level is $0$) to maximize his comfort level. Can you help him?

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains a integer $n$ $(1 ≤ n ≤ 500)$ -- the number of cources.

Each of the next $n$ lines contains two integers $H_i$ and $C_i$ $(1 ≤ H_i ≤ 10000, 1 ≤ C_i ≤ 100)$.

It is guaranteed that the sum of all $n$ does not exceed $5000$.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.

Output

For each case, you should output one integer denoting the maximum comfort.

Sample Input

2
3
10 1
5 1
2 10
2
1 10
2 10

Sample Output

191
0

Hint

For the first case, Edward should select the first and second courses.

For the second case, Edward should select no courses.

Problem Link

vjudge_ZOJ-3956-Course Selection System

Thought

通过题目我们可以了解到在一定的$C$下$H$越高，$comfort level$就越高，所以我们应该求出在所有可能的$C$值下最高的$H$值，因为$C$的最大值并不大，题目给出不超过$5000$；因此我们可以创建一个数组来进行0/1背包的求解。求出每个$C$下最高的$H$，注意$H$的范围，所以int的范围是不够表达comfortable的值的，要用long long int,求出所有最高$H$后再进行计算，求出所有$C$中的最优解。

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
# define MaxN 500+5
# define MaxC 500*100+5
typedef long long int LL;
LL max(LL a,LL b)
{
    return a>b ? a:b;
}
int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int dp[MaxC];
        int H[MaxN];
        int C[MaxN];
        memset(dp,0,sizeof dp);
        int N;
        int i;
        int TopC=0;
        scanf("%d",&N);
        for(i=1;i<=N;i++)
        {
            scanf("%d",&H[i]);
            scanf("%d",&C[i]);
            TopC+=C[i];
        } 
        for(i=1;i<=N;i++)
        {
            int l;
            for(l=TopC;l>=C[i];--l)        
                    dp[l]=max(dp[l],dp[l-C[i]]+H[i]);
        }
        LL max1=0;
        for(i=0;i<=TopC;i++)
            max1=max(1LL*dp[i]*dp[i]-1LL*dp[i]*i-1LL*i*i,max1);
        printf("%lld",max1);
        if(T!=0)
            printf("\n");
    }
    return 0;
}