Задачи
Шопінг-лихоманка
Шопінг-лихоманка
Хейді зараз у великому магазині. Вона хоче купити $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 балів): без додаткових обмежень.
Входные данные #1
7 10 300 200 200 300 100 300 200
Выходные данные #1
1090
Входные данные #2
3 20 1000 500 100
Выходные данные #2
1280
Входные данные #3
4 0 200 100 300 200
Выходные данные #3
600