提示: 欢迎访问OurACM平台。
Problem 1542 Speed Reading

Accept: 160    Submit: 291
Time Limit: 1000 mSec    Memory Limit : 32768 KB

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

Sample Input

10 3 2 4 1 6 1 5 3 3 3

Sample Output

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

Submit  Back  Status  Discuss