You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

限制

• 时间限制：$1s$
• 空间限制：$256M$

题目描述

期末考试快到了，文印店正在打印正在打印试题，文印店有$n$台打印机。第$i$台打印机每$t_i$秒可以打印一份试题，但每打印$l_i$份后必须停机$w_i$秒防止过热。即第$i$台打印机的工作计划为：持续工作$t_i×l_i$秒，然后停机$w_i$秒，循环进行。老师同时使用所有打印机，求打印$k$份试题至少需要多少秒。

输入格式

• 第一行输入两个整数$n$和$k$ $（1 \le n \le 100，1 \le k \le 10^9）$。
• 接下来$n$行，每行输入三个整数$t_i、l_i、w_i$（$1 \le t_i, l_i, w_i \le 10^9）$，表示第$i$台打印机的参数。

输出格式

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

样例1

输入

3 15
3 4 5
5 7 2
1 2 20

输出

25

样例2

输入

1 100
1 100 1

输出

100

样例解释

• 第一组样例中，$25$ 秒内三台打印机分别打印 $6、5、4$份，总计$15$份。
• 第二组样例中，仅有一台打印机，打印$100$份需$1×100=100$秒（无需停机，因$l_i=1$，打印$1$份后停机，但$k=100$刚好在一次工作周期内完成）。

数据分布

$40\%$ 的样例，保证 $（1 \le n \le 10，1 \le k \le 1000）$。$t_i、l_i、w_i$（$1 \le t_i, l_i, w_i \le 1000）$，

$100\%$ 的样例，保证 $（1 \le n \le 100，1 \le k \le 10^9）$。$t_i、l_i、w_i$（$1 \le t_i, l_i, w_i \le 10^9）$，