// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <complex>

#include <cstring>

#include <cstdlib>

#include <string>

#include <cmath>

#include <cassert>

#include <queue>

#include <set>

#include <map>

#include <valarray>

#include <bitset>

#include <stack>

#include <iomanip>

#include <fstream>

using namespace std;



#define REP(i,n) for(int i=0;i<(int)(n);++i)

#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

#define ALL(c) (c).begin(), (c).end()

#define chmax(a,b) (a<b?(a=b,1):0)

#define chmin(a,b) (a>b?(a=b,1):0)

#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)

const int INF = 1<<29;

typedef long long ll;

typedef pair<int,int> pii;



const int MAX_N = 50010;



struct SegSum {

  int bit[MAX_N], n;

  void init(int _n) {

    n = _n;

    memset(bit, 0, sizeof(bit));

  }

  int sum(int i) {              // [1,i]テ」ツ?ョテ・ツ陳?

    int s = 0;

    while(i > 0) {

      s += bit[i];

      i -= i & -i;

    }

    return s;

  }

  int sum2(int a, int b) {      // [a,b]テ」ツ?ョテ・ツ陳?

    return sum(b)-sum(a-1);

  }

  void add(int i, int x) {      // i(>=1)テ」ツ?ォxティツカツウテ」ツ??

    while(i <= n) {

      bit[i] += x;

      i += i & -i;

    }

  }

  void addSeg(int a, int b, int x) {   // [a,b]テ」ツつ遅テ・ツ?凝・ツ環?」ツ?暗」ツつ?

    add(a, x);

    add(b+1, -x);

  }

} dp;



int x[50000];

int sum[50001];

int w,n;



bool ok2(int a, int b) { // [a,b]テ」ツつ津」ツ?偲」ツつ甘」ツ?偲」ツつ甘」ツ?ァティツゥツーテ」ツつ?」ツ?淌」ツ?ィテ」ツ?購テ」ツ?ォテ・ツ?・テ」ツつ凝」ツ?凝」ツ?ゥテ」ツ??」ツ??

  int num = b-a+1;

  int space = num-1;

  // cout << "ok2 " << a << ":" << b << ":" << sum[b+1]-sum[a]+space << endl;

  return sum[b+1]-sum[a] + space <= w;

}



int maxnum(int i, int m) {      // テ・ツ債佚ィツェツ枴テ」ツ?セテ」ツ?ァテ」ツつ津・ツケツ?テ、ツサツ・テ、ツクツ凝」ツ?ァテ・ツ淞凝」ツつ?」ツつ凝」ツ?ィテ」ツ?催」ツ?ォ1ティツ。ツ古」ツ?ォテ・ツ?・テ」ツつ凝・ツ債佚ィツェツ榲」ツ?ョテヲツ閉ーテ」ツ?ョテヲツ慊?・ツ、ツァ

  int low = 0, high = i+1;

  while(low+1<high) {

    int mid = (low+high)/2;

    int a = i-mid;

    int b = i;

    if (ok2(a,b)) low = mid;

    else high = mid;

  }

  return low;

}



bool ok3(int a, int b, int m) {        // [a,b]テ」ツつ津、ツスツ凖ィツ」ツ陛」ツつ津ヲツ個?」ツ?」テ」ツ?ヲティツゥツーテ」ツつ?」ツ?淌」ツ?ィテ」ツ?催・ツケツ?テ、ツサツ・テ、ツクツ凝」ツ?ァwテ」ツつ津・ツ淞凝」ツつ?」ツつ古」ツつ凝」ツ?凝」ツ?ゥテ」ツ??」ツ??

  int num = b-a+1;

  int space = (num-1) * m;

  // cout << a << ":" << b << ":" << sum[b+1]-sum[a]+space << endl;

  return sum[b+1]-sum[a]+space >= w;

}



