//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);
}
}
}