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 <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
//#include <utility>
//#include <memory>
//#include <functional>
//#include <deque>
//#include <cctype>
//#include <ctime>
//#include <numeric>
//#include <list>
//#include <iomanip>

//#if __cplusplus >= 201103L
//#include <array>
//#include <tuple>
//#include <initializer_list>
//#include <forward_list>
//
//#define cauto const auto&
//#else

//#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif
#define LDcout(x,n) fixed<<setprecision(n)<<x

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
int n,m;
bool check(int a,vint &v){
    int t=0;
    int cnt=0;
    rep(i,v.size()){
        if(a<v[i]) return false;
        if(t+v[i]>a){
            cnt++;
            t=v[i];
        }
        else{
            t+=v[i];
        }
    }
    if(cnt+1<=m) return true;
    return false;
}


void mainmain(){
    // int m,n;
    while(cin>>m>>n){
        if(m==0) return;
        vint v(n);
        rep(i,n) cin>>v[i];
        int l=0;
        int r=INF;
        while(r-l>1){
            int mid=(r+l)/2;
            if(check(mid,v)) r=mid;
            else l=mid;
        }
        cout<<r<<endl;
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
      cout<<fixed<<setprecision(20);
    mainmain();
}

C++: #include <stdio.h>
#include <vector>
#include <algorithm>

#define MAX_SIZE 1500000

using namespace std;

int main(){
	int dansu,kansu,shelf[20],book[100],min_size,left,right,m,dansu_index,max_length;

	while(true){
		scanf("%d %d",&dansu,&kansu);
		if(dansu == 0 && kansu == 0)break;

		max_length = 0;

		for(int i = 0; i < kansu; i++){
			scanf("%d",&book[i]);
			max_length = max(max_length,book[i]);
		}

		min_size = MAX_SIZE;
		left = max_length,right = MAX_SIZE;
		m = (left+right)/2;

		while(left < right){

			for(int i = 0; i < dansu; i++)shelf[i] = m;
			dansu_index = 0;
			for(int i = 0; i < kansu && dansu_index < dansu;){
				if(shelf[dansu_index] >= book[i]){
					shelf[dansu_index] -= book[i];
					i++;
				}else{
					dansu_index++;
				}
			}

			if(dansu_index == dansu){
				left = m + 1;
				m = (left + right)/2;
			}else{
				right = right - 1;
				m = (left + right)/2;
			}
		}

		printf("%d\n",left);

	}

    return 0;
}

C++: #include <iostream>

bool fit(int m, int n, int* w, int width)
{
	int tray = 0;
	int sum_of_w = 0;
	int books;
	for (books=0; books<n; books++) {
		while (sum_of_w + w[books] > width && tray<m) { tray++; sum_of_w = 0; }
		if (tray == m) return false;
		sum_of_w += w[books];
	}
	return true;
}

int getWidth(int m, int n, int* w)
{
	int lb = w[0], ub = 1500000;
	while (lb < ub) {
		if (lb+1==ub) break;
		int mid = (lb + ub) / 2;
		if (fit(m, n, w, mid)) ub = mid;
		else lb = mid;
	}
	if (fit(m, n, w, lb)) return lb;
	else return ub;
}

int main()
{
	int m, n;
	while (true) {
		std::cin >> m >> n;
		if (m == 0) break;
		int* w = new int[n];
		for (int i=0; i<n; i++) std::cin >> w[i];
		std::cout << getWidth(m, n, w) << std::endl;
		delete[] w;
	}
	return 0;
}

C++: #include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
 
using namespace std;
 
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define rep(i,n) REP(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<ll, ll> pll;
 

 
const int INF = 1000000;
const double EPS = 1e-8;
const int mod = 1e9 + 7;
const ll LINF = 1e18;
const double PI = acos(-1);

struct Input
{
	int n;
	char c;
	char str[1024];
	string s;
	ll l;
	int nextInt(){
		scanf("%d", &n);
		return n;
	}
	ll nextLong(){
		scanf("%lld", &l);
		return l;
	}
	char nextChar(){
		scanf("%c", &c);
		return c;
	}
	string next(){
		scanf("%s", str);
		return string(str);
	}
	string nextLine(){
		getline(cin, s);
		return s;
	}
};
Input in;

vi v;
int n, m;

bool check(int mid){
	int w = 0, h = 0;
	for(int i = 0; i < v.size(); i++){
		if(v[i] > mid) return false;
		if(w + v[i] > mid){
			h++;
			w = v[i];
		}
		else{
			w += v[i];
		}
	}
	return h < m;
}

int main(){
	while(1){
		m = in.nextInt(); n = in.nextInt();
		if(m == 0 && n == 0) break;
		v.resize(n);
		rep(i, n) v[i] = in.nextInt();
		int l = 0, r = 1e9;
		rep(i, 100){
			int mid = (l + r) / 2;
			if(check(mid)){
				r = mid;
			}
			else{
				l = mid;
			}
		}
		printf("%d\n", r);
	}
}