SP15736 BRKSTRNG - Breaking String
题目描述
某种字符串处理语言允许程序员将一个字符串切分成两部分。由于这涉及复制原字符串，因此将一个长度为 $n$ 的字符串切分为两部分需要消耗 $n$ 个单位的时间。假设程序员希望将一个字符串切分成许多段，切分的顺序会直接影响消耗的总时间。
例如，假设我们希望在一个长度为 20 的字符串的第 3、8 和 10 个字符之后进行切分（字符从左端开始从 1 递增编号）。如果按照从左到右的顺序切分：第一次切分消耗 20 个单位时间，第二次切分消耗 17 个单位时间，第三次切分消耗 12 个单位时间，总共消耗 49 个单位时间（参见下方示例）。如果按照从右到左的顺序切分：第一次切分消耗 20 个单位时间，第二次切分消耗 10 个单位时间，第三次切分消耗 8 个单位时间，总共消耗 38 个单位时间。
按从左到右顺序切分的代价：
```
thisisastringofchars (原字符串)
thi sisastringofchars (代价: 20 单位)
thi sisas tringofchars (代价: 17 单位)
thi sisas tr ingofchars (代价: 12 单位)
总计: 49 单位
```
按从右到左顺序切分的代价：
```
thisisastringofchars (原字符串)
thisisastr ingofchars (代价: 20 单位)
thisisas tr ingofchars (代价: 10 单位)
thi sisas tr ingofchars (代价: 8 单位)
总计: 38 单位
```
输入格式
包含多组测试数据。
对于每组测试数据：
* 第一行包含两个整数 $N$（$2 \le N \le 10^7$）和 $M$（$1 \le M \le 1000$，$ M < N$）。$N$ 表示字符串的原始长度，$M$ 表示切分的次数。
* 接下来的行包含 $M$ 个按升序排列的整数 $M_i$（$1 \le M_i < N$），代表从字符串左端算起的切分位置。
读取输入直至文件结束（EOF）。测试数据不会超过 100 组。
输出格式
对于每组测试数据，单行输出完成所有切分所需的最小总代价。