#include<bits/stdc++.h>
using namespace std;

int dp[109][109][109];
int cost[109][109];

int rec(int i, int lasta, int lastb){
    if(i<0)return 0;

    if(i==0)return cost[i][lasta]+cost[i][lastb];
    
    int &ret=dp[i][lasta][lastb];
    //dp already calculated
    if(ret!=-1)return ret;

    //assign node numbered i to set A
    ret=cost[i][lasta] + rec(i-1,i,lastb);

    //assign node numbered i to set B
    ret=min(ret, cost[i][lastb] + rec(i-1,lasta,i));

    return ret;
}

int main(){
    int p;
    cin >> p;
    for(int ii=1; ii<=p; ii++){
        memset(dp,-1,sizeof(dp));
        int k,r;
        cin >> k >> r;

        for(int i=0; i<k+2; i++){
            int x,y,z;
            cin >> x;
            for(int j=0; j<k+1; j++){
                cin >> y >> z;
                cost[x][y]=z;
            }
        }

        cout << "Case " << ii << ": " << rec(k,k+1,k+1)+r*(k+1) << endl;
    }
    return 0;
}