Remove Stones to Minimize the Total (LC 1962 :)

Each time, choose any pile and remove floor(stones/2) from it, leaving ceil(stones/2). The same pile may be chosen repeatedly. After exactly k operations, minimize the total number of remaining stones.

输入格式

The first line contains n k, and the second line contains n pile sizes. Original constraints: 1≤n≤100000, 1≤pile size≤10000, 1≤k≤100000.

输出格式

Output the single integer required by the problem.

样例 1

输入：

3 2
5 4 9

输出：

12

样例 2

输入：

4 3
4 3 6 7

输出：

12

样例 3

输入：

2 100000
1 1

输出：

2

样例说明

The answers to the three public examples are, in order: 12; 12; 2. The examples were checked by independent enumeration, state search, or direct simulation.