Vào ngày trung thu vừa qua, cậu bé Mandink muốn làm một chiếc lồng đèn thật đẹp. Để làm được một chiếc lồng đèn, cậu cần có những thanh tre với các độ dài phù hợp. Vì cậu chỉ có một thanh tre duy nhất, nên cậu phải cắt nó ra thành các thanh tre ngắn hơn.

Thanh tre của Mandink có độ dài là ~l~, cậu bắt đầu đánh dấu ~n~ vị trí cần cắt trên thanh tre, vị trí thứ ~i~ cách đầu bên trái thanh tre là ~a_i~. Mỗi khi Mandink cắt một đoạn tre có độ dài ~x~, cậu sẽ mất đi ~x~ sức lực.

Bạn hãy giúp Mandink tìm cách cắt thanh tre sao cho tốn ít sức lực nhất.

Input

Dòng đầu tiên chứa hai số nguyên ~l~ và ~n~ ~(1 \le l \le 1000)~.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1 < a_2 < a_3 < ... < a_n~ ~(0 < a_i < l)~.

Output

In ra trên một dòng là tổng sức lực ít nhất mà Mandink phải bỏ ra để cắt hết ~n~ vị trí.

Giới hạn

• Có ~30\%~ số điểm có ~n = 2~.
• Có ~30\%~ số điểm có ~n \le 10~.
• Có ~40\%~ số điểm có ~n \le 50~.

Sample Input 1

100 3
25 50 75

Sample Output 1

200

Sample Input 2

10 4
4 5 7 8

Sample Output 2

22

Giải thích

Ở ví dụ đầu tiên, cách cắt tối ưu là:

1. Cắt vị trí ~a_2~ tốn ~100~ sức. Tạo thành ~2~ thanh tre nhỏ, mỗi thanh có độ dài ~50~.
2. Cắt vị trí ~a_1~ tốn ~50~ sức.
3. Cắt vị trí ~a_3~ tốn ~50~ sức.

Vậy tổng sức ít nhất phải bỏ ra là ~200~.