Serverlər
"' Bir evdəki kompüter şəbəkəsi, yeni kompüterin artıq qoşulmuş sonuncu kompüterə bağlanması prinsipi ilə qurulmuşdur. Şəbəkədəki heç bir iki kompüter arasında əlavə əlaqə yoxdur. Beləliklə, şəbəkəyə ardıcıl olaraq n kompüter qoşulmuşdur. Qonşular bir-biri ilə məlumat mübadiləsi edirdilər, lakin bir müddət sonra onlara proxy serverlərin lazım olduğunu anladılar. Evin kompüter icması k kompüterə proxy serverlər quraşdırmağa qərar verdi. İndi isə hansı kompüterlərin bu məqsəd üçün seçiləcəyinə qərar vermək lazımdır. Əsas meyar bütün kompüterlərin serverlər tərəfindən aylıq xidmət xərcləridir.
Hər bir kompüter üçün xidmət tarifi müəyyən edilmişdir və bu tarif metr kabel üçün rubl ilə ifadə olunur. Hər hansı bir server tərəfindən bir kompüterin xidmət xərci, kompüterin tarifinin bu kompüterdən onu xidmət edən serverə qədər olan kabelin ümumi uzunluğuna vurulmasına bərabərdir.
Sizin vəzifəniz, bütün kompüterlərin xidmət xərclərinin minimum olması üçün k kompüter seçərək onlara proxy serverlər quraşdıracaq bir proqram yazmaqdır.
Giriş verilənləri
Birinci sətirdə şəbəkədəki kompüterlərin sayı və quraşdırılacaq proxy serverlərin sayı olan iki tam ədəd n və k verilir (1 ≤ k ≤ n ≤ 2000).
Şəbəkədəki bütün kompüterlər qoşulma sırasına görə 1 ilə n arasında nömrələnmişdir.
İkinci sətirdə birinci kompüterin xidmət tarifi olan bir tam ədəd t_{i} verilir.
Növbəti n – 1 sətirdə ardıcıl nömrələrə görə şəbəkədəki digər kompüterlər haqqında iki tam qeyri-mənfi ədəd l_i, t_{i} verilir. Burada l_{i} - i-ci kompüteri daha kiçik nömrəli qonşu kompüterlə birləşdirən kabelin uzunluğu, t_{i} - həmin kompüterin xidmət tarifidir (2 ≤ i ≤ n). Bütün l_{i} və t_{i} 10^6-dan çox deyil.
Çıxış verilənləri
Birinci sətirdə bütün kompüterlərin bütün serverlər tərəfindən xidmət edilməsinin minimal xərci yazılmalıdır. İkinci sətirdə serverlərin quraşdırılması üçün seçilməli olan k kompüterlərin nömrələri boşluqla ayrılmış şəkildə yazılmalıdır. Bir neçə yerləşdirmə variantı olduqda, istənilən birini çıxarmağa icazə verilir. "'