ფიცრების გათანაბრება

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

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

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

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


ბუბამ მუშაობა დაიწყო სამხერხაოში. მას მისცეს N (N ლუწია) ცალი ფიცარი და დაავალეს, რომ ამ ფიცრებისგან დაამზადოს ზუსტად ერთნაირი ორი პაკეტი, ანუ ეს ფიცრები უნდა გაჰყოს ორ ნაწილად ისე, რომ თითოეულ ნაწილში იყოს ზუსტად N/2 ფიცარი და ყოველ ფიცარს ერთ-ერთი ნაწილიდან მოეძებნებოდეს ზუსტად იმავე სიგრძის ანალოგი მეორე ნაწილში. ცხადია, რომ ამ მიზნის მისაღწევად ზოგიერთ ფიცარს გადახერხვა დასჭირდება და გადახერხილი ნაჭრების ჯამური სიგრძე მინიმალური უნდა იყოს. დაწერეთ პროგრამა, რომელიც გამოთვლის გადახერხილი ნაჭრების მინიმალურ ჯამურ სიგრძეს.

შესატანი მონაცემები: პირველ სტრიქონში ლუწი დადებითი რიცხვი N (1<N<1001). მეორე სტრიქონში N ცალი მთელი დადებითი რიცხვი დიაპაზონიდან 1..100.

გამოსატანი მონაცემები: გადახერხილი ნაჭრების მინიმალური ჯამური სიგრძე.




მაგალითები

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