Hugo Thi Chay

package backtrack;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoThiChay {
	static int energy;
	static int distance;
	static int[][] runType;
	static int minTime;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int test_case = sc.nextInt();
		for (int tc = 1; tc <= test_case; tc++) {
			energy = sc.nextInt();
			distance = sc.nextInt();
			runType = new int[5][2];
			for (int i = 0; i < 5; i++) {
				int m = sc.nextInt();
				int s = sc.nextInt();
				int e = sc.nextInt();
				runType[i][0] = m * 60 + s;
				runType[i][1] = e;
			}
			minTime = 16800;
			backtrack(0,0, energy, 0);
			System.out.println("Case #" + tc);
			if (minTime == 16800) {
				System.out.println(-1);
			} else
				System.out.println(minTime / 60 + " " + minTime % 60);

		}

	}

	public static void backtrack(int localDistance,int index, int remainEnergy, int time) {
		if (time >= minTime)
			return;
		if(remainEnergy < 0 || index == 5) return;
		if (localDistance == distance) {
				minTime = Math.min(minTime, time);
				return;
		}
		for(int i = 0;i<2;i++){
			if(i == 0){
				backtrack(localDistance, index + 1, remainEnergy, time);
			}
			else{
				backtrack(localDistance + 1,index, remainEnergy - runType[index][1], time + runType[index][0]);
			}
		}
		

	}

}