打印机

题目描述

打印车间有 $n$ 台打印机。 $i$ （台）打印机每 $t_i$ 秒可以打印一份问题集。然而，每当第 $i$ 台打印机打印出 $l_i$ 份副本后，必须停止 $w_i$ 秒以避免过热。也就是说， $i$ /th 打印机将重复以下工作计划：连续工作 $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

样例输入 #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$ 份。