დროის ლიმიტი: 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 დაკოპირება
ამოცანის პირობა და ტესტები მოგვაწოდა სტეფანე გურგენიძემ.