SUA 程序设计竞赛命题组的裁判们正在为即将举行的 2024 中国大学生程序设计竞赛全国邀请赛（山东）暨 CCPC 山东省大学生程序设计竞赛打印试题。
文印店里共有 台打印机。第 台打印机每 秒可以打印一份试题。然而，第 台打印机每次打印出 份试题后，必须停机 秒防止过热。也就是说，第 台打印机将重复进行以下工作计划：持续工作 秒，然后停机 秒。
裁判们将同时使用所有打印机。求打印 份试题至少需要多少秒。
有多组测试数据。第一行输入一个整数 （）表示测试数据组数，对于每组测试数据：
第一行输入两个整数 和 （，）表示打印机的数量和需要的试题数量。
对于接下来的 行，第 行输入三个整数 ， 和 （）。它们的意义如上所述。
每组数据输出一行一个整数，表示打印试题至少需要多少秒。
2 3 15 3 4 5 5 7 2 1 2 20 1 100 1 1 100
25 10000
对于第一组样例数据，在 秒内，第一台打印机可以打印 份试题，第二台打印机可以打印 份试题，第三台打印机可以打印 份试题。所以一共打印了 份试题。
