#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)

#define dwn(i, j, k) for (int i = int(j); i >= int(k); -- i)

using namespace std;

typedef pair<int, int> P;

const int N = 1e4 + ;

P dp[][N];

int w[N];

int main() {

    int n, t;

    scanf("%d%d", &t, &n);

    rep(i, , n) scanf("%d", w + i); P tmp;

    auto Enlarge = [&](P &a, P &b) {

        if (a.first == -) a = b;

        else {

            if (a.first > b.first || (a.first == b.first && a.second < b.second)) a = b;

        }

    };

    for (int i = ; i <= n; ++ i) dp[(n & )][i].first = -;

    dp[(n & )][] = P(, );

    dwn(l, n, ) { // i, j 之间还没消去

        int cur = l & , next = cur ^ ;

        // cout << l << ' ' << dp[cur][3].first << ' ' << dp[cur][3].second << '\n';

        for (int i = ; i <= n; ++ i) dp[next][i].first = -;

        for (int i = ; i + l -  <= n; ++ i)

            if (dp[cur][i].first != -) {

                int j = i + l - ;

                // 选第i个

                if (w[i] <= dp[cur][i].second) {

                    tmp = P(dp[cur][i].first, dp[cur][i].second - w[i]);

                    Enlarge(dp[next][i + ], tmp);

                }

                else {

                    tmp = P(dp[cur][i].first + , t - w[i]);

                    Enlarge(dp[next][i + ], tmp);

                }

                // 选第jge

                if (w[j] <= dp[cur][i].second) {

                    tmp = P(dp[cur][i].first, dp[cur][i].second - w[j]);

                    Enlarge(dp[next][i], tmp);

                }

                else {

                    tmp = P(dp[cur][i].first + , t - w[j]);

                    Enlarge(dp[next][i], tmp);

                }

            }

    }

    // cout << dp[0][3].first << ' ' << dp[0][3].second << '\n';

    int ans = ;

    for (int i = ; i <= n; ++ i)

        if (dp[][i].first != -)

            ans = min(ans, dp[][i].first);

    printf("%d\n", ans);

}

/*

4 5

1 1 3 1 2

*/