დროის ლიმიტი: 1 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: USACO, 2006/07, MAR, BRONZE
დამოუკიდებლობის დღის აღსანიშნავად ფერმერ ჯონს სურს ბესი ფეიერვერკს დაესწროს. რადგან ბესის გაუჭირდება სრულად უყუროს მთელს შოუს, ფჯ-ის სურს გაიგოს წარმოდგენის რა ნაწილს ნახავს ბესი. რაკეტების გამშვები მოწყობილობები (ქვემეხები) გადანომრილია თანმიმდევრობით 1-დან C-მდე (1<= C <= 100). i-ური ქვემეხიდან ფეიერვერკის რაკეტებს უშვებენ ყოველ T_i (1<= T_i <= N) წამში (ამ ამოცანაში ყველა მონაცემი მთელ რიცხვს წარმოადგენს). წარმოდგენის გახსნისას ყველა ქვემეხიდან გაისვრიან დროის 0 მომენტში. ილუმინაცია (ნათება) რაკეტის გაშვების შემდეგ ჩანს მხოლოდ ერთი წამის განმავლობაში - ეს წამი რაკეტის გაშვების წამია. ბესი ესწრება შოუს დროის 1 მომენტიდან N (1 <= N <= 2,000,000) წამის ჩათვლით. დაეხმარეთ ფჯ-ის, გაარკვიოს თუ რამდენჯერ დაინახავს ბესი რაკეტების გაშვებას დროის იმ შუალედში, როცა ის შოუზე იქნება.
შეტანის ფორმატი:
* სტრიქონი 1: ჰარით გაყოფილი ორი მთელი რიცხვი: C და N.
* სტრიქონები 2..C+1: სტრიქონი i+1 შეიცავს ერთ მთელ T_i რიცხვს.
განმარტება:
შოუზე ორი ქვემეხია: ერთი ისვრის რაკეტას ყოველ 4 წამში, მეორე - ყოველ 6 წამში. ძროხები იმყოფებიან შოუზე 1 წამიდან მე-20 წამის ჩათვლით. ქვემოთ ნაჩვენებია დიაგრამა, რომელიც ასახავს რაკეტების გაშვებას და ძროხების ყოფნას ფეიერვერკზე.
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
2 2 2 ...
1 1 2 1 1 1 2 1 1 ...
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ ...
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ...
გამოტანის ფორმატი:
* სტრიქონი 1: ერთი მთელი რიცხვი - იმ განსხვავებული წამების რაოდენობა 1..N ინტერვალში, რომელთა განმავლობაში ძროხები ხედავენ ფეიერვერკს.
შესატანი მონაცემები
2 20 4 6 დაკოპირება
გამოსატანი მონაცემები
7 დაკოპირება
განმარტება:
რაკეტების გაშვება მოხდება დროის შემდეგ მომენტებში: 4, 6, 8, 12, 16, 18, 20 - სულ 7
განსხვავებული წამი. შევნიშნოთ, რომ მე-12 წამზე ერთდროულად მომხდარი ორი გასროლა, ითვლება ერთად.