#include <bits/stdc++.h>
#define fi first
#define se second
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;

template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}

const int N = 2e5 + 5;
const int oo = 1e9;
const int INF = 1e9;
const long long ooo = 1e18;
int b, p;
int A[1003], B[1003];
int dp[60001][2];

int main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);  
    cin >> b >> p;
        // cout << "TES\n"; fflush(stdout);    
    for(int i = p-1; i >= 0; i--) cin >> A[i];
        // cout << "TES\n"; fflush(stdout);
    for(int i = p-1; i >= 0; i--) B[i] = b-A[i]-1;
    B[0]++;

    // cout << "TES\n"; fflush(stdout);

    for(int i = 0; i <= 60000; i++) dp[i][0] = dp[i][1] = INF;
    dp[A[0]][1] = 0;
    dp[0][0] = B[0];

    for(int i = 1; i < p; i++)
    {
        for(int j = 60000; j >= 0; j--)
        {
            int tmp0 = INF, tmp1 = INF;
            if(j >= A[i]) tmp1 = min(tmp1, dp[j-A[i]][1]);
            if(j >= A[i]+1) tmp1 = min(tmp1, dp[j-A[i]-1][0]);

            int x = j;
            tmp0 = min(dp[x][1]+B[i]+1, dp[x][0]+B[i]);
            tmp0 = min(INF, tmp0);
            dp[x][0] = tmp0;
            dp[x][1] = tmp1;
            if(tmp0 != INF || tmp1 != INF)
            {
                // cout << i << " " << j << " ";
                // cout << tmp0 << " " << tmp1 << "\n";
            }
        }
    }
    int res = INF;
    for(int i = 0; i <= 60000; i++)
    {
        res = min(res, max(i, min(dp[i][0],dp[i][1])));
    }
    cout << res << "\n";
}