Minimum Total Weight

Each day, choose one piece and eat floor(w/2) of it, leaving ceil(w/2); the same piece may be chosen repeatedly. Find the minimum total weight after d days.

输入格式

The first line contains n d, and the second line contains n weights; n≤100000, 1≤w≤10000, 1≤d≤2000000.

输出格式

Output the single integer required by the problem.

样例 1

输入：

3 4
30 20 25

输出：

31

样例 2

输入：

1 1
2

输出：

1

样例 3

输入：

2 1
2 3

输出：

4

样例说明

The answers to the three public examples are, in order: 31; 1; 4. All examples have been verified by independent small-scale enumeration or state search.