Tiệm Bánh

Bessie điều hành một tiệm bánh với một lò nướng. Lò có thể sản xuất bánh quy trong $t_C$ đơn vị thời gian hoặc bánh muffin trong $t_M$ đơn vị thời gian. Có $N$ người bạn đến lần lượt, người thứ $i$ đặt $a_i$ bánh quy và $b_i$ bánh muffin, và sẵn sàng chờ tối đa $c_i$ đơn vị thời gian.

Tổng thời gian sản xuất cho một đơn hàng là $a_i·t_C+b_i·t_M$. Bessie có thể dùng "moonies" để giảm thời gian sản xuất: mỗi moonie giảm $t_C$ hoặc $t_M$ đi 1 đơn vị (nhưng mỗi giá trị tối thiểu phải bằng 1). Việc giảm áp dụng cho tất cả đơn hàng.

Hãy tìm số moonies tối thiểu cần chi để phục vụ tất cả khách hàng trong giới hạn chờ đợi.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ ($1\le T\le 100$) — số bộ test.
• Mỗi bộ test:
  • Dòng đầu (sau dòng trống): Ba số nguyên $N$, $t_C$, $t_M$ ($1\le N\le 100$, $1\le t_C,t_M\le {10}^9$).
  • $N$ dòng tiếp theo: Ba số nguyên $a_i$, $b_i$, $c_i$ ($1\le a_i,b_i\le {10}^9$, $a_i+b_i\le c_i\le 2·{10}^{18}$).

Dữ liệu ra

Với mỗi bộ test, in số moonies tối thiểu trên một dòng.

Ràng buộc

• $1\le T\le 100$
• $1\le N\le 100$
• $1\le t_C,t_M\le {10}^9$
• $1\le a_i,b_i\le {10}^9$
• $a_i+b_i\le c_i\le 2·{10}^{18}$

Ví dụ