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 <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#include <stack>
#include <set>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
    return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
    os<<'[';
    rep(i,a.size()) os<<(i?" ":"")<<a[i];
    return os<<']';
}



int main() {
    for (int m, n; cin >> m >> n, (m | n) != 0;) {
        int bs[100];
        rep(i, n) cin >> bs[i];

        int lb = 0, ub = 1500001;
        while (ub - lb > 1) {
            int mid = (ub + lb) / 2;
            int c = 1;
            int l = 0;
            bool suc = true;
            rep(i, n) {
                if (l + bs[i] > mid) {
                    if (c == m || bs[i] > mid) {
                        suc = false;
                        break;
                    }
                    c++;
                    l = bs[i];
                }
                else {
                    l += bs[i];
                }
            }
            if (suc) ub = mid;
            else lb = mid;
        }
        cout << ub << endl;
    }
    return 0;
}

C++: #include <iostream>
#include <climits>

using namespace std;

int jagde( int *book, int ix, int n, int m )
{
	int sum;
	int j;

	sum = 0;
	j = 0;
	for( int i = 0;i < n;i++ ){
		sum += book[i];
		if( sum > ix ){
			j++;
			i--;
			sum = 0;
		}
	}
	if( j >= m ) return -1;

	ix--;

	sum = 0;
	j = 0;
	for( int i = 0;i < n;i++ ){
		sum += book[i];
		if( book[i] > ix ) return 0;
		if( sum > ix ){
			j++;
			i--;
			sum = 0;
		}
	}
	if( j >= m ) return 0;
	return 1;
}


int answer( int m, int n, int *book )
{
	int low,high;
	int sum[101];

	sum[0] = book[0];
	low = book[0];
	for( int i = 1;i < n;i++ ){
		if( low < book[i] ) low = book[i];
		sum[i] = sum[i - 1] + book[i];
	}

	high = sum[n - 1];

	while( true ){
		int ix = (low + high) / 2;
		int answer = jagde( book, ix, n, m );

		if( answer == -1 ){
			low = ix;
		} else if( answer == 0 ) {
			return ix;
		} else if( answer == 1 ) {
			high = ix;
		}
	}
	return -1;

}

int main(int argc, char const* argv[])
{
	int m,n;
	int book[101];

	while( cin >> m >> n && m != 0 ){
		for( int i = 0;i < n;i++ ) cin >> book[i];

		cout << answer( m, n, book ) << endl;
	}
	return 0;
}

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

int main() {
  int M, N;
  while(cin >> M >> N && M) {
    vector<int> books(N);
    for(int i=0; i<N; i++) {
      cin >> books[i];
    }
    
    int l = 1, r = 1500001;
    while(r - l > 1) {
      int m = (l+r)/2;
      int bpos = 0;
      for(int i=0; i<M; i++) {
	int size = m;
	for(;;) {
	  if(bpos == N) break;
	  if(size - books[bpos] < 0) break;
	  size -= books[bpos++];
	}
	if(bpos == N) break;
      }
      if(bpos == N) {
	r = m;
      } else l = m;
    }
    
    cout << l+1 << endl;
  }
  
  return 0;
}

C++: //2?????¢?´¢????????£????§£????????????????????????????????§??????
#include<cstdio>
#include<iostream>

using namespace std;

int gcd(int m, int n)
{
	if ((0 == m) || (0 == n))
		return 0;
	while (m != n)
	{
		if (m > n) m = m - n;
		else         n = n - m;
	}
	return m;
}




int main(void) {

//	while (1) {

		int floor, n, book[101] = { 0 };
		cin >> floor >> n;

		if (floor == 0)return 0;

		for (int i = 0; i < n; i++) {
			cin >> book[i];
		}

		//?????§??¬?´???°????±???????
		int m = book[0];
		int w_avr = book[0];
		for (int i = 1; i < n; i++) {
			m = gcd(m, book[i]);
			w_avr += book[i];
		}
		//?????????????????§?????¬??????????????????????????°??§?????£?????°??????????????¬????????§?????????
		int ans = w_avr / floor;

		for (int i = 0; i < n; i++) {
			if (ans < book[i]) {
				ans = book[i];
			}
		}
		while (ans%m != 0) {
			ans=ans-1;
		}
		while (1) {
			int count = floor;
			int length = ans;
			int i = 0;
			while (count != 0 && i < n) {
				if (length >= book[i]) {
					length -= book[i];
					i++;
				}
				else {
					length = ans;
					count = count - 1;
				}
			}
			if (count != 0) {
				break;
			}
			ans += m;
		}
		cout << ans << endl;

//	}
}

C++: #include <iostream>

using namespace std;

int m, n;
float avg;
int books[100];

bool judge(int i, int width)
{
	int w = 0;
	int h = 2;
	for(int k=i+1; k<n; k++)
	{
		w += books[k];
		if(w > width)
		{
			w = books[k];
			h++;
		}

		if(h > m) return false;
	}

	return true;
}

int solve()
{
	int width = 0;
	for(int i=0; i<n; i++)
	{
		width += books[i];
		if(width >= avg)
		{
			if(judge(i, width)) return width;
		}
	}

	return -1;
}

int main()
{
	while( 1 )
	{
		cin >> m >> n;
		if(m==0 && n==0) break;
		
		avg = 0.0f;
		for(int i=0; i<n; i++)
		{
			cin >> books[i];
			avg += books[i];
		}
		avg /= (float)n;

		int ans = solve();
		printf("%d\n", ans);
	}
}

C++: #include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
bool C(vector<int>& v, int w, int m){
  int index = 0;
  for(int i = 0; i < m && index < v.size(); i++){
    int count = 0;
    while(index < v.size() && count + v[index] <= w){
      count += v[index++];
    }
  }
  if(index == v.size()) return true;
  else return false;
}

int main(){
  int m,n;
  while(cin>>m>>n,m){
    vector<int> thick(n);
    REP(i,n)cin>>thick[i];
    int up = 15000000;
    int lw = 1;
    while(up - lw > 0){
      int mid = (up + lw) /2;
      if(C(thick,mid,m)){
        up = mid;
      }else{
        lw = mid + 1;
      }
    }
    cout<<up<<endl;
  }
  return 0;
}