Untitled

#include <iostream>
using namespace std;
#define MAX 100000

struct Gate{
	int vt;
	int guest;
};

Gate gate[5];
int N, gateVisited[5], slot[100], kc[100];
int res;

bool checkAllGate() {
	for (int i = 0; i < 3; i++) {
		if (gateVisited[i] == 0)
			return false;
	}
	return true;
}

void backTrack(int sum) {
	if (sum > res)
		return;
	if (checkAllGate()) {
		res = std::min(res, sum);
		return;
	}
	for (int i = 0; i < 3; i++) {
		if (gateVisited[i] == 1) continue;
		gateVisited[i] = 1;
		int vt = gate[i].vt;
		int guest = gate[i].guest;
		int numSpace = 1;
		int distance = 0;
		while (guest > 0) {
			if (guest > 0 && vt + distance <= N) {
				if (slot[vt + distance] == -1) {
					slot[vt + distance] = i;
					kc[vt + distance] = numSpace;
					sum += kc[vt + distance];
					guest--;
				}
			}
			if (guest > 0 && vt + distance >= -1){
				if (slot[vt - distance] == -1) {
					slot[vt - distance] = i;
					kc[vt - distance] = numSpace;
					sum += kc[vt - distance];
					guest--;
				}
			}
			numSpace++;
			distance++;
		}
		if (guest == 0 ) backTrack(sum);
		for (int j = 1; j <= N; j++) {
			if (slot[j] == i) {
				slot[j] = -1;
				sum -= kc[j];
				kc[j] = 0;
			}
		}
		vt = gate[i].vt;
		guest = gate[i].guest;
		numSpace = 1;
		distance = 0;
		while (guest > 0) {
			if (guest > 0 && vt + distance >= -1){
				if (slot[vt - distance] == -1) {
					slot[vt - distance] = i;
					kc[vt - distance] = numSpace;
					sum += kc[vt - distance];
					guest--;
				}
			}
			if (guest > 0 && vt + distance <= N) {
				if (slot[vt + distance] == -1) {
					slot[vt + distance] = i;
					kc[vt + distance] = numSpace;
					sum += kc[vt + distance];
					guest--;
				}
			}
			numSpace++;
			distance++;
		}
		if (guest == 0 ) backTrack(sum);
		for (int j = 1; j <= N; j++) {
			if (slot[j] == i) {
				slot[j] = -1;
				sum -= kc[j];
				kc[j] = 0;
			}
		}
		gateVisited[i] = 0;
	}
}
int main() {
	//freopen("in.txt", "r", stdin);
	int T;
	cin >> T;
	int tc = 1;
	while(T--) {
		cin >> N;
		for (int i = 0; i < 3; i++) {
			cin >> gate[i].vt >> gate[i].guest;
			gateVisited[i] = 0;
		}
		for (int i = 1; i < N; i++){
			slot[i] = -1;
			kc[i] = 0;
		}
		res = MAX;

		backTrack(0);

		cout << "Case #" << tc++ << endl << res << endl;
	}
	return 0;
}