#include <iostream>
#include <algorithm>
#include <cstdint>

using namespace std;

int b, n;
int dp[1000][2][100001];

int get(int i, int mode, int a) {
    if (i < 0 && a == 0 && mode == 0) return 0;
    if (i < 0) return INT32_MAX / 2;
    return dp[i][mode][a];
}

int main() {
    cin >> b >> n;
    int arr[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    reverse(arr, arr + n);
    for (int i = 0; i < n; ++i) {
        for (int a = 0; a <= 100000; ++a) {
            dp[i][0][a] = INT32_MAX / 2;
            dp[i][1][a] = INT32_MAX / 2;
            // push down
            if (a - arr[i] >= 0) dp[i][0][a] = min(dp[i][0][a], get(i-1, 0, a - arr[i]));
            if (a - (arr[i] + 1) % b >= 0) dp[i][0][a] = min(dp[i][0][a], get(i-1, 1, a - (arr[i] + 1) % b));
            // push up
            dp[i][1][a] = min(dp[i][1][a], get(i - 1, 0, a) + (b - arr[i]));
            dp[i][1][a] = min(dp[i][1][a], get(i - 1, 1, a) + (b - arr[i] - 1));
        }
    }
    int res = INT32_MAX;
    for (int mode = 0; mode < 2; ++mode) {
        for (int a = 0; a <= 100000; ++a) {
            res = min(res, max(dp[n - 1][mode][a], a));
        }
    }
    cout << res << endl;

    return 0;
}