Шопинг-лихорадка

Хейди находится в большом магазине и планирует купить $n$ товаров.

Сегодня ей повезло: магазин предлагает специальную скидку. При каждой покупке можно выбрать одно из двух предложений:

1. Если покупаются как минимум $3$ товара, то самый дешёвый из них достаётся бесплатно.

2. Если покупаются менее $3$ товаров, то на покупку предоставляется скидка $q$%.

Хейди хочет приобрести все $n$ товаров из своего списка, каждый по одному разу. Она может совершать любое количество покупок. Для каждой покупки будет применяться соответствующая скидка.

Какова минимальная общая сумма, которую Хейди должна заплатить, чтобы купить все $n$ товаров?

Входные данные

Первая строка содержит два целых числа $n$ ($1\le n\le 100000$) и $q$ ($0\le q\le 100$) — количество товаров, которые Хейди хочет купить, и процент скидки на покупку менее чем трёх товаров.

Следующая строка содержит $n$ целых чисел $p_1,\dots ,p_n$ — цены товаров ($100\le p_i\le 100000$, $1\le i\le n$).

Гарантируется, что каждое $p_i$ делится нацело на 100, то есть сниженная цена каждого товара всегда будет целым числом.

Выходные данные

Выведите одно число — минимальную общую сумму, которую Хейди должна заплатить, чтобы купить все $n$ товаров.

Примеры

Примечание

В первом примере три товара по 200 каждый можно купить за 400 (один из товаров бесплатный). Затем три товара по 300 можно купить за 600. Наконец, последний товар стоимостью 100 покупается с $10\%$ скидкой.

Во втором примере, если Хейди покупает все три товара за один раз, она получает скидку 100. Однако, если она покупает каждый товар отдельно, её скидка составит $(1000+500+100)\cdot 20/100=320$.

Оценивание

Блок 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 1000$ ($1\le i\le n$)

Блок 5 (36 баллов): без дополнительных ограничений.