A. Printer
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Judges from the SUA Programming Contest Problem Setter Team are printing problem sets for the upcoming 2024 CCPC Shandong Invitational Contest and CCPC Shandong Provincial Collegiate Programming Contest.

There are $$$n$$$ printers in the printing shop. The $$$i$$$-th printer can produce one copy of the problem set every $$$t_i$$$ seconds. However, each time after producing $$$l_i$$$ copies from the $$$i$$$-th printer, it must halt for $$$w_i$$$ seconds to avoid overheating. That is to say, the $$$i$$$-th printer will repeat the following working schedule: Work continuously for $$$t_i \times l_i$$$ seconds, then halt for $$$w_i$$$ seconds.

The judges will use all printers at the same time. Calculate the minimum number of seconds needed to produce at least $$$k$$$ copies of the problem set.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 100$$$) indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le 10^9$$$) indicating the number of printers and the number of copies needed.

For the following $$$n$$$ lines, the $$$i$$$-th line contains three integers $$$t_i$$$, $$$l_i$$$, and $$$w_i$$$ ($$$1 \le t_i, l_i, w_i \le 10^9$$$). Their meanings are described above.

Output

For each test case, output one line containing one integer indicating the minimum number of seconds needed.

Example
Input
2
3 15
3 4 5
5 7 2
1 2 20
1 100
1 1 100
Output
25
10000
Note

For the first sample test case, in $$$25$$$ seconds, the first printer can produce $$$6$$$ copies, the second printer can produce $$$5$$$ copies, while the third printer can produce $$$4$$$ copies. So they can produce $$$6 + 5 + 4 = 15$$$ copies in total.