K (1 <= K <= 1,000)头奶牛一起参加一年一度的读书比赛。比赛内容是尽可能快地读懂一本N (1 <= N <= 100,000)页的书。 奶牛i每分钟能读懂S_i (1 <= S_i <= 100)页书，奶牛连续读书T_i (1 <= T_i <= 100)分钟就至少要休息R_i (1 <= R_i <= 100)分钟。 求出每头奶牛读完这本书的最少分钟数。

第1行：两个用空格隔开的整数：N和K 第2..K+1行：第i+1行包含三个且空格隔开的整数：S_i,T_i和R_i

第1..K行:第i行将输出第i头奶牛读完整本书的所需的最少分钟数

10 3
2 4 1
6 1 5
3 3 3

6
7
7