100 Böyük Ukraynalı#1132
Məşhur bir televiziya şousunun qaydası belədir: müəyyən bir dövrdə Ukraynada yaşamış bir sıra tanınmış şəxslər namizəd göstərilir. Studiyadakı qonaqlar və tamaşaçılar müxtəlif namizədləri müzakirə edir. Ən maraqlı hissə isə veriliş bitdikdən sonra baş verir: efirdə telefon nömrələri elan edilir və hər kəs öz telefonundan (qiyməti qrivna) SMS göndərməklə sevimli namizədinə səs verə bilər. Hər SMS seçilən namizədə səs qazandırır. Bir müddət sonra, SMS-lə verilən səslər sayılır və ən yüksək səs toplamış müəyyən sayda namizəd "Böyük" elan edilir. Əgər Böyük seçiləcək namizədlərin sayını aşacaq sayda namizədlər arasında bərabərlik olarsa, həmin bərabərlikdə olanlar və onlardan daha az səs toplayanlar Böyük sayılmır.
Müəyyən bir ictimai-siyasi təşkilat, seçdiyi bəzi namizədlərin Böyük siyahısına düşməsini təmin etmək istəyir. Nəticələr rəsmiləşdirilməzdən bir gün əvvəl təşkilat bütün namizədlərin indiki səs saylarını öyrənir və bu nəticələr onların istədiyi namizədlərin Böyük olmasını təmin etmir. Çünki bir nömrədən təkrarı SMS-lər sayılmır, təşkilat üzvü küçəyə çıxıb yoldan keçənlərdən istədiyi namizəd üçün SMS göndərmələrini xahiş edir. Təşkilat ödənilən məbləği geri qaytardığı üçün, yoldan keçən şəxs dərhal öz qrivnasını geri alır.
Əlavə olaraq, digər bir təşkilat da birincinin planını pozmaq məqsədilə eyni qaydada hərəkət edir. Bu təşkilatın nümayəndəsi də öz dəstək verdiyi namizədlər üçün yoldan keçənlərə müraciət edir.
İkinci təşkilatın sərəncamında olan məbləğ məlum olduqda, birinci təşkilatın dəstəklədiyi namizədləri Böyük Ukraynalı etmək üçün, ikinci təşkilatın ən güclü qarşı strategiyasını nəzərə alaraq, birinci təşkilatın xərcləməli olduğu minimal məbləği müəyyən edin.
Əlavə edək ki, əhalinin sayı istənilən SMS-i göndərməyə imkan verir və hər iki nümayəndə lazım olan sayda adam tapa bilər. Qalan müddətdə adi şəxslər isə öz pulları ilə, öz təşəbbüsü ilə səsləməyəcək.
Birinci sətrdə tam ədəd: (namizədlərin ümumi sayı), (Böyük seçiləcək namizədlərin sayı), (birinci təşkilatın dəstəklədiyi namizədlərin sayı) verilir. İkinci sətrdə — ikinci təşkilatın sərəncamında olan məbləğ (1 \leq K \leq M \leq N \leq 10^5, 0 \leq S \leq 10^9). Üçüncü sətrdə A_i (i=1,\ldots,N) — hər bir namizədin indiki səs sayı verilib (0 \leq A_i \leq 10^9). Dördüncü sətrdə B_j (j=1,\ldots,K) — Böyük edilməli namizədlərin indeksləri verilib.
Məqsədin yerinə yetirilməsi üçün birinci təşkilatın xərcləməli olduğu minimal məbləği çap edin.
Nümunə 1