Bessie vừa mở một tiệm bánh!

Trong tiệm bánh của mình, Bessie có một lò nướng có thể làm một chiếc bánh quy trong \(t_C\) giây hoặc một chiếc bánh nướng xốp trong \(t_M\) giây \((1\leq t_C,t_M\leq10^9)\). Do hạn chế về không gian, Bessie chỉ có thể làm một chiếc bánh ngọt mỗi lần, vì vậy để làm \(A\) bánh quy và \(B\) bánh nướng xốp, phải mất \(A*t_C+B*t_M\) giây.

\(N(1 \leq N \leq 100)\) người bạn của Bessie muốn lần lượt tham quan tiệm bánh. Người bạn thứ \(i\) sẽ gọi \(a_i\) \((1 \leq a_i \leq 19^9)\) bánh quy và \(b_i(1 \leq b_i \leq 10^9)\) bánh nướng xốp ngay khi bước vào. Bessie không có chỗ để đựng bánh ngọt nên nó chỉ bắt đầu làm bánh ngọt khi nhận được đơn đặt hàng. Hơn nữa, bạn bè của Bessie rất bận rộn nên người bạn thứ \(i\) chỉ sẵn lòng đợi \(c_i(a_i+b_i<c_i<2*10^{18})\) giây, nếu không sẽ trở nên buồn bã và rời đi.

Bessie không muốn bạn bè mình phải buồn. Với một mặt trăng, nó có thể nâng cấp lò nướng của mình để giảm \(1\) giây làm một chiếc bánh quy hoặc giảm \(1\) giây làm một chiếc bánh nướng xốp. Nó chỉ có thể nâng cấp lò nướng trong một lượng số tự nhiên giây, và nó có thể nâng cấp lò nướng vô số lần trước khi bạn bè đến, miễn là thời gian cần thiết để làm bánh quy và bánh nướng xốp luôn dương

Với mỗi test \(T(1 \leq T \leq 100)\), hãy giúp Bessie tìm ra số mặt trăng tối thiểu mà Bessie phải bỏ ra để tiệm bánh của nó có thể làm hài lòng tất cả bạn bè.

Input

• Dòng đầu tiên chứa \(T\), số lượng test.
• Mỗi test bắt đầu bằng một dòng chứa \(N,t_C,t_M\). Sau đó, \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i,b_i,c_i\).
• Các test liên tiếp cách nhau bởi dòng mới.

Output

Số lượng mặt trăng tối thiểu mà Bessie cần dành cho mỗi test trên các dòng riêng biệt.

Scoring

• Subtask \(1\): \(N \leq 10;t_c,t_m\leq1000\).
• Subtask \(2\): Không có điều kiện gì thêm.

Example

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

11
6