時間制限:1000ミリ秒
メモリ制限:65536KB
問題
K匹(1 ≤ K ≤ 1,000)の牛が年に一度の農夫ジョンの読書コンテストに参加しています。コンテストではN (1 ≤ N ≤ 100,000)の一冊の本をちゃんと理解しつつなるべく速く読みます。
牛iは一分あたりSi(1 ≤ Si ≤ 100)の速さで本を読み、最長でTi(1 ≤ Ti ≤ 100)だけ連続して本を読みつづけることができ、最短の休憩時間はRi(1 ≤ Ri ≤ 100)分ですみます。
牛は毎分Siページで本を読めますが、一回でTi分しか読めません。休憩のため読書を停止し、読書を再開するまでにRi分の休憩をしなくてはなりません。
各牛が本を読み終えるのにかかる時間(最も近い分単位に四捨五入)を求めてください。
入力
1行目: スペースで区切られた2つの整数: NとK
2~K+1行目: i+1行目はスペースで区切られた3つの整数SiとTi, Ri
出力
1~K行: i行は牛iが本を読み終えるのにかかる時間を表す。
入力の例
10 3 2 4 1 6 1 5 3 3 3
出力の例
6 7 7
出典
USACO 2007 November Bronze