Хейді зараз у великому магазині. Вона хоче купити n товарів.
Сьогодні її щасливий день. Магазин запускає спеціальну знижку: на кожну покупку, покупець отримує одну з двох пропозицій:
Коли щонайменше 3 товари купуються разом, найдешевший — безкоштовний.
Коли менш ніж 3 товари купуються разом, покупець отримує q% знижку на покупку.
Хейді хоче купити усі n товарів в її шопінг-листі, кожен рівно один раз. Вона може зробити довільну кількість покупок. Для кожної покупки, що вона здійснить, відповідна знижка буде застосована.
Яку мінімальну сумарну ціну має вона заплатити аби купити усі n товарів?
Перший рядок містить два цілі числа n (1≤n≤100000) та q (0≤q≤100) — кількість товарів, що Хейді хоче купити та відсоток знижки, який вона отримує за купівлю менш ніж трьох товарів.
Наступний рядок містить n цілих чисел p1,…,pn — ціни товарів (100≤pi≤100000, 1≤i≤n).
До того ж гарантується що кожне pi завжди ділиться націло на 100. Тобто, знижена ціна кожного продукту завжди буде цілим числом.
Виведіть один рядок — мінімальну сумарну ціну, яку Хейді має заплатити, щоб купити усі n товарів.
У першому прикладі, три товари, що коштують по 200 кожен можуть бути куплені за 400 (ми отримуємо один з товарів безкоштовно). Далі, три товари за 300 можна аналогічно купити за 600. Нарешті, ми купуємо останній товар (вартістю 100) і отримуємо 10% знижку.
У другому прикладі, якщо Хейді купує усі три товари в одній транзакції, вона отримує знижку 100. Однак, якщо вона купує кожен товар окремо, її знижка буде рівна (1000+500+100)⋅20/100=320.
Блок 1 (8 балів): n=3 та 100≤pi≤1000 (1≤i≤3)
Блок 2 (18 балів): q=0
Блок 3 (16 балів): q=40
Блок 4 (22 бали): 100≤pi≤1000 (1≤i≤n)
Блок 5 (36 балів): без додаткових обмежень.