Untitled

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int energy[5][2];
int nTestcase, M, D, hour, sec, minEnergy, minTime, mE;

void arrangeTime() {
	int temp;
	for (int i = 0; i < 4; i++) {
		for (int j = i + 1; j < 5; j++) {
			if (energy[i][0] > energy[j][0]) {
				temp = energy[j][0];
				energy[j][0] = energy[i][0];
				energy[i][0] = temp;

				temp = energy[j][1];
				energy[j][1] = energy[i][1];
				energy[i][1] = temp;
			}
		}
	}
}

void backtrack(int dist, int sumTime, int sumEnergy) {
	if (sumEnergy > M)
		return;
	if (sumTime >= minTime)
		return;
	if (dist == D) {
		minTime = minTime > sumTime ? sumTime : minTime;
		return;
	}
	for (int i = 0; i < 5; i++) {
		if(sumEnergy + energy[i][1] <= M)
			backtrack(dist + 1, sumTime + energy[i][0], sumEnergy + energy[i][1]);
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> nTestcase;
	for (int testcase = 1; testcase <= nTestcase; testcase++) {
		minEnergy = 10000;
		cin >> M >> D;
		for (int i = 0; i < 5; i++) {
			cin >> hour >> sec >> energy[i][1];
			if (energy[i][1] < minEnergy) {
				minEnergy = energy[i][1];
				mE = i;
			}
			energy[i][0] = hour * 60 + sec;
		}
		if (minEnergy * D > M) {
			cout << "Case #" << testcase << endl << -1 << endl;
		}
		else {
			minTime = energy[mE][0]*D;
			arrangeTime();
			backtrack(0,0,0);
			cout << "Case #" << testcase << endl << minTime / 60 << " " << minTime % 60 << endl;
		}
	}
	return 0;
}