Bạn có một que gậy với độ dài \(x\) và bạn muốn chia nó thành \(n\) que, tổng độ dài các phần bị chia là \(x\).
Mỗi bước bạn có thể lấy bất kì que nào và chia nó thành hai que. Chi phí của một thao tác như vậy là chiều dài của que bị chia.
Chi phí tối thiểu cần thiết để tạo ra các que là bao nhiêu?

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(x\) và \(n\): chiều dài của que và số que trong việc chia
• Dòng thứ hai chứa \(n\) số nguyên \(d_1, d_2, \ldots, d_n\): chiều dài của mỗi que trong việc chia

Constraints

• \(1 \leq x \leq 10^9\)
• \(1 \leq n \leq 2 \cdot 10^5\)
• \(\sum d_i = x\)

Output

• In một số nguyên: chi phí tối thiểu của việc chia

Example

8 3
2 3 3

13