最省成本切木棍

題目敘述

木工社要把一根長 L 的木棍，在指定的 n 個位置各鋸一刀。每鋸一刀，成本等於當下被鋸的那一段木棍的長度（鋸開後兩段分別獨立處理）。鋸的順序可以自由安排，請算出完成所有切割的最小總成本。

輸入包含多組測資：每組先給木棍長度 L，再給切點數 n，最後是 n 個切點位置。當 L=0 時輸入結束。

輸入格式

重複讀取：一行 L，一行 n，一行 n 個切點位置；遇到 L=0 結束。

輸出格式

每組測資輸出一行 The minimum cutting is C.，其中 C 是最小總成本。

限制

• 1 ≤ L ≤ 1000
• 1 ≤ n ≤ 50
• 0 < c_i < L，且切點互不相同

範例

範例 1

輸入

100
3
25 50 75
0

輸出

The minimum cutting is 200.

範例 2

輸入

10
1
5
0

輸出

The minimum cutting is 10.

說明

範例 1 中，先切中間 50（成本 100），再各切左右兩段（各 50），共 200。範例 2 只有一刀，要鋸整根木棍，成本就是 10。

提示：把 0 和 L 也當成端點，對區間做 DP。