Bookshelf (AOJ 0181) by letter
Contest: 3575    RunID: 2376312    Status: Accepted    Date: Sat Jun 17 17:12:17 JST 2017


#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;

#define DEBUG false

int main(){
	
	//1500000	
	int n, m;
	while(cin >> m >> n, m, n){
		vector<ll> w(n);
		rep(i, n) cin >> w[i];
		int l = 0, r = 1500000;
			while (r - l > 1) {
				int mid = (l + r) / 2;
				
				bool flag = false;
				int pos = 0;
				rep(i, m){
					int tmp = 0;
					while(pos != n && tmp + w[pos] <= mid){
						tmp += w[pos];
						pos++;
					}
					if(pos == n) flag = true;
				}
				
				if (flag) r = mid;
				else l = mid;
			}
		
		cout << r << endl;
		
		
	}
	
	
	
	return 0;
}

/*
struct BIT {
  int N;
  vector<ll> data;
  BIT(int n) : N(n), data(n + 1, 0) { }
  void add(int a, ll w) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x] += w;
    }
  }
  ll sum(int a) {
    ll ret = 0;
    for(int x = a; x > 0; x -= x & -x) {
      ret += data[x];
    }
    return ret;
  }
  
  ll sum(int l, int r){//[l, r)
  	return sum(r) - sum(l);
  }
};

BIT bit = BIT(1);
int m, n;

ll dfs(int pos, int rest){
	ll ret = LLINF;
	
	if(rest == 1) return bit.sum(pos, n+1);
	for(int i = 0; i + pos <= n+1; i++){
		ll hoge1 = bit.sum(pos, pos+i);
		ll hoge2 = dfs(pos+i, rest-1);
		cout << "sum(" << pos << ", " << pos+i << "): " << hoge1 << endl;
		cout << "des(" << pos+i << ". " << rest-1 << "): " << hoge2 << endl;
		cout << endl;
		ret = min(ret, hoge1 + hoge2);
	}
	
	return ret;
}

int main(){

	while(cin >> m >> n, m, n){
		bit = BIT(n);
		rep(i, n){
			ll tmp;
			cin >> tmp;
			bit.add(i+1, tmp);
		}
		
		cout << dfs(1, m) << endl;
		
	}
	
	return 0;
}
*/