გადატანის გარეშე

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

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

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

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

წყარო: USACO, 2011/12, DEC, BRONZE


ბუბა სწავლობს ქვეშ მიწერით შეკრებას, მაგრამ ჯერ არ იცის როგორ მოიქცეს, როცა რომელიმე თანრიგში ციფრთა ჯამი 9-ს გადააჭარბებს. ამის გამო მას სურს შეარჩიოს ისეთი რიცხვები, რომელთა შეკრებისას ასეთი სიტუაცია არ შეიქმნება. დაწერეთ პროგრამა, რომელიც მოცემული N ცალი რიცხვიდან შეარჩევს მაქსიმალურ რაოდენობას ისე, რომ მათი შეკრებისას ერთი თანრიგიდან მეორეში რაიმე შედეგის გადატანა საჭირო არ იქნება.

შესატანი მონაცემები:

  • სტრიქონი 1: რიცხვების რაოდენობა N (1 <= N <= 20).
  • სტრიქონები 2..N+1: ყოველ სტრიქონში თითო რიცხვი, დიაპაზონში 1...100,000,000.

გამოსატანი მონაცემები:

* სტრიქონი 1: რიცხვების მაქსიმალური რაოდენობა, რომელთა შეკრებაც შესაძლებელია გადატანის გარეშე.

 




მაგალითები

შესატანი მონაცემები
5 522 6 84 7311 19 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება

შენიშვნა

განმარტება: გვაქვს 5 რიცხვი 522, 6, 84, 7311, 19. მათგან შესაძლებელია მაქსიმუმ 3-ის შეკრება გადატანის გარეშე.

   522

   6

+ 7311

   ------

   7839