Serverlər#2881
Bir evdə kompüter şəbəkəsi aşağıdakı qaydada qurulmuşdur: hər yeni kompüter daha əvvəl qoşulmuş son kompüterə birləşdirilmişdir. Qoşulduqdan sonra, heç bir iki kompüter daha bir-birinə birləşdirilməmişdir. Cəmi kompüter ardıcıl şəkildə qoşulub. Qonşu kompüterlər bir-birilə məlumat mübadiləsi aparırdı, amma sonda gördülər ki, proksi-serverlərə ehtiyac var. Sakinlər məhz kompüterdə proksi-server qurulmasına qərar verdilər. İndi isə hansı kompüterlərin bu məqsəd üçün seçiləcəyinə qərar verilməlidir. Əsas məqsəd serverləri olan bütün kompüterlərin aylıq saxlanma xərcini minimuma endirməkdir.
Hər bir kompüterin xidmət tarifi var, o da avro ilə bir metr məftil üzrə ifadə edilir. Kompüterin server tərəfindən xidmət olunma xərci kompüterin tarifi və onun serverə olan ümumi məftil uzunluğunun hasilinə bərabərdir.
Sizdən tələb olunur ki, proksi-serverlərin qurulacağı kompüterin elə seçimini verən proqram yazasınız ki, bütün kompüterlərin xidmət olunma üçün ümumi xərci minimum olsun.
Birinci sətirdə iki tam ədəd və verilir — şəbəkədəki kompüterlərin sayı və quraşdırılacaq proksi-serverlərin sayı (1 \leq k \leq n \leq 2000).
Bütün kompüterlərə qoşulma ardıcıllığına görə -dən -ə qədər nömrə verilir.
İkinci sətirdə bir tam ədəd t_1 — birinci kompüterin xidmət tarifi verilir.
Daha sonrakı n-1 sətirin hər birində iki qeyri-mənfi tam ədəd l_i və t_i verilir — bu, hər növbəti kompüter barədə məlumatdır. l_i — -ci kompüterin daha kiçik nömrəli qonşusuna olan məftil uzunluğudur, və t_i — bu kompüterin xidmət tarifidir (2 \leq i \leq n). Bütün l_i və t_i 10^6-dan böyük deyil.
Birinci sətirdə bütün serverlərin xidmətində olan kompüterlər üçün minimum ümumi xərci çap edin. İkinci sətirdə isə serverlərin quraşdırılması üçün seçilmiş kompüterin nömrələrini boşluqla ayırmaqla verin. Əgər bir neçə düzgün cavab varsa, istənilənini verə bilərsiniz.
Nümunə 1