Böyük pilləkənlərdən olan qarətçilər#5330
Çoxumuz pilləkənin üstündə gözləyən quldurlar haqqında kədərli hekayəni bilirik. Lakin zaman dəyişir, və daha çox "müştəri" cəlb etmək üçün quldurlar endirim sistemi tətbiq ediblər. İndi pilləkənin birində sizi soyduqdan sonra 50% endirimli kart verirlər. Bu kartla, növbəti pilləkənlərdə quldurlara yalnız adi məbləğin yarısını ödəyirsiniz!
Qalan qaydalar dəyişməz qalıb: siz qalxmağa döşəmədən (pilləkən ) başlayırsınız və bir dəfəlik –dən -yə qədər istənilən sayda pilləkən keçə bilərsiniz. Hər pilləkəndə quldurlar sizdən c_i rubl tələb edir, əgər ora düşsəniz. Məqsədiniz -ci pilləkənə mümkün qədər az pul xərcləyərək çatmaqdır.
Birinci sətrdə iki tam ədəd verilir: (1 \leq n \leq 10^5) — pilləkənlərin sayı, və (1 \leq k \leq 100) — bir addımda keçə biləcəyiniz maksimal pilləkən sayı.
İkinci sətrdə tam ədəd c_1, c_2, \ldots, c_n (0 \leq c_i \leq 10^4, hamısı cütdür) — -ci pilləkəndə quldurlara ödəməli olduğunuz rublun miqdarı verilir.
Üçüncü sətrdə bir tam ədəd (1 \leq d \leq n) — quldurların endirim kartı verdiyi pilləkənin nömrəsi.
Çıxışda pilləkənləri keçmək üçün lazım olan minimal rubl miqdarını çap edin.
Nümunə 1