// Arup Guha
// 4/13/2018
// Solution to 2018 Code Jam Round 1A Problem: Bit Party
// Written in contest, commented later.

import java.util.*;

public class Solution {

	public static int numRobots;
	public static long bits;
	public static int numCash;
	public static cashier[] list;
	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();

		// Process each case.
		for (int loop=1; loop<=nC; loop++) {

			numRobots = stdin.nextInt();
			bits = stdin.nextLong();
			numCash = stdin.nextInt();

			// Read the data.
			list = new cashier[numCash];
			for (int i=0; i<numCash; i++) {
				long m = stdin.nextLong();
				long s = stdin.nextLong();
				long p = stdin.nextLong();
				list[i] = new cashier(m,s,p);
			}

			// Solve via binary search.
			System.out.println("Case #"+loop+": "+binSearch());

		}
	}

	public static long binSearch() {

		// Make a note of high, the bound must be strictly greater than 10^18.
		long low = 0L, high = 2000000000000000000L;

		// Usual binary search.
		while (low < high) {

			long mid = (low+high)/2;

			if (canDo(mid))
				high = mid;
			else
				low = mid+1;
		}

		return low;
	}

	public static boolean canDo(long t) {

		ArrayList<Long> items = new ArrayList<Long>();

		// Figure out the max # of items here per robot.
		for (int i=0; i<numCash; i++) {
			long limit = (t-list[i].extra)/list[i].sec;
			limit = Math.min(limit, list[i].max);
			items.add(limit);
		}

		// Sort from most to least.
		Collections.sort(items);
		Collections.reverse(items);

		// Now, just take the "best" shoppers.
		long total = 0;
		for (int i=0; i<items.size() && i<numRobots; i++) {
			total += items.get(i);
			if (total >= bits) return true;
		}

		// If we get here, we didn't get enough items.
		return false;
	}
}

class cashier {

	public long max;
	public long sec;
	public long extra;

	public cashier(long m, long s, long p) {
		max = m;
		sec = s;
		extra = p;
	}
}