Time Limit: 1000 mSec

Memory Limit: 32768 KB

## Description

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.

## Input

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.

## Output

* 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

## Hint

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

## Source

USACO 2007 November