Untitled

//Hugo thi chay
package HugoThiChay;

import java.util.Scanner;

public class test {
static int Power,S;
static int[][] KieuChay=new int[5][3];
static int ans=0;
//backtrack
static void backtrack(int k,int time,int nl) {
	if(k==S && nl<=Power) {
		if(time<ans) {
			ans=time;
		}
		return;
	}
	if(nl>=Power) {
		return;
	}
	if(time>=ans) {
		return;
	}
	for(int i=0;i<5;i++) {
		backtrack(k+1, time+60*KieuChay[i][0]+KieuChay[i][1],nl+KieuChay[i][2]);
	}
}
public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	int tc=sc.nextInt();
	for(int i=0;i<tc;i++) {
		Power=sc.nextInt();
		S=sc.nextInt();
		for(int j=0;j<5;j++) {
			for(int k=0;k<3;k++) {
				KieuChay[j][k]=sc.nextInt();
			}
		}
		ans=999999999;
		backtrack(0, 0, 0);
		if(ans!=999999999) {
			System.out.println("Case #"+(i+1));
			System.out.println(ans/60+" "+ans%60);
		}
		else {
			System.out.println(-1);
		}
	}
}
}


//Hugo giao hang
package HugoGiaoHang;

import java.util.Scanner;

public class test {
static int x1,y1,x2,y2;
static int N;
static int ans=0;
static int[] ToaDoX=new int[100];
static int[] ToaDoY=new int[100];
static int[][] dis=new int[100][100];
static int[][] mindis=new int[100][100];
static int[] visit=new int[100];

static int Distance(int a1,int b1,int a2,int b2) {
	int sum=0;
	if(a1>a2) {
		sum+=a1-a2;
	}
	else {
		sum+=a2-a1;
	}
	if(b1>b2) {
		sum+=b1-b2;
	}
	else {
		sum+=b2-b1;
	}
	return sum;
}
static void reset() {
	for(int j=0;j<=N;j++) {
		for(int k=0;k<=N;k++) {
			dis[j][k]=0;
		}
	}
}
//static void Dijsktra(int n) {
//	for(int i=0;i<N+2;i++) {
//		mindis[n][i]=999999;
//		visit[i]=0;
//	}
//	mindis[n][n]=0;
//	int minPoint;
//	int minVal;
//	for(int i=0;i<N+2;i++) {
//		minPoint=-1;
//		minVal=999999;
//		for(int j=0;j<=N+1;j++) {
//			if(visit[j]==0 && mindis[n][j]<minVal) {
//				minVal=mindis[n][j];
//				minPoint=j;
//			}
//		}
//		visit[minPoint]=1;
//		int tmp;
//		for(int j=0;j<N+2;j++) {
//			tmp=minVal+dis[minPoint][j];
//			if(visit[j]==0 && tmp<mindis[minPoint][j]) {
//				mindis[minPoint][j]=tmp;
//			}
//		}
//	}
//}
static void backtrack(int point,int sum,int k) {
	if(point==N+1) {
		if(sum+Distance(x2, y2, ToaDoX[k], ToaDoY[k])<ans) {
			ans=sum+Distance(x2, y2, ToaDoX[k], ToaDoY[k]);
		}
		return;
	}
	if(sum>ans) {
		return;
	}
	for(int j=0;j<N+1;j++) {
		if(visit[j]==0) {
		visit[j]=1;
		backtrack(point+1, sum+dis[k][j],j);
		visit[j]=0;
		}
	}
}
public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	int tc=sc.nextInt();
	for(int i=0;i<tc;i++) {
		x1=sc.nextInt();
		y1=sc.nextInt();
		x2=sc.nextInt();
		y2=sc.nextInt();
		N=sc.nextInt();
		for(int j=1;j<=N;j++) {
			ToaDoX[j]=sc.nextInt();
			ToaDoY[j]=sc.nextInt();
		}
		ToaDoX[0]=x1;
		ToaDoY[0]=y1;
		reset();
		for(int j=0;j<N;j++) {
			for(int k=j+1;k<=N;k++) {
				dis[j][k]=Distance(ToaDoX[j], ToaDoY[j], ToaDoX[k], ToaDoY[k]);
				dis[k][j]=dis[j][k];
			}
		}
		ans=999999;
		backtrack(0, 0, 0);
		System.out.print("Case #"+(i+1)+" ");
		System.out.println(ans);
	}
}
}