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.

Output

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

Constraints

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

Example

Sample input

8 3  
2 3 3

Sample output

13

Note

• Giải thích: Trước tiên, bạn chia que có chiều dài \(8\) thành các que có chiều dài \(3\) và \(5\) (chi phí \(8\)). Sau đó, bạn chia que có chiều dài \(5\) thành các que có chiều dài \(2\) và \(3\) (chi phí \(5\)). Tổng chi phí là \(8 + 5 = 13\).