int minnum(int i, int m) {

  int low = 0, high = i+1;

  while(low+1<high) {

    int mid = (low+high)/2;

    int a = i-mid;

    int b = i;

    if (ok3(a,b,m)) high = mid;

    else low = mid;

  }

  return high;

}



bool ok(int m) {

  if (ok2(0,n-1)) return 1;

  dp.init(n+2);

  dp.add(1,1);

  // cout << "m = " << m << endl;

  REP(i,n) {

    int ma = maxnum(i,m);

    int mi = minnum(i,m);

    // cout << i << " " << i-ma << " " << i-mi << endl;

    if (dp.sum2(i+1-ma,i+1-mi)) {

      dp.add(i+2,1);

      // cout << "ADD!! " << i << " " << ok2(i+1,n-1) << endl;

      if (ok2(i+1, n-1)) return 1;

    }

  }

  return dp.sum2(n+1,n+1);

}





int main() {

  while(cin>>w>>n,w||n) {

    REP(i,n) cin >> x[i];

    REP(i,n) sum[i+1] = sum[i] + x[i];

    int low=0,high=w;

    while(low+1<high) {

      int mid = (low + high) / 2;

      if (ok(mid)) high = mid;

      else low = mid;

    }

    cout << high << endl;

  }

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <complex>

#include <cstring>

#include <cstdlib>

#include <string>

#include <cmath>

#include <cassert>

#include <queue>

#include <set>

#include <map>

#include <valarray>

#include <bitset>

#include <stack>

#include <iomanip>

#include <fstream>

using namespace std;



#define REP(i,n) for(int i=0;i<(int)(n);++i)

#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

#define ALL(c) (c).begin(), (c).end()

#define chmax(a,b) (a<b?(a=b,1):0)

#define chmin(a,b) (a>b?(a=b,1):0)

#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)

const int INF = 1<<29;

typedef long long ll;

typedef pair<int,int> pii;



const int MAX_N = 50010;



bool dp[MAX_N];



int x[50000];

int sum[50001];

int w,n;



inline bool ok2(int a, int b) { // [a,b]をぎりぎりで詰めたときwに入るかどうか

  int num = b-a+1;

  int space = num-1;

  // cout << "ok2 : " << a << "," << b << " : " << sum[b+1]-sum[a]+space << endl;

  return sum[b+1]-sum[a] + space <= w;

}



inline bool ok3(int a, int b, int m) {        // [a,b]を余裕を持って詰めたとき幅m以下でwを埋めれるかどうか

  int num = b-a+1;

  int space = (num-1) * m;

  // cout << "ok3 : " << a << "," << b << " : " << sum[b+1]-sum[a]+space << endl;

  return sum[b+1]-sum[a]+space >= w;

}



bool ok(int m) {

  if (ok2(0,n-1)) return 1;

  int a = 0, b = 0;

  int cnt = 0;

  // REP(i,n+1)dp[i]=0;

  // memset(dp,0,sizeof(dp));

  // cout << "m = " << m << endl;

  dp[0] = 1;

  REP(i,n) {

    while(a<=i&&!ok2(a,i)) {

      if (dp[a]) cnt--;

      a++;

    }

    while(b<=i&&ok3(b,i,m)) {

      if (dp[b]) cnt++;

      b++;

    }

    // cout <<  i << " : " << a << " " << b << " "  << cnt << endl;

    if (cnt) {

      dp[i+1] = 1;

      if (ok2(i+1,n-1)) return 1;

    } else {

      dp[i+1] = 0;

    }

  }

  return 0;

}



int main() {

  while(scanf("%d%d",&w,&n),w||n) {

    REP(i,n) scanf("%d",x+i);

    REP(i,n) sum[i+1] = sum[i] + x[i];

    int low=0,high=w;

    while(low+1<high) {

      int mid = (low + high) / 2;

      if (ok(mid)) high = mid;

      else low = mid;

    }

    cout << high << endl;

  }

}

// Fastest known solution for this problem: