d.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <cmath>
#include <string>
#include <cstdlib>
#include <queue>

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;

const int MAXN = 110;
const ll INF = 1e18;
ll dp[MAXN][MAXN], a[MAXN];
int main() {
    IOS;

    int L, n;

    cin >> L >> n;
    a[1] = 0;
    for (int i = 2; i <= n + 1; i++){
        cin >> a[i];
    }
    a[n + 2] = L;
    n += 2;

    for (int len = 1; len <= n; len++){
        int x = 1;
        int y = len;


        while (x <= n && y <= n){
            dp[x][y] = INF;
            if (len <= 2){
                dp[x][y] = 0;
            }
            else{
                //cout << "!! " << x << ' ' << y << "\n";
                for (int k = x + 1; k < y; k++){
                    dp[x][y] = min(dp[x][y], dp[x][k] + dp[k][y] + a[y] - a[x]);
                }
            }
            x++;
            y++;
        }
    }
/*
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cout << dp[i][j] << ' ';
        }
        cout << "\n";
    }
*/
    cout << dp[1][n];

}