Беси открыла пекарню!
Она может делать печенье за \(t_C\) единиц времени или булочку за \(t_M\)
единиц времени (\(1\le t_C,t_M\le 10^9\)). В каждый момент времени она может делать
только один вид выпечки, поэтому чтобы произвести \(A\) печенек и \(B\) булочек,
её требуется \(A \cdot t_C + B \cdot t_M\) единиц времени.
У Беси есть \(N\) (\(1\le N\le 100\)) друзей, которые любят заглядывать в пекарню
по одному. \(i\)-ый друг делает заказ на \(a_i\) (\(1 \leq a_i\leq 10^9\)) печенек и
\(b_i\) (\(1 \leq b_i \leq 10^9\)) булочек немедленно после входа. У Беси нет места
хранить выпечку, поэтому она начинает изготовление сразу после получения заказа.
Кроме того, друзья Беси очень заняты и не могут ждать более \(c_i\) (\(a_i + b_i \leq c_i \leq 2 \cdot 10^{18}\))
единиц времени, после чего печалятся и уходят.
Беси не хочет огорчать своих друзей. За один муни она может апгрейдить
свою печь, чтобы печь печенье на одну единицу времени меньше или печь булочку
на одну единицу времени меньше. Она не может апгрейдить печь на дробное количество
времени, но она может апргрейдить печь сколько хочет раз прежде чем придут друзья,
при этом время на изготовление печенек и булочек должно оставаться строго положительным.
Для каждого из \(T\) (\(1 \leq T \leq 100\) подтестов помогите Беси вычислить
минимальное количество муни, которое ей требуется потратить так, чтобы её пекарня
могла удовлетворить всех друзей.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\), количество подтестов.
Каждый подтест начинается со строки, содержащей \(N\), \(t_C\), \(t_M\).
Затем следуют \(N\) строк, каждая из которых содержит три целых числа \(a_i,b_i, c_i\).
Последовательные подтесты разделены пустыми строками.
ФОРМАТ ВЫВОДА (на экран / stdout):
Минимальное количество муни, которые должна потратить Беси на каждый подтест на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
11
6
|