度度熊是他同时代中最伟大的数学家，一切数字都要听命于他。现在，又到了度度熊和他的数字仆人们玩排排坐游戏的时候了。游戏的规则十分简单，参与游戏的N个整数将会做成一排，他们将通过不断交换自己的位置，最终达到所有相邻两数乘积的和最大的目的，参与游戏的数字有整数也有负数。度度熊为了在他的数字仆人面前展现他的权威，他规定某些数字只能在坐固定的位置上，没有被度度熊限制的数字则可以自由地交换位置。

 

 

第一行一个整数T，表示T组数据。
每组测试数据将以如下格式从标准输入读入：

N

a1p1

a2p2

:

aNPN

第一行，整数 N(1≤N≤16)，代表参与游戏的整数的个数。

从第二行到第 (N+1) 行，每行两个整数，ai(−10000≤ai≤10000)、pi(pi=−1 或 0≤pi<N)，以空格分割。ai代表参与游戏的数字的值，pi代表度度熊为该数字指定的位置，如果pi=−1，代表该数字的位置不被限制。度度熊保证不会为两个数字指定相同的位置。

 

 

第一行输出："Case #i:"。i代表第i组测试数据。

第二行输出数字重新排列后最大的所有相邻两数乘积的和，即max{a1⋅a2+a2⋅a3+......+aN−1⋅aN}。

 

 

 

 

 

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <cmath>

#include<queue>

#include<vector>

using namespace std;

const int N = <<, M = 1e6+, mod = ,inf = 1e9;

typedef long long ll;

ll dp[<<][];

int n,a[N],p[N],H[N],F[N];

int main() {

    int T,cas = ;

    scanf("%d",&T);

    while(T--) {

        scanf("%d",&n);

        memset(H,,sizeof(H));

        memset(F,-,sizeof(F));

        int tmp = ;

        for(int i=;i<n;i++) {

            scanf("%d%d",&a[i],&p[i]);

            if(p[i]!=-)

             H[i] = ,F[p[i]] = i;

        }

        for(int i=;i<(<<n);i++)

            for(int j=;j<n;j++) dp[i][j] = -1e18;

  //      for(int i=0;i<n;i++)

    //        for(int j=0;j<n;j++) if(i!=j&&!H[i]&&!H[j]) dp[(1<<i)|(1<<j)][j] = a[i]*a[j], dp[(1<<i)|(1<<j)][i] = a[i]*a[j];

       if(F[]!=-) dp[(<<F[])][F[]] = ;

       else {

        for(int i=;i<n;i++) {

            if(!H[i]) dp[(<<i)][i] = ;

        }

       }

       int U = (<<n) - ;

        for(int i=;i<=U;i++) {

            int counts = ;

            for(int j=;j<n;j++) if((<<j)&(i)) counts++;

            if(F[counts]!=-) {

                counts = F[counts];

                for(int j=;j<n;j++) if(i&(<<j)&&counts!=j)dp[i|(<<(counts))][counts] = max(dp[i][j]+a[j]*a[counts],dp[i|(<<counts)][counts]);

            }

            else {

                for(int k=;k<n;k++) {

                    if((<<k)&(i))

                    for(int j=;j<n;j++) {

                       if(!((<<j)&i)) {

                            dp[i|(<<j)][j] = max(dp[i|(<<j)][j],dp[i][k]+a[k]*a[j]);

                        }

                    }

                }

            }

        }

        printf("Case #%d:\n",cas++);

        ll ans = -1e18;

        for(int i=;i<n;i++) ans = max(dp[U][i],ans) ;

        printf("%I64d\n",ans);

    }

    return ;

}