题目描述

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

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

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

输入

第 $1$ 行: 两个整数 $N$ , $K$

第 $2 \dots K+1$ 行: 第 $i+1$ 行 包含三个整数: $Si$ , $Ti$ , $Ri$

输出

第 $1 \dots K$ 行: 第 $i$ 行为一个整数，表示奶牛读完书需要的时间，向上保留到整数。

样例

10 3
2 4 1
6 1 5
3 3 3

6
7
7

来源

二维数组