Description

对于一本共N（1 ≤ N ≤ 100,000）页的书，XX班的每个学生都需要读完它。XX班的学生有这样一个的规律，第i个学生每个分钟能读Si（1 ≤ Si ≤ 100）页书，且连续读书的最长时间为Ri (1 ≤ Ri ≤ 100)，一旦到达或中断时，必须至少休息Ti(1 ≤ Ti ≤ 100)分钟，才能继续读书。现在给定每个学生的Si,Ri，Ti,求每个学生读完N页的书的最少时间。

Format

Input

第一行为N，K.(N如题意，K代表有多少个学生，1 ≤ K ≤ 1,000) 以下共K行，每行为每个学生对应的Si,Ri,Ti。

Output

输出共K行，每行输出对应的学生的最少读书时间。

Samples

10 3
2 4 1
6 1 5
3 3 3

6
7
7

Limitation

1s, 1024KiB for each test case.