AtCoder Beginner Contest 141
翻译中…
Problem Statement
翻译中…
Takahashi is going to buy $N$ items one by one.
翻译中…
The price of the $i$-th item he buys is $A_i$ yen (the currency of Japan).
翻译中…
He has $M$ discount tickets, and he can use any number of them when buying an item.
翻译中…
If $Y$ tickets are used when buying an item priced $X$ yen, he can get the item for $\frac{X}{2^Y}$ (rounded down to the nearest integer) yen.
翻译中…
What is the minimum amount of money required to buy all the items?
翻译中…
Constraints
翻译中…
- All values in input are integers.
$1 \leq N, M \leq 10^5$$1 \leq A_i \leq 10^9$
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N M
A_1 A_2 ... A_N翻译中…
Output
翻译中…
Print the minimum amount of money required to buy all the items.
翻译中…
样例
Input #1
3 3
2 13 8
Output #1
9
We can buy all the items for $9$ yen, as follows:
- Buy the $1$-st item for $2$ yen without tickets.
- Buy the $2$-nd item for $3$ yen with $2$ tickets.
- Buy the $3$-rd item for $4$ yen with $1$ ticket.
Input #2
4 4
1 9 3 5
Output #2
6
Input #3
1 100000
1000000000
Output #3
0
We can buy the item priced $1000000000$ yen for $0$ yen with $100000$ tickets.
Input #4
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Output #4
9500000000
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。