#include<iostream>#include<cstring>#include<cstdio>#include<string>#include<queue>#include<map>#include<algorithm>using namespace std;#define ll long long#define inf 100000000000LL#define M 100000int k[1010][1010];ll f[1010][1010],a[1010];int main(){int n,m,st,ed;while (~scanf("%d%d",&m,&n)){memset(k,0,sizeof(k));for (int i=1;i<=n;i++){scanf("%d",&a[i]);}sort(a+1,a+n+1);a[++n]=m;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)f[i][j]=inf;for (int i=1;i<=n;i++){f[i][i]=a[i]-a[i-1];k[i][i]=i;}for (int step=1;step<n;step++)for (int i=1;i+step<=n;i++){int j=i+step;st=k[i][j-1];ed=k[i+1][j];if (st>ed) swap(st,ed);for (int ki=st;ki<=ed;ki++){ll temp=f[i][ki-1]+f[ki][j]+a[j]-a[i-1];if (temp<f[i][j]){f[i][j]=temp;k[i][j]=ki;}}}printf("%lldn",f[1][n]-m);}}
