გუბერნატორის არჩევნები

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

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

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

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


იმერიკის ერთ-ერთ ოლქში გუბერნატორის არჩევნები შემდეგი წესით  ტარდება: ოლქის ყველა ამომრჩეველი იყოფა N ჯგუფად, ამასთან რიცხობრივი თანაბრობა ამ ჯგუფებს შორის აუცილებელი არ არის. არჩევნების დროს კენჭისყრა ტარდება თითოეულ ჯგუფში ცალ-ცალკე და თუ ჯგუფის ნახევარზე მეტი ხმას მისცემს რომელიმე კანდიდატს, ითვლება, რომ ჯგუფი მთლიანად თანახმაა ამ კანდიდატის არჩევაზე. ჯგუფებში კენჭისყრის ჩატარების შემდეგ  განისაზღვრება თუ რამდენი ჯგუფია კონკრეტული კანდიდატის მომხრე და თუ რომელიმე მათგანს ჯგუფების ნახევარზე მეტი უჭერს მხარს, ის ინიშნება გუბერნატორად.  მაგალითისათვის ვთქვათ, ოლქში შეიქმნა ამომრჩეველთა სამი ჯგუფი შესაბამისად 5, 5 და 7 ადამიანის ოდენობით. მაშინ არჩევნებში გასამარჯვებლად საკმარისია 3-3 მხარდამჭერი პირველ ორ ჯგუფში. დაწერეთ პროგრამა, რომელიც ამომრჩეველთა ჯგუფების მოცემული დაყოფისათვის განსაზღვრავს ხმების მინიმალურ რაოდენობას, რომელიც არჩევნებში გამარჯვებისთვისაა საკმარისი.

შემომავალი მონაცემები: პირველ სტრიქონში მოცემულია ნატურალური რიცხვი N<100 – ამომრჩეველთა ჯგუფების რაოდენობა. მეორე სტრიქონში მოცემულია N ცალი ჰარით გაყოფილი რიცხვი, რომლებიც აღწერენ ჯგუფებში ამომრჩეველთა რაოდენობას. ამომრჩეველთა საერთო რაოდენობა არ აღემატება 1000 ადამიანს.

გამომავალი მონაცემები: ერთადერთი ნატურალური რიცხვი, რომელიც აღნიშნავს არჩევნებში გამარჯვებისათვის საჭირო ხმების მინიმალურ რაოდენობას.




მაგალითები

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