Untitled

public class Solution {

	static Scanner sc;
	static Type[] runs;
	static boolean[] visited;
	static int minTime = 0;
	static int M, D;

	static public void main(String[] args) throws Exception {
		sc = new Scanner(System.in);

		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			M = sc.nextInt();
			D = sc.nextInt();

			runs = new Type[5];
			visited = new boolean[6];
			minTime = 99999;

			for (int i = 0; i < 5; i++) {
				int mm = sc.nextInt();
				int ss = sc.nextInt();
				int mana = sc.nextInt();
				runs[i] = new Type(mm * 60, ss, mana);
			}

			// so thu tu chay, mana, quang duong
			backtrack(0, 0, M, 0);
			System.out.print("Case #" + tc + "\n");
			if (minTime == 99999) {
				System.out.println(-1);
			} else {
				int mM = minTime / 60;
				int sS = minTime % 60;
				System.out.println(mM + " " + sS);
			}
		}
	}

	private static void backtrack(int lc, int index, int energy, int time) {
		// dieu kien dung
		if (minTime <= time) {
			return;
		}

		if (energy < 0) {
			return;
		}

		if (index == 5) {
			return;
		}

		if (lc == D) {
			minTime = Math.min(minTime, time);
			return;
		}

		for (int i = 0; i <= 1; i++) {
			if (i == 0) {
				backtrack(lc, index + 1, energy, time);
			} else {
				int mana = runs[index].mana;
				int nTime = runs[index].mm + runs[index].ss;
				backtrack(lc + 1, index, energy - mana, time + nTime);
			}
		}
	}

	static class Type {
		int mm, ss, mana;

		public Type(int mm, int ss, int mana) {
			this.mm = mm;
			this.ss = ss;
			this.mana = mana;
		}
	}
}