All K (1 <= K <= 1,000) of the cows are participating in Farmer John'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.</p>

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 minute sat 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
</ul>

 

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

예제 입력

10 3
2 4 1
6 1 5
3 3 3

예제 출력

6
7
7

힌트

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.</p>

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.