22011번 - Shopping Fever 서브태스크다국어

문제

Heidi is in a big store. She would like to purchase $n$ items.

Today is her lucky day. The store runs a special sale: on every purchase, the customer receives one of the following two promotions:

1. When at least 3ドル$ items are bought together, the cheapest one is free.
2. When fewer than 3ドル$ items are bought together, the customer gets a $q\%$ discount on the purchase.

Heidi would like to buy all $n$ items on her shopping list, each exactly once. She can make an arbitrary number of purchases. For each purchase she'll make, the appropriate promotion will apply.

What is the minimum total price she has to pay to buy all $n$ items?

입력

The first line contains two single space-separated integers $n$ (1ドル \le n \le 100,000円$) and $q$ (0ドル \le q \le 100$) — the number of items Heidi wants to buy and the percentage discount she gains for purchases of fewer than three items.

The following line contains $n$ single space separated integers $p_1, \dots, p_n$ — the prices of the goods (100ドル \le p_i \le 100,000円,ドル 1ドル \le i \le n$).

Additionally, it is guaranteed that each $p_i$ will always be divisible by 100ドル$. Hence, the discounted price of each purchase will always be an integer.

출력

Output a single integer — the minimum total price Heidi has to pay in order to buy all $n$ items.

제한

서브태스크

노트

First, Heidi can buy the three items that cost 200ドル$ in a single transaction for 400ドル$ (she gets one of them for free). Then she can purchase the three items that cost 300ドル$ for 600ドル$ (again, one is free). Finally, she can purchase the last remaining item (with cost 100ドル$) with a 10ドル\%$ discount.

In the second example test, if Heidi buys all three items in a single transaction, she receives discount of 100ドル$. However, if she buys each item individually, her discount will be $(1000 + 500 + 100) \cdot 20 / 100 = 320$.