贝茜开了一家面包店。

贝茜的面包店中只有一个烤箱，该烤箱制作一块饼干需要花费的时间为$t_c$ ，制作一块松饼需要花费的时间为 $t_m$。

烤箱每次只能制作一个糕点，也就是说制作 $A$ 块饼干和 $B$ 块松饼需要花费的时间为 $A×t_c+B×t_m$。

有 $N$ 个客人来光顾贝茜的生意，编号 $1∼N$。

客人是一个接着一个来的，并且第 $i+1$ 个客人一定会在第 $i$ 个客人走后才会来。

第 $i$ 个客人想要 $a_i$ 块饼干和 $b_i$ 块松饼。

为了保证售出糕点足够新鲜，贝茜一定会在客人下单后才开始现场制作其所需要的全部糕点。

每个客人的耐心都是有限的，对于第 $i$ 个客人，如果贝茜制作其所需全部糕点花费的总时间超过 $c_i$，那么它就会生气离开。

贝茜不希望得罪任何客人，在第 1 个客人到来之前，它可以选择对它的烤箱进行升级。

烤箱每升一级，可以进行如下选择：要么使得生产一块饼干所需的时间减少 1，要么使得生产一块松饼所需的时间减少 1。

请你计算，为了让所有客人都能满意，至少需要升多少级烤箱。

输入格式

第一行包含整数 $T$，表示共有 $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

提示

$1≤T≤100,$
$1≤N≤100,$
$1≤t_c,t_m≤10^9,$
$1≤a_i,b_i≤10^9,$
$a_i+b_i \leq ci ≤2×10^{18}$

样例解释

对于第一组数据，贝茜可以对烤箱进行 11 次升级，其中 4 次减少饼干制作时间，7 次减少松饼制作时间，升级过后制作一块饼干的时间为 3，制作一块松饼的时间为 2。

这样的话，完成第 1 个客人的订单需要花费的总时间为 18，完成第 2 个客人的订单需要花费的总时间为 14，完成第 3 个客人的订单需要花费的总时间为5，所有人都可以满意离开。

对于第二组数据，贝茜可以对烤箱进行6 次升级，全部用于减少饼干制作时间。