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 <cstdio>

using namespace std;

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

int n, m;
int v[100];

bool check(int x) {
	int cnt = 0, pos = 0;
	while (pos < n) {
		cnt++;
		int now = v[pos++];
		while (pos < n && now + v[pos] <= x) now += v[pos++];
	}
	
	return cnt <= m;
}

int main() {
	while (cin >> m >> n, n || m) {
		REP(i, n) scanf("%d", &v[i]);
		
		int r = 1500000, l = -1;
		
		REP(i, n) l = max(l, v[i] - 1);
		
		while (r - l > 1) {
			int mid = (r + l) / 2;
			if (check(mid)) r = mid;
			else l = mid;
		}
		
		cout << r << endl;
	}
	
	return 0;
}

C++: #include <iostream>
using namespace std;

int n,m,w[100];


bool C(int width){
	int now = 0,b = 0;
	for(int i = 0;i < n;i++){
		if(now + w[i] > width){
			now = w[i];
			b++;
		}else now += w[i];
		if(b >= m) return false;
	}
	return true;
}

int main(){
	while(cin >> m >> n,n){
		int ma = 0;
		for(int i = 0;i < n;i++) {
			cin >> w[i];
			ma = max(ma,w[i]);
		}
		int low = ma - 1,up = 1500000;
		while(up - low > 1){
			int mid = (low + up) / 2;
			if(C(mid)) up = mid;
			else low = mid;
		}
		cout << up << endl;
	}
	return 0;
}

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 = 0,ub = 1500000;
    while(1){
      int mid = (lb+ub)/2;
      if(mid == ub) break;
      if(check(v,mid)){
        ub = mid;
      }
      else{
        lb = mid+1;
      }
    }
    cout << ub << endl;
  }
  return 0;
}

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

typedef long long ll;

    ll m, n;
    ll w[110];
    
    bool check(ll mid){
        ll sum=0, count=1;
        for(ll i=1; i<=n; i++){
            if(w[i]>mid)    return false;
            sum+=w[i];
            if(sum>mid){
                count++;
                sum=w[i];
            }
        }
        return count<=m;
    }
    
int main(void){
    while(cin >> m >> n){
        if(m+n==0) break;
        for(int i=1; i<=n; i++){
            cin >> w[i];
        }
        ll under=0, upper=1500000;
        while(upper-under>1LL){
            ll mid=(under+upper)/2;
            
            if(! check(mid)){
                under=mid;
            }
            else{
                upper=mid;
            }
        }
    
        cout << upper << "\n";
    }
    
    return 0;
}

C++: #include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

bool check( const VI &as, int m, int width )
{
	int sum = 0, res = 1;
	REP( i, 0, as.size() )
	{
		if ( width < as[i] )
		{
			return false;
		}

		if ( sum + as[i] <= width )
		{
			sum += as[i];
		}
		else
		{
			sum = as[i];
			res++;
		}
	}

	return res <= m;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	while ( true )
	{
		int m, n;
		cin >> m >> n;

		if ( !( m | n ) )
		{
			break;
		}

		VI as( n );
		FOR( a, as )
		{
			cin >> a;
		}

		int lb = 1, ub = 1500000;
		while ( lb + 1 < ub )
		{
			int mid = ( lb + ub ) / 2;

			if ( check( as, m, mid ) )
			{
				ub = mid;
			}
			else
			{
				lb = mid;
			}
		}

		cout << ub << endl;
	}	

	return 0;

}