Go: package main

import (
	"bufio"
	"os"
	"strings"
	"strconv"
	"fmt"
	)

var scanner = bufio.NewScanner(os.Stdin)
const MAX_WIDTH = 1500000

func main() {
	// 二分探索で探す
	// 二分探索はソート済みの配列に対して、特定の条件を満たす値を
	// 効率よく選択するアルゴリズム
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		m, _ := strconv.Atoi(buf[0])
		n, _ := strconv.Atoi(buf[1])
		if n == 0 && m == 0 {
			break
		}
		books := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			books[i], _ = strconv.Atoi(scanner.Text())
		}
		check := func(width int) bool {
			// widthの幅の本棚に順番にbooksを詰めて行ったら
			// 何段になるのかを確認し、それがmを以下であることを確認する
			shelf_index := 1
			position_in_stage := 0
			for i := 0; i < n; i++ {
				// 入れることができない本がある時点でこのwidthは不採用
				if books[i] > width {
					return false
				}
				// 新たに本を追加することができるかをチェックする
				if position_in_stage + books[i] <= width {
					// 新たに本を入れることができたので、そのステージにおける
					// 現在の本の位置を記録
					position_in_stage += books[i]
				} else {
					// 新たな本を入れることができなかったので、一段下のステージに
					// 入れれば良い
					position_in_stage = books[i]
					shelf_index++ // 本棚のステージ数が増えた
				}
			}
			return shelf_index <= m // 条件を満たすかの確認
		}
		low, high := 0, MAX_WIDTH
		for low < high {
			mid := (low+high)/2
			if check(mid) {
				high = mid
			} else {
				low = mid+1
			}
			// log.Printf("low: %d, high: %d\n", low, high)
		}
		fmt.Println(low)
	}
}

C++: #include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef pair<int, int> P;
const int INF = 1e9;

class C{
  public:
    int n, w, m;
    C(){}
    C(int _n, int _w, int _m){ n = _n; w = _w; m = _m; }
    bool operator > (const C &c) const {
      if(w != c.w) return w > c.w;
      return m < c.m;
    }
};

int main() {
  int M, N;
  while(cin >>M >>N && M){
    vector<int> v(N + 1); FOR(i, 1, N + 1) cin >>v[i];
    FOR(i, 1, v.size()) v[i] += v[i - 1];
    priority_queue<C, vector<C>, greater<C> > open;
    open.push(C(1, 0, 0)); 
    while(!open.empty()){
      C tmp = open.top(); open.pop();
      int n = tmp.n, w = tmp.w, m = tmp.m;
      if(n == N && m == M){ cout <<w <<endl; break; }
      if(m + 1 == M){
        int nw = v[N] - v[n - 1];
        open.push(C(N, max(w, nw), m + 1));
        continue;
      }
      FOR(next, n, N + 1){
        int nw = v[next] - v[n - 1];
        open.push(C(next + 1, max(w, nw), m + 1));
      }
    }
  }
  return 0;
}

C++: #include "bits/stdc++.h"
using namespace std;

#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using pii = pair<int, int>; using vi = vector<int>;
static const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
static const int MOD = (int)(1e9 + 7);

int m, n;
//??¬?£?????????????????????????
bool f(vector<int> &w, int a) {
	int cnt = 1;
	int tmp = 0;
	for (int i = 0; i < w.size(); i++) {
		if (tmp + w[i] > a) {
			if (tmp == 0)return false;
			cnt += 1;
			tmp = 0;
		}
		tmp += w[i];
	}
	if (cnt > m)return false;
	return true;
}

signed main() {
	for (; cin >> m >> n&&m;) {
		vector<int> w(n);
		rep(i, 0, n)cin >> w[i];

		int L = 0, R = 1500001;
		while (L < R) {
			int MID = (L + R) / 2;
			if (f(w, MID))R = MID;
			else L = MID + 1;
		}
		cout << R << endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

bool c(int x, int M, vector<int> &a)
{
    int N = a.size();
    int cnt = 0, sum = 0;
    for (int i = 0; i < N; ) {
        if (a[i] > x) return 0;

        while (i < N && sum < x) {
            sum += a[i++];            
        }
        if (sum > x) {
            i--;
        }                 
        cnt++;
        sum = 0;
    }
    return (cnt <= M);
}

int main()
{
    int M, N;
    while (cin >> M >> N, M) {
        vector<int> a(N);
        for (int i = 0; i < N; i++) {
            cin >> a[i];
        }
        int l = 0, r = 1e9;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (c(mid, M, a)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        cout << r << endl;
    }
    return 0;
}

C++: #include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)

#define f first
#define s second

int main(){
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0)break;
		
		int hon[111];
		rep(i,m){
			cin>>hon[i];
		}
		
		double left=0;
		double right=15000001;
		
		while(1){
			double h=(left+right)/2;
			
			int dan=0;
			int now=0;
			rep(i,m){
				if(now+hon[i]>h){
					now=0;
					i--;
					dan++;
				}else{
					now+=hon[i];
				}
				if(dan>n)break;
			}
			
			if(dan>n){
				left=h;
			}else{
				right=h;
			}
			
			if(right-left<0.0001){
				printf("%d\n",(int)right);
				break;
			}
		}
	}
}

C++: #include <bits/stdc++.h>
using namespace std ;

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) (r).begin(),(r).end()
#define gsort(st,en) sort((st),(en),greater<int>())
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using dict = map<string,int>;
using pii = pair<int,int> ;

const int mod = 1000000007;
constexpr int imax = ((1<<30)-1)*2+1 ;
constexpr int inf = 100000000;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0};
const int dx[] = {0,-1,0,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

template<typename T>
void Unique(vector<T> &v){
  sort(all(v));
  v.erase(unique(all(v)),v.end());
}

template<typename T>
T ston(string& str, T n){
  istringstream sin(str) ;
  T num ;
  sin >> num ;
  return num ;
}

void Ans(bool f){
  if(f) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

int m, n;
bool check(vector<int> v,int mid){
  int h = 1;
  int w = 0;
  rep(i,n){
    if(v[i] > mid){
      return false;
    }
    if(w + v[i] <= mid){
      w += v[i];
    }
    else{
      w = v[i];
      ++h;
    }
  }
  if(h > m){
    return false;
  }
  return true;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(cin >> m >> n&&m&&n){
    vary(int,v,n,0);
    rep(i,n){
      cin >> v[i];
    }
    int lb = 1,ub = 1500000;
    while(1){
      int mid = (lb+ub)/2;
      if(mid == lb) break;
      if(check(v,mid)){
        ub = mid;
      }
      else{
        lb = mid;
      }
    }
    cout << ub << endl;
  }
  return 0;
}