Cắt thanh gỗ

Một xưởng cưa tính tiền cắt gỗ theo chiều dài của thanh đang được cắt: mỗi nhát cắt tốn số tiền bằng chiều dài của đoạn gỗ chứa nhát cắt đó, và mỗi lần chỉ cắt được một nhát.

Cho một thanh gỗ dài \(L\) mét và \(n\) vị trí cần cắt (tính từ một đầu thanh). Thứ tự thực hiện các nhát cắt ảnh hưởng đến tổng chi phí. Ví dụ, thanh dài \(10\) cần cắt ở \(2, 4, 7\): cắt lần lượt \(2 \to 4 \to 7\) tốn \(10 + 8 + 6 = 24\), còn cắt \(4 \to 2 \to 7\) tốn \(10 + 4 + 6 = 20\).

Hãy tính tổng chi phí nhỏ nhất để cắt thanh gỗ tại đủ \(n\) vị trí đã cho.

Input

Dữ liệu gồm nhiều bộ test. Mỗi bộ test gồm:

• dòng thứ nhất: số nguyên \(L\) (chiều dài thanh);
• dòng thứ hai: số nguyên \(n\) (số vị trí cắt);
• dòng thứ ba: \(n\) số nguyên \(c_1 < c_2 < \dots < c_n\), các vị trí cần cắt.

Dữ liệu kết thúc bằng một dòng chứa \(L = 0\) (không phải bộ test).

Output

Với mỗi bộ test in ra trên một dòng chi phí nhỏ nhất.

Constraints

• \(2 \le L \le 999\)
• \(1 \le n \le 49\), \(0 < c_i < L\), dãy \(c\) tăng ngặt
• Có không quá \(100\) bộ test.

Sample Input

20
3
5 8 14
9
4
2 3 5 7
0

Sample Output

40
21

Explanation

Với bộ đầu tiên: cắt tại \(8\) trước (tốn \(20\)), đoạn \([0,8]\) cắt tại \(5\) (tốn \(8\)), đoạn \([8,20]\) cắt tại \(14\) (tốn \(12\)); tổng \(40\).