题目描述

SUA 程序设计竞赛命题组的裁判们正在为即将举行的 2024 中国大学生程序设计竞赛全国邀请赛（山东）暨 CCPC 山东省大学生程序设计竞赛打印试题。

文印店里共有 $n$ 台打印机。第 $i$ 台打印机每 $t_i$ 秒可以打印一份试题。然而，第 $i$ 台打印机每次打印出 $l_i$ 份试题后，必须停机 $w_i$ 秒防止过热。也就是说，第 $i$ 台打印机将重复进行以下工作计划：持续工作 $t_i \times l_i$ 秒，然后停机 $w_i$ 秒。

裁判们将同时使用所有打印机。求打印 $k$ 份试题至少需要多少秒。

输入格式

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 100$）表示测试数据组数，对于每组测试数据：

第一行输入两个整数 $n$ 和 $k$（$1 \le n \le 100$，$1 \le k \le 10^9$）表示打印机的数量和需要的试题数量。

对于接下来的 $n$ 行，第 $i$ 行输入三个整数 $t_i$，$l_i$ 和 $w_i$（$1 \le t_i, l_i, w_i \le 10^9$）。它们的意义如上所述。

输出格式

每组数据输出一行一个整数，表示打印试题至少需要多少秒。

2
3 15
3 4 5
5 7 2
1 2 20
1 100
1 1 100

25
10000

提示

对于第一组样例数据，在 $25$ 秒内，第一台打印机可以打印 $6$ 份试题，第二台打印机可以打印 $5$ 份试题，第三台打印机可以打印 $4$ 份试题。所以一共打印了 $6 + 5 + 4 = 15$ 份试题。