ნახირის გაყოფა

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

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

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

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

წყარო: USACO, 2000/01, WINTER, GREEN


ფერმერ ჯონს სურს N (1<=N<=40) ძროხისაგან შედგენილი ნახირი გაჰყოს ორ ნაწილად. i-ური ძროხა იძლევა Mi ლიტრ (1<=Mi<=100) რძეს თვეში და ფჯ-ს სურს ისე გაჰყოს ნახირი, რომ ორივე ნაწილი რძეს თანაბრად იძლეოდეს. თუკი ნახირის ასე გაყოფა შეუძლებელია, ფჯ აპირებს მოაშოროს ნახირს რომელიმე ძროხა (ან ძროხები – თუკი ეს საჭიროა), ვიდრე დანარჩენ ძროხებს გაჰყოფდეს ორ ჯგუფად. რძის საერთო რაოდენობა, რომელსაც თითოეული ჯგუფი იძლევა თვის განმავლობაში, აღვნიშნოთ T-თი. თქვენი ამოცანაა, იპოვოთ მაქსიმალურად შესაძლებელი T.

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

გამომავალი მონაცემები: ერთადერთ სტრიქონში ერთი მთელი რიცხვი – T-ს მაქსიმალური მნიშვნელობა. თუკი არ არსებობს შესაძლებლობა, რომ ძროხების გარკვეული რაოდენობის მოშორების შემდეგაც კი დარჩენილი ნახირი გავყოთ ორ ჯგუფად, გამოიტანეთ 0.




მაგალითები

შესატანი მონაცემები
6 1 2 39 6 10 7 დაკოპირება
გამოსატანი მონაცემები
13 დაკოპირება