D - Powerful Discount Tickets

Time Limit: 2 sec / Memory Limit: 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