სამართლიანი თოვლის ბაბუა

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

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

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

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


ახალი წელი ბავშვების საყვარელი დღესასწაულია, რადგან ყოველ ახალ წელს თოვლის ბაბუა მათ საჩუქრებს ჩუქნის. თუმცა მანამ, სანამ ყველა ბავშვი კუთვნილ საჩუქარს მიიღებს, თოვლის ბაბუას მძიმე სამუშაო აქვს შესასრულებელი: 

 ლაპლანდიის სახელოსნოში ერთ რიგად არის დალაგებული N ცალი სათამაშო. სათამაშოები ერთმანეთისგან ხარისხით განსხვავდება, რაც ნატურალური რიცხვების სახით არის წარმოდგენილი (რაც მეტია მისი რიცხვითი მნიშვნელობა, მით უფრო კარგი ხარისხის არის სათამაშო). თოვლის ბაბუა საჩუქრებს შემდეგი წესების დაცვით ამზადებს: 

• ყოველი საჩუქარი ერთი ან მეტი ერთმანეთის მომდევნო სათამაშოსგან უნდა შედგებოდეს;

• საჩუქრები არ უნდა თანაიკვეთებოდნენ, ყოველი სათამაშო მაქსიმუმ ერთი საჩუქრის შემადგენლობაში უნდა შედიოდეს;

• ყოველ საჩუქარში შემავალი სათამაშოების ჯამური ხარისხი უნდა იყოს ტოლი. 

 თქვენი მიზანია, ამ წესების დაცვით რაც შეიძლება მეტი საჩუქარი დაამზადებინოთ თოვლის ბაბუას. 

 

შესატანი მონაცემები: პირველ ხაზზე შემოდის მთელი რიცხვი N (1 ≤ N ≤ 1500) - სათამაშოების რაოდენობა. მეორე ხაზზე შემოდის N ცალი მთელი რიცხვი a[1], a[2], …, a[N] (1 ≤ ai ≤ 105) - სათამაშოების ხარისხები. 

 გამოსატანი მონაცემები: გამოიტანეთ მთელი რიცხვი M - მაქსიმუმ რამდენი საჩუქრის დამზადება შეუძლია თოვლის ბაბუას. 




მაგალითები

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

შენიშვნა

 

 

ამოცანის პირობა და ტესტები მოგვაწოდა სტეფანე გურგენიძემ.