Shopping Fever

Heidi is shopping in a large store and plans to purchase $n$ items.

Today, she benefits from a special store discount, which offers two options for each purchase:

1. If she buys at least $3$ items together, the cheapest item is free.

2. If she buys fewer than $3$ items, she receives a $q$% discount on the total purchase.

Heidi aims to buy all $n$ items on her list, each exactly once. She can make multiple purchases, and the respective discount will apply to each.

What is the minimum total cost Heidi must pay to acquire all $n$ items?

Input

The first line contains two 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 for purchasing fewer than three items.

The second line lists $n$ integers $p_1,\dots ,p_n$ — the prices of the items ($100\le p_i\le 100,000$, $1\le i\le n$).

Each $p_i$ is guaranteed to be divisible by 100, ensuring that any discounted price will be an integer.

Output

Output a single line — the minimum total amount Heidi needs to pay to purchase all $n$ items.

Examples

Note

In the first example, Heidi can buy three items priced at 200 each for a total of 400, as one item is free. She can then buy another three items priced at 300 each for 600. Finally, she buys the last item, priced at 100, with a $10\%$ discount.

In the second example, if Heidi buys all three items in one transaction, she saves 100. However, if she buys each item separately, her total discount will be $(1000+500+100)\cdot 20/100=320$.

Scoring

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

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

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

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

Block 5 (36 points): no additional constraints.