(Analysis by David Hu)

Suppose Bessie's oven ends up taking $x$ units of time to produce a cookie and $y$ units of time to produce an oven. Each of the $N$ cows can be viewed as a constraint $a_i \cdot x + b_i \cdot y \leq c_i$.

Note that for all $0 \leq w < t_C + t_M - 2$, if is possible to spend $i$ moonies and satisfy all the cows, then it is possible to spend $w + 1$ moonies. So we can binary search on the number of moonies Bessie will spend.

Suppose we would like to check if it is possible to spend $w$ moonies, where $0\le w\le t_C+t_M-2$. The answer is yes if and only if there exists an integer solution $(x, y)$ to the following system of inequalities:

$1 \leq x \leq t_C$

$1 \leq y \leq t_M$

$x + y = t_C + t_M - w$

$a_i \cdot x + b_i \cdot y \leq c_i$ (for all $i$).

By combining the last two inequalities, we can obtain that for any $i$, we must have:

$(a_i-b_i) \cdot x \leq c_i - b_i \cdot (t_C + t_M - w)$

Dividing through by $a_i - b_i$, we find that these inequalities are bounds on the range of possible values that $x$ can take. It can also be seen that the first two inequalities are also bounds on the possible values $x$ can take. So we can maintain lower and upper bounds on the possible values of $x$ in our binary search and return yes if these bounds produce a nonempty range for the possible values of $x$.

Make sure to handle the case $a_i = b_i$ correctly.

The overall time complexity is $O(N \log (t_C + t_M))$.

My Python code:

TC = int(input())

for tc in range(TC):
_ = input()

N, X, Y = map(int, input().split())

A, B, C = [0 for i in range(N)], [0 for i in range(N)], [0 for i in range(N)]

for i in range(N):
A[i], B[i], C[i] = map(int, input().split())

def check(w):
#1 <= x <= X
#1 <= y <= Y
#x + y = X + Y - w
#x = X + Y - y - w
lx, hx = max(1, X - w), min(X + Y - w - 1, X)
for i in range(N):
a, b, c = A[i], B[i], C[i]
d = X + Y - w
#a * x + b * y <= c
#x + y = d = (X + Y - w)
#-b * x - b * y <= -b * d
#(a-b) * x <= c - b * d
if (b - a > 0):
lx = max(lx, (-c + b * d + (b - a - 1)) // (b - a))
elif (a - b > 0):
hx = min(hx, (c - b * d) // (a - b))
else:
if (a * d > c):
return False
return (lx <= hx)

lo = 0
hi = X + Y - 2

while(hi > lo):
mid = (lo + hi) // 2
if (check(mid)):
hi = mid
else:
lo = mid + 1

print(lo)