#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;
using ll = long long;

struct Sum {
    using T = int;
    T operator()(const T& a, const T& b) const
    {
        return a + b;
    }
    T inv(const T& a) const
    {
        return -a;
    }
    static constexpr T identity()
    {
        return 0;
    }
};

template <typename Base>
class BinaryIndexedTree
{
public:
    using T = typename Base::T;
    using AbelGroup = Base;

    BinaryIndexedTree(const int n) : data_num(n), size(1 << (__lg(2 * data_num - 1))), value(size + 1, AbelGroup::identity()) { assert(n > 0); }
    BinaryIndexedTree(const vector<T>& val) : data_num(val.size()), size(1 << (__lg(2 * data_num - 1))), value(size + 1, AbelGroup::identity())
    {
        for (int i = 1; i <= data_num; i++) {
            value[i] = val[i - 1];
        }
        for (int x = 1; x < size; x++) {
            value[x + (x & -x)] = op(value[x + (x & -x)], value[x]);
        }
    }

    T accumulate(const int a) const
    {
        assert(0 <= a and a < data_num);
        int ind = a + 1;
        T sum = AbelGroup::identity();
        while (ind > 0) {
            sum = op(sum, value[ind]);
            ind &= ind - 1;
        }
        return sum;
    }
    T accumulate(const int l, const int r) const  // [l,r)
    {
        assert(0 <= l and l < r and r <= data_num);
        return op(accumulate(r - 1), op.inv(l == 0 ? AbelGroup::identity() : accumulate(l - 1)));
    }

    void add(const int a, const T& val)
    {
        assert(0 <= a and a < data_num);
        int ind = a + 1;
        while (ind <= size) {
            value[ind] = op(value[ind], val);
            ind += ind & (-ind);
        }
    }

    T get(const int a) const
    {
        assert(0 <= a and a < data_num);
        return accumulate(a, a + 1);
    }

private:
    const int data_num;
    const int size;
    const AbelGroup op{};
    vector<T> value;
};

int main()
{
    while (true) {
        int W, N;
        cin >> W >> N;
        if (W == 0 and N == 0) {
            break;
        }
        W++;
        auto getsum = [](const vector<ll>& accum, const int inf, const int sup) {
            return accum[sup] - accum[inf];
        };
        vector<ll> S(N + 1, 0);
        for (int i = 1; i <= N; i++) {
            cin >> S[i];
            S[i]++;
        }
        for (int i = 1; i <= N; i++) {
            S[i] += S[i - 1];
        }
        int inf = -1;
        int sup = W;
        while (sup - inf > 1) {
            const int L = (sup + inf) / 2;
            vector<ll> T(N + 1, 0);
            for (int i = 1; i <= N; i++) {
                T[i] = S[i] + L * i;
            }
            BinaryIndexedTree<Sum> dp(N + 1);
            dp.add(N, 1);
            for (int i = N - 1; i >= 0; i--) {
                if (getsum(S, i, N) <= W) {
                    dp.add(i, 1);
                } else {
                    const ll sobj = W + getsum(S, 0, i);
                    const ll tobj = W + L + getsum(T, 0, i);
                    const int lower = max((int)(lower_bound(T.begin(), T.end(), tobj) - T.begin()), i + 2);
                    const int upper = upper_bound(S.begin(), S.end(), sobj) - S.begin();
                    if (lower < upper and dp.accumulate(lower, upper) > 0) {
                        dp.add(i, 1);
                    }
                }
            }
            if (dp.get(0)) {
                sup = L;
            } else {
                inf = L;
            }
        }
        cout << sup + 1 << endl;
    }
    return 0;
}



Measured memory_bytes: 3872