Time Limit: 1000 mSec Memory Limit : 32768 KB

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.

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.

The input will consist of several datasets.

Each dataset contains two parts:

*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

Input is terminated by end of file.

Each dataset contains two parts:

*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

Input is terminated by end of file.

* 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.

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.