Untitled

#include <iostream>
using namespace std;
#define INT_MAX 999999999

int m, d; // m: max energy; d: distance;
int runType[5][3]; // runType[i][0] : minutes; runType[i][1] : seconds; runType[i][2] : energy;
int dp[45][605];

int solve(int dist, int energy) {
	if (dist == 0) {
		if (energy >= 0) {
			return 0;
		}
		else return INT_MAX; 
	}
	if (energy < 0) return INT_MAX;
	if (dp[dist][energy] != -1) return dp[dist][energy];
	int ans = INT_MAX;
	for (int i = 0; i < 5; i++) {
		int tmp = solve(dist-1,energy-runType[i][2]) + (runType[i][0]*60+runType[i][1]);
		ans = tmp < ans ? tmp : ans;
	}
	dp[dist][energy] = ans;
	return ans;
}

int main() {
	freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> m >> d;
		for (int i = 0; i < 5; i++) {
			cin >> runType[i][0] >> runType[i][1] >> runType[i][2];
		}
		// Can use memset(dp,-1,sizeof(dp)); instead but sever not allow
		for (int i = 0; i < 45; i++) {
			for (int j = 0; j < 605; j++) {
				dp[i][j] = -1;
			}
		}
		int res = solve(d,m);
		cout << "Case #" << tc << endl;
		if (res == INT_MAX) cout << -1 << endl;
		else cout << res / 60 << " " << res % 60 << endl;
	}
	return 0;
}