Lưu ý: Bài toán này không chia Subtask.

Cho mảng ~a~ gồm ~n~ số nguyên dương được đánh số từ ~1~ đến ~n~. Thực hiện thao tác sau đây chính xác ~k~ lần:

• Chọn một chỉ số ~i~ ~(1 \le i \le n)~ và gán ~a_i=a_i \times 2~. Lưu ý rằng chỉ số ~i~ có thể được chọn nhiều lần trong số ~k~ thao tác.

Bạn hãy tìm cách thực hiện ~k~ thao tác trên sao cho tổng các phần tử trong mảng sau khi thực hiện ~k~ thao tác đạt giá trị lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \le n \le 10^5~ ~;~ ~1 \le k \le 30)~.
• Dòng thứ hai chứa ~n~ số nguyên của mảng ~a~ ~(1 \le a_i \le 10^8)~.

Output

• In ra giá trị lớn nhất của tổng các phần tử trong mảng.

Examples

Sample Input

3 2
1 2 3

Sample Output

15

Notes

Trong ví dụ, thực hiện ~k~ thao tác như sau:

• Chọn ~i=3~ và gán ~a_3=a_3 \times 2=6~.
• Chọn ~i=3~ và gán ~a_3=a_3 \times 2=12~.

Tổng các phần tử trong mảng là ~a_1+a_2+a_3=1+2+12=15~.