Thùng kem

Khu vực pantry của VNG Game Studios có n thùng kem, thùng kem thứ i ban đầu có A_i cây kem ($1\leq i \leq n$ và $A_i\leq10^6$). Mỗi khi một thùng kem được mở ra, các nhân viên có thể cùng nhau lấy hết toàn bộ số kem trong thùng đó. Sau khi thùng rỗng, nó sẽ lập tức được châm thêm một lượng kem bằng $1/2$ lượng kem trước đó (làm tròn xuống). Tuy nhiên, vì số lượng có hạn nên kem chỉ được phục vụ trong m lần mở thùng.

Hãy tìm số lượng kem lớn nhất mà các nhân viên có thể lấy được sau m lần mở thùng kem.

Đầu vào:

• Dòng 1: Gồm 2 số nguyên dương $n, m$ lần lượt là số lượng thùng kem và số lần tối đa được mở thùng phục vụ kem.
• Dòng 2: Gồm n số nguyên không âm. Số nguyên thứ i trên dòng là số lượng kem ban đầu trong thùng thứ i.

Đầu ra: Số lượng kem lớn nhất có thể lấy được sau m lần mở thùng.

Subtask 1: $n \leq 10^{4}$ và $m \leq n$ (30%).
Subtask 2: $n \leq 5*10^{5}$ và $m \leq 10^6$ (70%).

Giải thích: Sau 4 lần mở cả 4 thùng kem ban đầu, số kem còn lại trong mỗi thùng lần lượt là $2, 3, 3$, và $4$. Để lấy được nhiều kem nhất, nhân viên sẽ mở tiếp các thùng thứ $2, 3$, và $4$.

Ví dụ 1:

Đầu vào:

4 7
5 6 7 8

Đầu ra:

36