Cắt Thanh Theo Danh Sách · canuc80k0447

Bạn có một thanh dài $x$ . Cần cắt nó thành đúng $n$ đoạn có độ dài $d_{1}, d_{2}, \dots, d_{n}$ ; tổng các độ dài này bằng $x$ .

Trong một thao tác, chọn một đoạn hiện có và cắt nó thành hai đoạn có độ dài nguyên dương. Chi phí của thao tác bằng độ dài của đoạn trước khi cắt.

Hãy tìm tổng chi phí nhỏ nhất để thu được đúng multiset độ dài yêu cầu.

Input

Dòng đầu chứa hai số nguyên $x, n$ .
Dòng thứ hai chứa $n$ số nguyên dương $d_{1}, d_{2}, \dots, d_{n}$ .

Output

In tổng chi phí nhỏ nhất.

Constraints

$1 \leq x \leq 1 0^{9}$ .
$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$d_{i} \geq 1$ với mọi $i$ .
$d_{1} + d_{2} + \dots + d_{n} = x$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 20$ và $x \leq 1000$ .
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung.

Example

Test 1

Input

10 4
1 2 3 4

Output

Giải thích: Có thể tạo hai đoạn $3$ bằng cách tách theo chiều ngược tương ứng với các lần ghép $1 + 2 = 3, 3 + 3 = 6$ , rồi $6 + 4 = 10$ . Tổng chi phí là $3 + 6 + 10 = 19$ .