Розрізання палиці

Вам потрібно розрізати дерев'яну палицю на частини. Найбільш доступна компанія The Analog Cutting Machinery, Inc. (ACM) стягує плату залежно від довжини палиці, яку розрізають. Їхні правила вимагають робити лише один розріз за раз.

Легко помітити, що різний порядок розрізів може призвести до різних витрат. Наприклад, розглянемо палицю довжиною $10$ метрів, яку потрібно розрізати в точках $2,4$ і $7$ метрів від одного кінця. Ось кілька варіантів:

• Можна спочатку розрізати в точці $2$, потім в $4$, а потім в $7$. Це призведе до вартості $10+8+6=24$, оскільки перша палиця була $10$ метрів, друга $8$ метрів, а третя $6$ метрів.

• Інший варіант — спочатку розрізати в точці $4$, потім в $2$, а потім в $7$. Це призведе до вартості $10+4+6=20$, що є вигіднішим.

Ваш начальник покладається на ваші комп'ютерні навички, щоб визначити мінімальну вартість розрізання даної палиці.

Вхідні дані

Вхід складається з кількох тестів. Перший рядок кожного тесту містить довжину палиці $l(l<1000)$, яку потрібно розрізати. Наступний рядок містить кількість розрізів $n(n<50)$, які потрібно зробити.

Наступний рядок містить $n$ додатних чисел $c_i(0<c_i<l)$, що представляють місця для розрізів, задані у строго зростаючому порядку. Рядок з $l=0$ позначає кінець вхідних даних.

Вихідні дані

Виведіть мінімальну вартість розрізання палиці у форматі, наведеному в прикладі.

Приклади