rt，可能是记贡献出错了，但是我看不什么问题。

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned ll
#define db double
#define ld long db

#define M 4005
#define N 105
#define mod 1000000007
#define inf 1e9
#define dinf 1e15
#define linf 1e18

int T;
int n;
ll t[M][2];
ll dp[M][2];

ll pre[M][2],ppre[M][2];
ll suf[M][2],ssuf[M][2];

void init(){
	for(int i=1;i<=n;++i) dp[i][0]=dp[i][1]=linf;
	dp[0][0]=dp[0][1]=0;
	pre[0][0]=pre[0][1]=ppre[0][0]=ppre[0][1]=suf[n+1][0]=suf[n+1][1]=ssuf[n+1][0]=ssuf[n+1][1]=0;
	for(int i=1;i<=n;++i){
		pre[i][0]=pre[i-1][0]+t[i][0];
		pre[i][1]=pre[i-1][1]+t[i][1];
		ppre[i][0]=ppre[i-1][0]+t[i][0]*i;
		ppre[i][1]=ppre[i-1][1]+t[i][1]*i;
	}
	for(int i=n;i>=1;--i){
		suf[i][0]=suf[i+1][0]+t[i][0];
		suf[i][1]=suf[i+1][1]+t[i][1];
		ssuf[i][0]=ssuf[i+1][0]+t[i][0]*(n-i+1);
		ssuf[i][1]=ssuf[i+1][1]+t[i][1]*(n-i+1);
	}
}

ll calc(int l,int r,int s){
	if(l==1) return ssuf[l][s]-ssuf[r+1][s]-(suf[l][s]-suf[r+1][s])*(n-r);
	if(r==n) return ppre[r][s]-ppre[l-1][s]-(pre[r][s]-pre[l-1][s])*(l-1);
	if((r-l+1)&1){
		int mid=(l+r)>>1;
		ll res=t[mid][s]*(mid-l+1);
		res+=ppre[mid-1][s]-ppre[l-1][s]-(pre[mid-1][s]-pre[l-1][s])*(l-1);
		res+=ssuf[mid+1][s]-ssuf[r+1][s]-(suf[mid+1][s]-suf[r+1][s])*(n-r);
		return res;
	} else {
		int mid=(l+r)>>1;
		ll res=0;
		res+=ppre[mid][s]-ppre[l-1][s]-(pre[mid][s]-pre[l-1][s])*(l-1);
		res+=ssuf[mid+1][s]-ssuf[r+1][s]-(suf[mid+1][s]-suf[r+1][s])*(n-r);
		return res;
	}
}

int main(){
	scanf("%d",&T);
	for(int tot=1;tot<=T;++tot){
		if(tot>1) printf("\n");
		scanf("%d",&n);
		for(int i=1;i<=n;++i) scanf("%lld %lld",&t[i][0],&t[i][1]);
		init();
		for(int i=1;i<=n;++i){
			for(int j=(i==n);j<i;++j){
				dp[i][0]=min(dp[i][0],dp[j][1]+calc(j+1,i,1));
				dp[i][1]=min(dp[i][1],dp[j][0]+calc(j+1,i,0));
			}
		}
		printf("Case #%d: %lld",tot,min(dp[n][0],dp[n][1]));
	}
	return 0;
}