All K (1 <= K <= 1,000) of the cows are participating in FarmerJohn’s annual reading contest. The competition consists of reading a single book with N (1 <= N <= 100,000) pages as fast as possible while understanding it.

Cow i has a reading speed S_i (1 <= S_i <= 100) pages per minute,a maximum consecutive reading time T_i (1 <= T_i <= 100) minutes,and a minimum rest time R_i (1 <= R_i <= 100) minutes. The cow can read at a rate of S_i pages per minute, but only for T_i minutes

at a time. After she stops reading to rest, she must rest for R_i minutes before commencing reading again.

Determine the number of minutes (rounded up to the nearest full minute) that it will take for each cow to read the book.

输入格式

• Line 1: Two space-separated integers: N and K

• Lines 2..K+1: Line i+1 contains three space-separated integers: S_i, T_i, and R_i

输出格式

• Lines 1..K: Line i should indicate how many minutes (rounded up tothe nearest full minute) are required for cow i to read the whole book.

样例

Input
10 3
2 4 1
6 1 5
3 3 3
INPUT DETAILS:
The book has 10 pages; 3 cows are competing. The first cow reads at a rate of 2 pages per minute, can read for at most 4 minutes at a time, and must rest for 1 minute after reading. The second reads at a rate of 6 pages per minute, can read for at most 1 minute at a time, and must rest 5 minutes after reading. The last reads at a rate of 3 pages per minute, can read for at most 3 minutes at a time, and must rest for 3 minutes after reading.

Output
6
7
7
OUTPUT DETAILS:
The first cow can read 8 pages in 4 minutes, rest for 1 minute, and read the last 2 pages in a minute. The second reads 6 pages in a minute, rests for 5 minutes, and finishes in the next minute. The last reads 9 pages in 3 minutes, rests for 3 minutes, and finishes
in the next minute.


82 人解决，92 人已尝试。

97 份提交通过，共有 199 份提交。

2.8 EMB 奖励。