SUA 编程竞赛命题组的评委们正在为即将到来的 2024 CCPC 山东邀请赛和 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$)，其含义如上所述。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示所需的最少秒数。

样例

样例输入 1

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

样例输出 1

25
10000

说明

对于第一个样例测试数据，在 25 秒内，第一台打印机可以生产 6 份，第二台打印机可以生产 5 份，而第三台打印机可以生产 4 份。因此，它们总共可以生产 $6 + 5 + 4 = 15$ 份。