Background

Day 2 Problem A.

Translated from EGOI2021 shoppingfever.

Problem Description

Heidi is in a large store. She wants to buy $n$ items.

Today is her lucky day. The store is having a promotion: for each bill, the customer gets one of the following two discounts:

1. If at least $3$ items are bought, the cheapest one is free.
2. If fewer than $3$ items are bought, this bill gets a $q\%$ discount.

Heidi wants to buy all $n$ items without buying any item more than once. She may split the purchase into any number of bills. For each bill, the corresponding discount policy will be applied.

What is the minimum amount of money she needs to pay to buy all $n$ items?

Input Format

The first line contains two integers $n, q$ — the number of items and the discount percentage when buying fewer than $3$ items.

The second line contains $n$ integers $p_i$ — the prices of the items.

It is also guaranteed that each item price is divisible by $100$. Therefore, the discounted price for each bill is always an integer.

Output Format

One line with one integer — the minimum amount of money needed.

7 10
300 200 200 300 100 300 200

1090

3 20
1000 500 100

1280

4 0
200 100 300 200

600

Hint

Explanation for Sample $1$

Heidi first buys three items priced at $200$, paying $400$ (one item is free). Then she buys three items priced at $300$, paying $600$ (again, one item is free). Finally, she buys the remaining item priced at $100$ and gets a $10\%$ discount.

Explanation for Sample $2$

If Heidi buys three items in a single bill, she gets a discount of $100$. However, if she buys the three items in three separate bills, the discount becomes $(1000+500+100)\cdot\frac{20}{100}=320$.

Constraints

For all testdata, $1\le n\le 10^5$, $0\le q\le 100$, $100\le p_i\le 10^5$, and $100\mid p_i$.

• Subtask 1 ($8$ points): $n=3$, $100\le p_i\le 10^3$.
• Subtask 2 ($18$ points): $q=0$.
• Subtask 3 ($16$ points): $q=40$.
• Subtask 4 ($22$ points): $100\le p_i\le 10^3$.
• Subtask 5 ($36$ points): no additional constraints.

Translated by ChatGPT 5