ხიდი

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

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

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

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

წყარო: პოლონეთი, ოლიმპიადა 11, ეტაპი 2


შუა ღამით მოსეირნე ტურისტების ჯგუფს სურს, გადალახოს დაზიანებული ხიდი. მათ აქვთ მხოლოდ ერთი ფანარი, რომლის შუქიც მხოლო ორ ტურისტს აძლევს საშუალებას, რომ ერთად გადაიარონ ხიდზე. ტურისტებს არ შეუძლიათ ხიდის გადალახვა ფანრის გარეშე, არც ჯგუფურად, სადაც ორზე მეტი ადამიანი იქნება, წინაღმდეგ შემთხვევაში გადავარდებიან ხიდიდან. თითოეულ ტურისტს გარკვეული დრო სჭირდება დაბრკოლების გადასალახად. ორ ტურისტს ერთად ხიდზე გადასასვლელად  სჭირდება იმდენი დრო, რამდენიც მათ შორის ყველაზე ნელს დასჭირდებოდა.  რა არის უმცირესი დრო, რომელშიც ყველა ტურისტი გადავა ხიდზე? 

 მაგალითი 

 დავუშვათ, ჯგუფში არის 4 ტურისტი. პირველ მათგანს ხიდზე გადასასვლელად სჭირდება 6 წთ,  მეორეს - 7 წთ, მესამეს - 10 წთ, ხოლო მეოთხეს - 15 წთ. ქვემოთ მოყვანილი ნახაზი გვიჩვენებს როგორ შეუძლიათ ტურისტებს 44 წუთში ხიდზე გადასვლა. თუმცა მათ ამის გაკეთება უფრო სწრაფადაც შეუძლიათ. როგორ?  

 

                                             6  7  →  Ξ Ξ Ξ                             Ξ Ξ Ξ  ←  6 7                     Ξ Ξ Ξ

                                           10 15       Ξ Ξ Ξ               10 15     Ξ Ξ Ξ                  6  10 →   Ξ Ξ Ξ   7

                                                          Ξ Ξ Ξ                            Ξ Ξ Ξ                    15          Ξ Ξ Ξ

                                                 (7 წუთი)                        (6 წუთი)                               (10 წუთი)

 

                                                                        Ξ Ξ Ξ  ←  6                         Ξ Ξ Ξ

                                                          10 15     Ξ Ξ Ξ   7  10         6  15 →   Ξ Ξ Ξ   7  10

                                                                       Ξ Ξ Ξ                                  Ξ Ξ Ξ

                                                                       (6 წუთი)                            (15 წუთი)

 

დაწერეთ პროგრამა, რომელიც: 

• წაიკითხავს ინფორმაციას ტურისტების ჯგუფის შესახებ სტანდარტული ინფუთიდან,

• იპოვნის უმცირეს დროს, რომელიც საჭირო იქნება ხიდის გადასალახად,

• გამოიტანს შედეგს, სტანდარტულ აუთფუთად. 

 

 

შესატანი მონაცემები: პირველ ხაზზე შემოდის დადებითი მთელი რიცხვი n - ტურისტების რაოდენობა, 1<= n <=100 000. შემდეგ n ცალ ხაზზე (ხაზ-ხაზად) შემოდის, ზრდადი მიმდევრობით, დადებითი მთელი რიცხვები, რომელთა მნიშვნელობაც არ აღემატება 1 000 000 000-ს.  i+1 -ე (1<= i <= n) ხაზზე მყოფი რიცხვი, განსაზღვრავს დროს წუთებში, თუ რამდენ ხანში შეუძლია შესაბამის ტურისტს ხიდის გადავლა. ამ დროების ჯამი არ აჭარბებს 1 000 000 000-ს. 

 გამოსატანი მონაცემები: თქვენმა პროგრამამ სტანდარტული აუთფუთით უნდა დააბრუნოს შედეგი, თუ რა მინიმალურ დროში გადალახავს ყველა ტურისტი ხიდის დაბრკოლებას. 

 

 




მაგალითები

შესატანი მონაცემები
4 6 7 10 15 დაკოპირება
გამოსატანი მონაცემები
42 დაკოპირება