该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

K (1 ≤ K ≤ 1,000) 头奶牛参加了 Farmer John 的年度阅读大赛。这个比赛的内容是读一本 N (1 ≤ N ≤ 100,000) 页的书，在理解它的情况下，比谁读的最快。

奶牛 i 的阅读速度为 Si (1 ≤ Si ≤ 100) 页每分钟，最长连续读书的时间为 Ti (1 ≤ Ti ≤ 100) 分钟，需要休息的时间为 Ri (1 ≤ Ri ≤ 100) 分钟。奶牛i只能一次连续读 Ti 分钟，接下来她必须休息 Ri 分钟，才能继续读书。

请你计算出每头奶牛读完书需要的时间，请向上保留到整数。

输入格式

输出格式

样例

10 3
2 4 1
6 1 5
3 3 3

6
7
7