Untitled

Sau khi tham khảo thông tin Hugo biết được quãng đường cần chạy bộ D của cuộc thi. Nhân viên y tế có thể giúp Hugo tính toán được số năng lượng tối đa của Hugo.
Cho thông tin của 5 kiểu chạy của Hugo bao gồm số phút, số giây (số phút <= 6 và số giây <= 60) và số năng lượng tiêu tốn.
Hãy tính thời gian ngắn nhất để Hugo về đích mà không bị bệnh.

 

Input

Dòng đầu số test T (T<=50)

Mỗi test bao gồm 2 dòng

Dòng 1 chứa số năng lượng tối đa M <=60 và chiều dài quãng đường D<=40km
Dòng thứ 2 chứa thông tin của 5 kiểu chạy lần lượt là số phút, số giây, số năng lượng tiêu tốn

 

Output
In ra thời gian ngắn nhất để Hugo về đích mà không bị bệnh theo dạng số phút, số giây. Nếu không thể hãy in ra -1

 



#include<iostream>
using namespace std ;
int P, D ;
int map[2][5];
int currP, currtime, mintime ,currdis;
int distan[45];


void backtrack( int type){

	if(currtime >= mintime) return;

	if(currP > P) return  ;

	

	if(currdis == 0){
		mintime = mintime > currtime ? currtime : mintime	;
		return ;
	}
	
	if( type == 5) return;

	
	for( int i = 0; i <= D ;i++){
		if( i <= currdis){
			currdis -= i ;
			currtime += i*map[0][type];
			currP += i*map[1][type];
			backtrack(type + 1 );
			currdis += i ;
			currtime -= i*map[0][type];
			currP -= i*map[1][type];
		
		}
	
	}


};

int main(){
	freopen("input.txt" , "r" , stdin );
	int T ;
	cin >> T ;
	for( int tc =1 ; tc <= T ;tc++){
		cin >> P >> D ;
		for( int i = 0 ; i <5 ;i++){
			int x,y ;
			cin >> x >> y >> map[1][i];
			map[0][i] = 60*x + y ;
		}
		for( int i =0; i<= D ;i++){
			distan[i] = 0;
		}
	currP = 0;
	currtime = 0;
	mintime =1000000;
	currdis = D ;
	backtrack(0);
		cout << "Case #" << tc <<endl;
	if(mintime==1000000) cout << -1 <<endl;
	else cout << mintime/60 << " " << mintime%60 <<endl;
	}
return 0;
}