სამეფო სამკაული

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

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

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

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

წყარო: GEOI, 2010, დასკვნითი, IX კლასამდე


 მეფე ლირს 3 ქალიშვილი ჰყავს და სურს მთელი ქონება მათ გაუნაწილოს. მან უკვე გაჰყო ტერიტორიები, ფინანსები და ა.შ. დარჩა მხოლოდ სამეფო სამკაული, რომელიც დამზადებულია ოქროს ძაფებისა და ალმასებისაგან. სამკაულს აქვს გრაფის, კერძოდ ხის მაგვარი სტრუქტურა, ანუ ყოველ ორ ალმასს აკავშირებს ძაფების უნიკალური კომბინაცია. ალმასების ღირებულება ფასდება კარატებით და ისინი იმდენად ძვირფასები არიან, რომ ოქროს ძაფების ღირებულება შეგვიძლია უგულვებელვყოთ, თუმცა ძაფები იშვიათ საიუველირო ნაკეთობას წარმოადგენენ და მათი გადაჭრა მხოლოდ ორ ადგილას გადაწყვიტეს (ეს გამოიწვევს სამკაულის გაყოფას სამ ნაწილად). რადგან ასეთი წესით გაყოფისას სამკაულის თანაბრად გაყოფა შეუძლებელია, მეფე ლირს სურს, რომ სამკაულის ყველაზე ძვირი ნაწილის ფასი მინიმალური იყოს. 
 
 შესატანი მონაცემები:
პირველ სტრიქონში მოცემულია ერთი მთელი რიცხვი N (5≤N≤5000) – ალმასების რაოდენობა.
მომდევნო N სტრიქონიდან თითოეულში მოცემულია თითო მთელი რიცხვი F (1≤ F≤500) – ალმასების ფასი. (i+1)-ე სტრიქონზე მოცემულია i-ური ალმასის ფასი. (N+2)-ე სტრიქონიდან 2N სტრიქონამდე მოცემულია ჰარით გაყოფილი ორ-ორი მთელი რიცხვი – იმ ალმასების ნომრები, რომელიც ოქროს ძაფებით არის შეერთებული.
 
 გამოსატანი მონაცემები: 
ერთი მთელი რიცხვი – სამკაულის სამად გაყოფის შემდეგ ყველაზე მეტი ფასის მქონე ნაწილის მინიმალური მნიშვნელობა. 



მაგალითები

შესატანი მონაცემები
6 10 20 25 40 30 30 4 5 1 3 3 4 2 3 6 4 დაკოპირება
გამოსატანი მონაცემები
70 დაკოპირება

შენიშვნა

განმარტება: თუ გავჭრით მე-3 და მე-4 ალმასების შემაერთებელ ძაფს და ასევე ძაფს,  რომელიც აერთებს მე-4 და მე-5 ალმასებს, სამკაული გაიყოფა 3 ნაწილად. I ნაწილი – ალმასები #1, #2 და #3 (ჯამური წონა 55 კარატი), II ნაწილი – #5 ალმასი  (წონა 30 კარატი), III ნაწილი – ალმასები #4 და #6 (ჯამური წონა 70 კარატი). მაქსიმალური წონა იქნება 70. ამ შედეგის გაუმჯობესება შეუძლებელია.