#include <iostream>
#include <algorithm>

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;
}

answer.code: In function ‘int get(int, int, int)’:
answer.code:11:23: error: ‘INT32_MAX’ was not declared in this scope
   11 |     if (i < 0) return INT32_MAX / 2;
      |                       ^~~~~~~~~
answer.code:3:1: note: ‘INT32_MAX’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
    2 | #include <algorithm>
  +++ |+#include <cstdint>
    3 | 
answer.code: In function ‘int main()’:
answer.code:22:27: error: ‘INT32_MAX’ was not declared in this scope
   22 |             dp[i][0][a] = INT32_MAX / 2;
      |                           ^~~~~~~~~
answer.code:22:27: note: ‘INT32_MAX’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?
answer.code:32:15: error: ‘INT32_MAX’ was not declared in this scope
   32 |     int res = INT32_MAX;
      |               ^~~~~~~~~
answer.code:32:15: note: ‘INT32_MAX’ is defined in header ‘<cstdint>’; did you forget to ‘#include <cstdint>’?