Untitled

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

public class Solution {
	static int n, m, k, cost[], power[], in[], max, c, p, visit[], count[], t;

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		long startTime = System.nanoTime();
		System.setIn(new FileInputStream("src/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			m = sc.nextInt();
			n = sc.nextInt();
			k = sc.nextInt();
			cost = new int[k];
			power = new int[k];
			in = new int[k];
			for (int i = 0; i < k; i++) {
				cost[i] = sc.nextInt();
				power[i] = sc.nextInt();
				in[i] = sc.nextInt();
			}
			count = new int[k];
			max = c = p = t = 0;
			visit = new int[k];
			train(0, 0, 0, 0, 0);
			System.out.println("#" + tc + " " + max);
		}
		sc.close();
		long endTime = System.nanoTime();
		long elapsedTime = endTime - startTime;
		double seconds = (double) elapsedTime / 1_000_000_000.0;

		System.out.println("Execution Time: " + seconds + " seconds");
	}

	private static void train(int idx, int h, int t, int p, int c) {
		// TODO Auto-generated method stub
		if (c > m)
			return;
		if (h == n) {
			max = p > max ? p : max;
			return;
		}
		for (int i = 0; i < 2; i++) {
			if (i == 0) {
				for (int j = 0; j < k; j++) {
					if (visit[j] == 0) {
						visit[j] = 1;
						train(j, h + 1, t + in[j], p + power[j] + t, c + cost[j]);
						visit[j] = 0;
					}
				}
			} else {
				train(idx, h + 1, t, p + t, c);
			}
		}

	}
}