21647_SpeedReading

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.

Cowihas 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 Sipages per minute, but only for Timinutes at a time. After she stops reading to rest, she must rest for Riminutes 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 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