Lawrence of Arabia
T. E. Lawrence Birinci Dünya Müharibəsi zamanı mübahisəli bir şəxsiyyət idi. O, Ərəb teatrında xidmət edən və Osmanlı İmperiyasına qarşı partizan hücumları həyata keçirən ərəb millətçiləri qrupuna rəhbərlik edən bir Britaniya zabiti idi. Onun əsas hədəfləri dəmir yolları idi. Onun macəralarının yüksək dərəcədə uydurulmuş bir versiyası "Ərəbistanlı Lourens" adlı blockbuster filmində təqdim edilmişdir.
Lourensə məhdud resurslarını ən yaxşı şəkildə necə istifadə edəcəyini anlamağa kömək edəcək bir proqram yazmalısınız. Sizdə Britaniya Kəşfiyyatından bəzi məlumatlar var. Əvvəlcə, dəmir yolu tamamilə xətti - heç bir budaq, heç bir çıxıntı yoxdur. Sonra, Britaniya Kəşfiyyatı hər bir depoya Strateji Əhəmiyyət təyin edib - 1 ilə 5 arasında bir tam ədəd. Bir depo öz-özünə heç bir fayda vermir, yalnız digər depolarla əlaqəli olduqda dəyəri var. Bütün dəmir yolunun Strateji Dəyəri, dəmir yolu ilə birbaşa və ya dolayı yolla əlaqəli olan hər bir depo cütü üçün Strateji Dəyərlərin məhsullarının cəmi ilə hesablanır. Bu dəmir yolunu nəzərdən keçirin:
Onun Strateji Dəyəri 4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49.
İndi, təsəvvür edin ki, Lourens yalnız bir hücum üçün kifayət qədər resursa malikdir. O, depoların özlərinə hücum edə bilməz - onlar çox yaxşı müdafiə olunmuşdur. O, səhranın ortasında depolar arasındakı dəmir yoluna hücum etməlidir. Lourens bu dəmir yoluna tam ortada hücum etsə nə baş verəcəyini düşünün:
Qalan dəmir yolunun Strateji Dəyəri 4*5 + 1*2 = 22. Amma, Lourens 4 və 5 depoları arasına hücum etsə:
Qalan dəmir yolunun Strateji Dəyəri 5*1 + 5*2 + 1*2 = 17. Bu, Lourensin ən yaxşı seçimidir.
Bir dəmir yolunun təsvirini və Lourensin həyata keçirə biləcəyi hücumların sayını nəzərə alaraq, o dəmir yolu üçün əldə edə biləcəyi ən kiçik Strateji Dəyəri tapın.
Giriş verilənləri
Bir neçə məlumat dəsti olacaq. Hər bir məlumat dəsti iki tam ədədlə başlayan bir sətirlə başlayacaq, n və m. n dəmir yolundakı depoların sayıdır (1 ≤ n ≤ 1000), və m Lourensin resurslarının yetdiyi hücumların sayıdır (0 ≤ m < n). Növbəti sətirdə hər biri 1 ilə 5 arasında olan n tam ədəd olacaq, hər biri sırayla hər bir depotun Strateji Dəyərini göstərir. Girişin sonu n=0 və m=0 olan bir sətirlə işarələnəcək, bu işlənməməlidir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün Lourensin hücumları ilə əldə edə biləcəyi dəmir yolunun ən kiçik Strateji Dəyərini göstərən bir tam ədəd çıxarın. Hər bir tam ədədi öz sətirində çıxarın.