408483: GYM103149 A 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.

Subtask 1 (8 points): $$$n = 3$$$ and $$$100 \le p_i \le 1000$$$ ($$$1 \le i \le 3$$$)

Subtask 2 (18 points): $$$q = 0$$$

Subtask 3 (16 points): $$$q = 40$$$

Subtask 4 (22 points): $$$100 \le p_i \le 1\,000$$$ ($$$1 \le i \le n$$$)

Subtask 5 (36 points): No additional constraints.

7 10
300 200 200 300 100 300 200

1090

3 20
1000 500 100

1280

4 0
200 100 300 200

600

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$$$.