Şopinq-qızdırması#10662
Хейді hazırda böyük bir mağazada alış-veriş edir. O, məhsul almaq niyyətindədir.
Bu gün Хейді üçün şanslı bir gündür, çünki mağaza xüsusi endirimlər təklif edir. Müştərilər hər alış-verişdə iki təklifdən birini seçə bilərlər:
Əgər ən azı məhsul birlikdə alınarsa, ən ucuz məhsul pulsuz verilir.
Əgər məhsuldan az alınarsa, alış-verişə % endirim tətbiq olunur.
Хейді alış-veriş siyahısındakı bütün məhsulu, hər birini yalnız bir dəfə almaq istəyir. O, istədiyi qədər alış-veriş edə bilər və hər alış-veriş üçün uyğun endirim tətbiq olunacaq.
Хейді bütün məhsulu almaq üçün minimum ümumi məbləği necə ödəyə bilər?
Birinci sətir iki tam ədəd (1 \le n \le 100\,000) və (0 \le q \le 100) ehtiva edir — Хейдіnin almaq istədiyi məhsul sayı və məhsuldan az alındıqda aldığı endirim faizi.
Növbəti sətir tam ədəd p_1, \dots, p_n ehtiva edir — məhsulların qiymətləri (100 \le p_i \le 100\,000, 1\le i \le n).
Bundan əlavə, hər bir p_i həmişə -ə tam bölünür. Yəni, hər bir məhsulun endirimli qiyməti həmişə tam ədəd olacaq.
Bir sətir çıxarın — Хейдіnin bütün məhsulu almaq üçün ödəməli olduğu minimum ümumi qiymət.
Nümunə 1
Nümunə 2
Nümunə 3
Birinci nümunədə, hər biri 200 olan üç məhsul 400-ə alına bilər (bir məhsulu pulsuz alırıq). Sonra, hər biri 300 olan üç məhsul eyni şəkildə 600-ə alına bilər. Nəhayət, son məhsulu (100 qiymətində) alırıq və endirim əldə edirik.
İkinci nümunədə, əgər Хейді bütün üç məhsulu bir tranzaksiyada alırsa, o, endirim alır. Lakin, əgər hər bir məhsulu ayrı-ayrılıqda alırsa, onun endirimi (1000 + 500 + 100) \cdot 20/100 = 320 olacaq.
Blok 1 (8 bal): n = 3 və 100 \le p_i \le 1000 (1 \le i \le 3)
Blok 2 (18 bal): q = 0
Blok 3 (16 bal): q = 40
Blok 4 (22 bal): 100 \le p_i \le 1\,000 (1 \le i \le n)
Blok 5 (36 bal): əlavə məhdudiyyətlər yoxdur.