სწრაფი კითხვა

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2007/08, NOV, BRONZE


ყოველი K (1<=K<=1,000) ძროხა მონაწილეობას იღებს ფერმერ ჯონის ყოველწლიურ შეჯიბრებაში. შეჯიბრების მიზანია რაც შეიძლება სწრაფად იქნეს წაკითხული წიგნი, რომელსაც N (1<=N<=100,000) გვერდი აქვს. i-ურ ძროხას აქვს კითხვის სიჩქარე S_i (1<=S_i<= 100) გვერდი წუთში, T_i (1<=T_i<=100) წუთი დრო გადაბმული კითხვისთვის და R_i (1<=R_i<=100) წუთი დრო შესვენებებისთვის. ეს ნიშნავს, რომ i-ური ძროხა S_i გვერდი წუთში სიჩქარით კითხულობს ტექსტს T_i წუთის განმავლობაში, შემდეგ ისვენებს R_i წუთს, შემდეგ ისევ იგივე სიჩქარით კითხულობს იგივე დროის განმავლობაში, ისევ ისვენებს იგივე დროით და ა.შ. მანამ, სანამ მთლიან წიგნს არ წაიკითხავს.

განსაზღვრეთ თითოეული ძროხის მიერ წიგნის წასაკითხად დახარჯული დრო (დაამრგვალეთ უკანასკნელ სრულ წუთამდე).

შეტანის ფორმატი:

* სტრიქონი 1: ჰარით გამოყოფილი ორი მთელი რიცხვი N და K.

* სტრიქონები 2..K+1: სტრიქონი i+1 შეიცავს ჰარით გამოყოფილ სამ რიცხვს: S_i, T_i, და R_i.

შეტანის დეტალები:

 წიგნს სულ 10 გვერდი აქვს. შეჯიბრში 3 ძროხა მონაწილეობს. პირველი ძროხა წუთში 2 გვერდს კითხულობს, მისი გადაბმული კითხვის დროა 4 წუთი, ხოლო გადაბმულ კითხვებს შორის შესვენებები 1 წუთია. მეორე ძროხის სიჩქარეა 6 გვერდი/წუთში, გადაბმული კითხვის დრო 1 წუთი, ხოლო შესვენებების დრო 5 წუთი. მესამე ძროხა კითხულობს 3 გვერდს/წუთში, გადაბმულად შეუძლია 3 წუთის განმავლობაში კითხვა და შესვენებებიც აქვს 3 წუთიანი.

გამოტანის ფორმატი:

 * სტრიქონები 1..K: სტრიქონი i გვიჩვენებს, თუ რამდენ დროს (დამრგვალებულს 1 წუთის სიზუსტით) მოანდომებს i-ური ძროხა მთლიანი წიგნის წაკითხვას.

 

  

 

 




მაგალითები

შესატანი მონაცემები
10 3 2 4 1 6 1 5 3 3 3 დაკოპირება
გამოსატანი მონაცემები
6 7 7 დაკოპირება

შენიშვნა

გამოტანის დეტალები:

 პირველი ძროხა 4 წუთში 8 გვერდს წაიკითხავს, მერე 1 წუთს დაისვენებს და კიდევ ერთ წუთში წაიკითხავს დარჩენილ 2 გვერდს - სულ 6 წუთი. მეორე ძროხა პირველ 1 წუთში 6 გვერდს წაიკითხავს, მერე 5 წუთს დაისვენებს და კითხვას დაამთავრებს ბოლო ერთ წუთში - სულ 7 წუთი. მესამე პირველ 3 წუთში 9 გვერდს წაიკითხავს, მერე 3 წუთი დაისვენებს და მერე 1 წუთში დაამთავრებს კითხვას.