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

Measured memory_bytes: 1752