¡Bessie ha abierto una panadería!

En su panadería, Bessie tiene un horno que puede producir una galleta en ~t_C~ unidades de tiempo o un muffin en ~t_M~ unidades de tiempo ~(1 \leq t_C, t_M \leq 10^9)~. Debido a restricciones de espacio, Bessie puede producir solamente un tipo de producto a la vez, entonces producir ~A~ galletas y ~B~ muffins, le toma ~A*t_C+B*t_M~ unidades de tiempo.

A cada uno de los ~N (1 \leq N \leq 100)~ amigos de Bessie les gustaría visitar la panadería uno por uno. El amigo ~i~-ésimo ordenará ~a_i (1 \leq a_i \leq 10^9)~ galletas y ~b_i (1 \leq bi \leq 10^9)~ muffins inmediatamente después de llegar. Bessie no tiene espacio para guardar sus productos, entonces recién comienza a hacerlos después de recibir un pedido. Aún más, los amigos de Bessie son gente muy ocupada, entonces el amigo ~i~-ésimo solamente piensa esperar ~c_i (a_i + b_i \leq c_i \leq 2*10^{18})~ unidades de tiempo antes de ponerse triste e irse.

Bessie realmente no quiere que sus amigos se pongan tristes. Con un mooney, ella puede actualizar su horno de manera que le tome una unidad menos de tiempo para producir una galleta o un muffin. Ella no puede actualizar su horno una cantidad fraccionarioa de tiempos, pero ella puede elegir actualizar su horno tantas veces como ella necesite antes de que sus amigos lleguen, en tanto que el tiempo necesario para producir una galleta y para producir un muffin ambos permanezcan estrictamente positivos.

Para cada uno de ~T (1 \leq T \leq 100)~ casos de prueba, por favor ayude a Bessie ha encontrar la cantidad mínima de moonies que ella debe gastar de manera que su panadería pueda satisfacer a todos sus amigos.

Entrada

La primera línea contiene ~T~, el número de casos de prueba. Cada caso de prueba comienza con una línea conteniendo ~N~, ~t_C~, ~t_M~. Luego, cada una de las ~N~ líneas siguientes contiene tres enteros ~a_i~, ~b_i~, ~c_i~.

Salida

La cantidad mínima de mooney que Bessie necesita gastar para cada caso de prueba, en líneas separadas.

Ejemplo de Entrada

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

Ejemplo de Salida

11
6

En el primer caso, Bessie puede pagar 11 monedas para disminuir el tiempo requerido para producir una galleta en 4 y un muffin en 7, de manera que su horno produzca galletas en 3 unidades de tiempo y muffins en 2 unidades de tiempo. Entonces ellas puede satisfacer al primer amgio en 18 unidades de tiempo, al segundo amigo en 14 unidades de tiempo, y al tercer amigo en 5 unidades de tiempo, de manera que ninguno se ponga triste y se vaya.

En el segundo caso, Bessie debería disminuir el tiempo requerido para producir una galleta en 5 y un muffin en 0.