/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
高橋くんは N 個の品物を 1 個ずつ順番に買う予定です。
i 番目に買う品物の値段は A_i 円です。
高橋くんは M 枚の割引券を持っています。
品物を買う際に割引券を好きな枚数使うことができます。
X 円の品物を買う際に Y 枚の割引券を使った場合、その品物を \frac{X}{2^Y} 円(小数点以下切り捨て)で買うことができます。
最小で何円あれば全ての品物を買うことができるでしょうか。
制約
- 入力は全て整数である。
- 1 \leq N, M \leq 10^5
- 1 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N
出力
全ての品物を買うのに必要なお金の最小値を出力せよ。
入力例 1
3 3 2 13 8
出力例 1
9
以下のように割引券を使えば、合計 9 円で全ての商品を買うことができます。
- 1 番目に買う品物には割引券を使わず、2 円で買います。
- 2 番目に買う品物には 2 枚の割引券を使い、3 円で買います。
- 3 番目に買う品物には 1 枚の割引券を使い、4 円で買います。
入力例 2
4 4 1 9 3 5
出力例 2
6
入力例 3
1 100000 1000000000
出力例 3
0
1000000000 円の品物を買う際に 100000 枚の割引券を使うと 0 円で買うことができます。
入力例 4
10 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 4
9500000000
Score : 400 points
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.
Sample Input 1
3 3 2 13 8
Sample 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.
Sample Input 2
4 4 1 9 3 5
Sample Output 2
6
Sample Input 3
1 100000 1000000000
Sample Output 3
0
We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.
Sample Input 4
10 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 4
9500000000