UVa 11218 - KTV

// UVa 11218 - KTV

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define datatype signed long long int

int main() {
	int n, m[81];
	datatype s[81];
	int t = 0;
	cin >> n;
	while (n) {
		t++;

		for (int i = 0; i < n; i++) {
			int a, b, c;
			cin >> a >> b >> c >> s[i];
			a--;
			b--;
			c--;
			m[i] = ((1 << a) | (1 << b) | (1 << c));

		}
		datatype T[512];
		memset(T, 127, sizeof(T));
		datatype oo = T[0];
		T[0] = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 512; j++) {
				if ((T[j] != oo) && ((m[i] & j) == 0) && (T[m[i] | j] == oo || T[m[i] | j] < T[j] + s[i])) {
					T[m[i] | j] = T[j] + s[i];
				}
			}
		}
		datatype sol = (T[511] == oo ? -1 : T[511]);
		printf("Case %d: %lld\n", t, sol);
		cin >> n;
	}
	return 0;
}