Untitled

#include<iostream>
using namespace std;
int N;
int time[50][2];
int ads[2][3]; // luu do dai ads va diem cua tung ads
int kq, min_time, max_time;
int plan[2][3];  // luu ke hoach mo cac ads, hang dau la start time, hang sau la end time
void reset_plan(){
	for(int i = 0; i < 3; i++){
		plan[0][i] = plan[1][i] = 0;
	}
}

bool check(int start, int end){
	for(int i = 0; i < 3; i++){
		if(start> plan[0][i] && start < plan[1][i]) return false;
		if(end > plan[0][i] && end < plan[1][i]) return false;
		if(plan[0][i] > start && plan[0][i] < end) return false;
		if(plan[1][i] > start && plan[1][i] < end) return false;
	}
	return true;
}
void set(int start, int end, int i){
	plan[0][i] = start;
	plan[1][i] = end;
}
void unset( int i){
	plan[0][i] = 0;
	plan[1][i] = 0;
}

int tinh_tong(){
	int sum = 0;
	for(int i = 0; i < N; i++){
		int max_point = 0;
		for(int j = 0; j < 3; j++){
			if(time[i][0] <= plan[0][j] && time[i][0] + time[i][1] >= plan[1][j]) { // xem thoa man tgian ko
				if(ads[1][j] > max_point) max_point = ads[1][j];
			}
		}
		sum += max_point;
	}
	return sum;
}



void backtrack(int i){ //backtrack tung ads 
	if(i ==3){
		int tong = tinh_tong();
		if(tong > kq) kq =tong;
		return;
	}
	for(int h = min_time; h <= 50; h++){ // check tung khoang tgian co the bat dau cua tung ads tu min_time den 50
		if(check(h, h + ads[0][i])){ //check xem ads day co the dat trong tgian tu h den h + ads[0][i] khong
			set(h,h+ads[0][i],i); // neu co the thi dat tgian bat dau la h, tgian ket thuc la h + ads[0][i]
			backtrack(i+1);
			unset(i);
		}
	}
}



int main(){
	int test;
	cin>> test;
	for(int tc = 1; tc <= test; tc++){
		cin >> N ;
		for(int i = 0; i < 3; i++){
			cin >> ads[0][i]; //do dai
		}
		for(int i = 0; i < 3; i++){
			cin >> ads[1][i]; // diem
		}
		for (int i = 0; i< N ; i++){
			cin >> time [i][0] >> time[i][1]; // dau tien la tgian vao, sau la tgian luu tru
		}
		min_time = 100000;
		max_time = 0;
		for(int i = 0; i < N; i++){  // tim tgian vao som nhat va tgian ra muon nhat cua tat ca cac khach
			if(time[i][0] < min_time) min_time = time[i][0];
			if( time[i][0] + time[i][1] > max_time) max_time = time[i][0] + time[i][1] ;
		}
		kq = 0;
		reset_plan();
		backtrack(0);
		cout << "Case #"<< tc << endl;
		cout << kq<<endl;	
		
	}
	return 0;
}