Untitled

package Lesson_15;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Hugo_Di_Tau {
	static int T, N, C;
	static int spots[];			// Trang thai ghe ngoi tren tau
	static boolean visited[];	// Status Gate đã đc duyệt hay chưa
	static int gates[][]; 		// So luong nguoi dang wait at Gate
	static int answer;
	
	//Ham kiem tra xem cong do da mo de nguoi vao het chua
	// True: Open - False: Close
	public static boolean isOpened(){
		for(int i = 0; i < 3; i++){
			if(!visited[i])	return false;
		}
		return true;
	}
	
	// Khoang cach tu cong do den vi tri ben phai gan nhat
	// Neu khong con cho ngoi ben phai thi tra ve gia tri rat lon
	public static int distanceToRightSpot(int start){
		for(int i = start; i <= N; i++){
			if(spots[i] == -1 ) return i - start;
		}
		return 1000000;
	}
	
	// Khoang cach tu cong do den vi tri ben trai gan nhat
	public static int distanceToLeftSpot(int start){
		for(int i = start; 1 <= i; i--){
			if(spots[i] == -1 ) return start - i;
		}
		return 1000000;
	}
	
	public static void backTrack(int sum){
		// Kiem tra cong da mo het chua ,neu da mo het tra ve gia tri
		if(isOpened()){
			if(answer > sum) answer = sum;
			return;
		}
		
		for(int i = 0; i < 3; i++){
			// Cong da dc mo thi bo qua
			if(visited[i]) continue;
			
			// Cong chua mo thi tham cong do va danh dau da tham
			visited[i] = true;
			
			int add = gates[i][1];
			
			// Xep het nguoi tai cong do vao vi tri. De lai 1 nguoi cuoi cung de check
			for(int j = 0; j < gates[i][1] - 1; j++){
				int left = distanceToLeftSpot(gates[i][0]); // Kc cong do den trai
				int right = distanceToRightSpot(gates[i][0]);
				
				// Kiem tra khoang cach khi them vao trai/ phai. Ben nao nho hon thi lay
				if(left  < right)
				{
					spots[gates[i][0] - left] = i;
					add += left;
				}
				else
				{
					spots[gates[i][0] + right] = i;
					add += right;
				}
			}
			
			// Tra ve khoang cach nguoi cuoi cung cua cong do so voi ben trai/ phai
			int left = distanceToLeftSpot(gates[i][0]);
			int right = distanceToRightSpot(gates[i][0]);
			
			// Neu khoang cach do khac nhau thi check xem ben trai hay phai nho hon de ta xep
			if(left != right)
			{
				if(left < right)
				{
					spots[gates[i][0] - left] = i;
					add += left;
				}
				else
				{
					spots[gates[i][0] + right] = i;
					add += right;
				}
				backTrack(sum + add);
			}
			// Neu khoang cach bang nhau thi can dat thu vao ca 2 ben trai va phai
			else
			{
				add += left;
				spots[gates[i][0] + right] = i;
				backTrack(sum + add);
				spots[gates[i][0] + right] = -1;
				
				spots[gates[i][0] - left] = i;
				backTrack(sum + add);
				spots[gates[i][0] -left] = -1;
			}
			
			// Tra lai cong chua tham de backTrack lai
			visited[i] = false;
			
			// Tra lai vi tri cong do da ngoi
			for(int j = 1; j <= N; j++){
				if(spots[j] == i) spots[j] = -1;
			}
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Hugo_Di_Tau"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			N = scanner.nextInt();
			gates = new int[3][2];
			for(int i = 0; i < 3; i++){
				gates[i][0] = scanner.nextInt();		// Vi tri cong
				gates[i][1] = scanner.nextInt();		// So luong nguoi trc cong
			}
			
			spots = new int[N+1];
			visited = new boolean[N+1];
			for(int i = 1; i <= N; i++){
				spots[i] = -1;
			}
			
			answer = 10000;
			backTrack(0);
			System.out.println("Case #"+ tc );
			System.out.println(answer);
		}
	}

}