UVa 11218 - KTV

// aarifshuvo   ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++) 

#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

struct DT
{
    ll a,b,c,s;
} ar[82];

ll vis[10];

int main()
{
    ll n, t, id, cs=0;

    while(scl(n)==1 and n)
    {
        ll mx = 0, sm = 0;

        REP(i,n)
        {
            scll(ar[i].a,ar[i].b);
            scll(ar[i].c,ar[i].s);
        }

        for(int i=0; i<n-2; i++)
        {
            vis[ar[i].a]++,vis[ar[i].b]++,vis[ar[i].c]++;
            sm += ar[i].s;

            for(int j=i+1; j<n-1; j++)
            {
                if(vis[ar[j].a]==0 && vis[ar[j].b]==0 && vis[ar[j].c]==0)
                {
                    vis[ar[j].a]++,vis[ar[j].b]++,vis[ar[j].c]++;
                    sm += ar[j].s;

                    for(int k=j+1; k<n; k++)
                    {
                        if(vis[ar[k].a]==0 && vis[ar[k].b]==0 && vis[ar[k].c]==0)
                        {
                            vis[ar[k].a]++,vis[ar[k].b]++,vis[ar[k].c]++;
                            sm += ar[k].s;

                            mx = max(mx,sm);

                            sm -= ar[k].s;
                            vis[ar[k].a]--,vis[ar[k].b]--,vis[ar[k].c]--;
                        }
                    }
                    sm -= ar[j].s;
                    vis[ar[j].a]--,vis[ar[j].b]--,vis[ar[j].c]--;
                }
            }
            sm -= ar[i].s;
            vis[ar[i].a]--,vis[ar[i].b]--,vis[ar[i].c]--;
        }

        printf("Case %lld: ", ++cs);

        if(mx==0) mx=-1;

        printf("%lld\n", mx);
    }
    return 0;
}