eolymp
Competitions

European Girls' Olympiad in Informatics 2021, II Day

Шопінг-лихоманка

Хейді зараз у великому магазині. Вона хоче купити $n$ товарів. Сьогодні її щасливий день. Магазин запускає спеціальну знижку: на кожну покупку, покупець отримує одну з двох пропозицій: \begin{enumerate} \item Коли щонайменше $3$ товари купуються разом, найдешевший --- безкоштовний. \item Коли менш ніж $3$ товари купуються разом, покупець отримує $q$\% знижку на покупку. \end{enumerate} Хейді хоче купити усі $n$ товарів в її шопінг-листі, кожен рівно один раз. Вона може зробити довільну кількість покупок. Для кожної покупки, що вона здійснить, відповідна знижка буде застосована. Яку мінімальну сумарну ціну має вона заплатити аби купити усі $n$ товарів? \InputFile Перший рядок містить два цілі числа $n$ ($1 \le n \le 100\,000$) та $q$ ($0 \le q \le 100$) --- кількість товарів, що Хейді хоче купити та відсоток знижки, який вона отримує за купівлю менш ніж трьох товарів. Наступний рядок містить $n$ цілих чисел $p_1, \dots, p_n$ --- ціни товарів ($100 \le p_i \le 100\,000$, $1\le i \le n$). До того ж гарантується що кожне $p_i$ завжди ділиться націло на 100. Тобто, знижена ціна кожного продукту завжди буде цілим числом. \OutputFile Виведіть один рядок --- мінімальну сумарну ціну, яку Хейді має заплатити, щоб купити усі $n$ товарів. \Note У першому прикладі, три товари, що коштують по 200 кожен можуть бути куплені за 400 (ми отримуємо один з товарів безкоштовно). Далі, три товари за 300 можна аналогічно купити за 600. Нарешті, ми купуємо останній товар (вартістю 100) і отримуємо $10\%$ знижку. У другому прикладі, якщо Хейді купує усі три товари в одній транзакції, вона отримує знижку $100$. Однак, якщо вона купує кожен товар окремо, її знижка буде рівна $(1000 + 500 + 100) \cdot 20/100 = 320$. \Scoring Блок 1 (8 балів): $n = 3$ та $100 \le p_i \le 1000$ ($1 \le i \le 3$) Блок 2 (18 балів): $q = 0$ Блок 3 (16 балів): $q = 40$ Блок 4 (22 бали): $100 \le p_i \le 1\,000$ ($1 \le i \le n$) Блок 5 (36 балів): без додаткових обмежень.
Time limit 1 second
Memory limit 256 MiB
Input example #1
7 10
300 200 200 300 100 300 200
Output example #1
1090
Input example #2
3 20
1000 500 100
Output example #2
1280
Input example #3
4 0
200 100 300 200
Output example #3
600
Author Anton Tsypko