Бесі відкрила пекарню!

Вона може робити печиво за \(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\) підтестів допоможіть Бесі обчислити мінімальна кількість муні, яку їй потрібно витратити так, щоб її пекарня могла задовольнити всіх друзів.

Формат вхідних даних

Перший рядок містить \(T\), кількість підтестів.

Кожен підтест починається з рядка, що містить \(N\), \(t_C\), \(t_M\). Потім слідують \(N\) рядків, кожен із яких містить три цілих числа \(a_i,b_i, c_i\).

Послідовні підтести розділені порожніми рядками.

Формат вихідних даних

Мінімальну кількість муні, які повинна витратити Бесі на кожен підтест в окремому рядку.

Приклад вхідних даних

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

У першому підтесті Бесі може заплатити 11 муні, щоб зменшити час, необхідний для випікання печива на 4 та булочок на 7, так що її піч змогла виробляти печиво за 3 одиниці часу, а булочку за 2 одиниці часу. Тоді вона зможе обслужити першого друга за 18 одиниць часу, а другого друга за 14 одиниць часу, і третього друга за 5 одиниць часу і ніхто з них не стане сумним і не піде, не поївши.

У другому підтесті Бесі має зменшити час, необхідний для виготовлення печива на 6 та булочок на 0.

ОЦІНЮВАННЯ:

• У тестах 2-4: \(N \leq 10, t_C, t_M \leq 1000\)
• У тестах 5-11: Немає додаткових обмежень.