day190824

package d1908;

import java.util.Scanner;

public class HugoThiChay {
	static int t, m, d;
	static int[][] a = new int[5][3];
	static int res = 10000000;

	public static void Try(int cach, int cntKm, int cntNangluong, int cntTime) {
		if(cach == 5){
			if(res > cntTime && cntKm == 0 && cntNangluong <= m){
				res = cntTime;
			}
			return;
		}
		if(cntNangluong > m){
			return;
		}
		if(res < cntTime){
			return;
		}
		for(int i = 0 ; i <= cntKm ; i++){
			Try(cach+1, cntKm-i, cntNangluong+i*a[cach][2], cntTime+i*(a[cach][0]*60+a[cach][1]));
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			m = sc.nextInt();
			d = sc.nextInt();
			for (int i = 0; i < 5; i++) {
				a[i][0] = sc.nextInt();
				a[i][1] = sc.nextInt();
				a[i][2] = sc.nextInt();
			}
			res = 10000000;
			Try(0, d, 0, 0);
			System.out.println("Case #" + tc);
			if (res == 10000000) {
				System.out.println(-1);
			} else {
				System.out.println(res / 60 + " " + res % 60);
			}

		}
	}

}