베시는 빵집을 열었다!

베시의 빵집에는 쿠키 하나를 만드는 데 \(t_C\)의 시간이 걸리고, 머핀 하나를 만드는 데 \(t_M\)의 시간이 걸리는 오븐이 있다. \((1 \le t_C,t_M \le 10^9)\) 공간이 부족하여 한 번에 빵 하나만 만들 수 있으므로, 쿠키 \(A\)개와 머핀 \(B\)개를 만드는 데에는 \(A \times t_C+B \times t_M\)의 시간이 걸린다.

베시의 친구 \(N\)명이 한 명씩 차례대로 빵집을 방문하려고 한다. \((1 \le N \le 100)\) \(i\)번째 친구는 들어오자마자 쿠키 \(a_i\)개와 머핀 \(b_i\)개를 주문한다. \((1 \le a_i,b_i \le 10^9)\) 베시는 빵을 보관할 공간이 없으므로 주문을 받은 뒤에야 빵을 만들기 시작한다. 친구들은 매우 바쁘기 때문에, \(i\)번째 친구는 최대 \(c_i\)만큼만 기다리며 그 안에 주문을 받지 못하면 슬퍼하며 떠난다. \((a_i+b_i \le c_i \le 2 \times 10^{18})\)

베시는 친구들을 슬프게 하고 싶지 않다. 베시는 \(1\)무니를 사용하여 쿠키 하나를 만드는 시간 또는 머핀 하나를 만드는 시간 중 하나를 \(1\)만큼 줄일 수 있다. 오븐을 정수가 아닌 횟수만큼 개선할 수는 없다. 친구들이 도착하기 전에 필요한 만큼 개선할 수 있지만, 쿠키와 머핀을 만드는 시간은 모두 양의 정수로 남아 있어야 한다.

각 테스트 케이스에 대하여, 모든 친구의 주문을 제한 시간 안에 완성하기 위해 베시가 사용해야 하는 무니의 최솟값을 구하여라.

입력

첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다. \((1 \le T \le 100)\)

각 테스트 케이스의 첫째 줄에는 \(N\), \(t_C\), \(t_M\)이 공백으로 구분되어 주어진다.

다음 \(N\)개의 줄에는 세 정수 \(a_i\), \(b_i\), \(c_i\)가 공백으로 구분되어 주어진다.

연속한 두 테스트 케이스는 빈 줄로 구분된다.

출력

각 테스트 케이스마다 베시가 사용해야 하는 무니의 최솟값을 한 줄에 하나씩 출력한다.

예제 입력 1

2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

예제 출력 1

11
6

예제 설명 1

첫 번째 테스트 케이스에서 베시는 \(11\)무니를 사용하여 쿠키 하나를 만드는 시간을 \(4\)만큼, 머핀 하나를 만드는 시간을 \(7\)만큼 줄일 수 있다. 그러면 쿠키 하나는 \(3\)의 시간, 머핀 하나는 \(2\)의 시간에 만들 수 있다. 세 친구의 주문을 완성하는 데에는 각각 \(18\), \(14\), \(5\)의 시간이 걸리므로 아무도 슬퍼하며 떠나지 않는다.

두 번째 테스트 케이스에서는 쿠키 하나를 만드는 시간을 \(6\)만큼 줄이고 머핀 하나를 만드는 시간은 줄이지 않는 것이 최적이다.

출처

USACO 2023 February Contest, Silver, Problem 1. Bakery