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 <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <numeric>

using namespace std;
using ll = long long;
using ull = unsigned long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll MOD2 = 998244353;
const ll HIGHINF = (ll)1e18;
const ll LOWINF = (ll)1e15;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max<T>(a,b);}
template <class T> void chmin(T& a, const T b){a=min<T>(a,b);}
void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}

int main() {
    int m,n;
    while(1){
        ll m,n; cin >> m >> n;
        if(m==0&&n==0) return 0;
        V<ll> w(n);
        for(int i = 0; i < n; ++i) cin >> w[i];
        
        ll ok = 123456789,ng = 0,md;
        while(ok - ng > 1){
            
            md = (ok + ng)/2;
            
            V<ll> a(m,md);
            
            
            int flg1 = 1;
            int j = 0;
            
            for(int i = 0; i < n; ++i){
                int flg2 = 1;
                for(; j < m; ++j){
                    if(a[j]>=w[i]){
                        a[j] -= w[i];
                        flg2 = 0;
                        break;
                    }
                }
                if(flg2) {
                    flg1 = 0;
                    break;
                }
            }
            (flg1?ok:ng) = md;
        }
        cout << ok << endl;
    }
    
    return 0;
}

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

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

int n,m;
int w[100];

bool test(int wm){
  int d = 0;
  int s = 0;
  REP(i,n){
    if(s + w[i] > wm){
      s = 0;
      d++;
    }
    s += w[i];
  }
  return d < m;
}

int main(){
  while(scanf("%d%d",&m,&n), n+m){
    int low  = 0;
    int high = 0;
    REP(i,n){
      scanf("%d",&w[i]);
      low = max(low, w[i]);
      high += w[i];
    }
    while(low < high){
      int mid = (low + high)/2;
      bool tmp = test(mid);
      if(tmp){
	high = mid - 1;
      }else{
	low  = mid + 1;
      }
    }
    printf("%d\n",low);
  }
  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

long long int len[1000];

int n, m;

bool check(long long int w){
	int count = 0;
	int sum = 0;
	for(int i = 0; i < n; i++){
		if(len[i] > w){
			return false;
		}
	}
	for(int i = 0; i < n; i++){
		sum += len[i];
		if(sum > w){
			sum = len[i];
			count++;
		}
	}
	count += 1;
	return count <= m;
}

long long int bin_search(long long int wmin, long long int wmax){
	if(wmax - wmin <= 1){
		if(check(wmin)){
			return wmin;
		}else{
			return wmax;
		}
	}
	long long int wmid = (wmin + wmax) / 2;
	if(check(wmid)){
		wmax = wmid;
	}else{
		wmin = wmid;
	}
	bin_search(wmin, wmax);
}

int main(){
	
	while(true){
		cin >> m >> n;
		if(n == 0 && m == 0){
			break;
		}
		for(int i = 0; i < n; i++){
			cin >> len[i];
		}
		
		cout << bin_search(0, 2000000) << endl;
	}
	
	return 0;
}

C++: #include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<map>
#include<algorithm>

using namespace std;

int n,m;
int hon[100];
//3 9 5 3 8 2 1 6 9 7 4

int doteki(){
	int d[101][30];
	int p[101];
	p[0]=hon[0];
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			d[i][j]=1<<29;
		}
	}
	for(int i=1;i<m;i++){
		p[i]=p[i-1]+hon[i];
	}
	for(int i=0;i<n;i++){
		d[0][i]=p[0];
	}
	for(int i=0;i<m;i++){
		d[i][0]=p[i];
	}
	for(int i=1;i<m;i++){
		for(int j=1;j<n;j++){
			for(int k=0;k<i;k++){
				d[i][j]=min(max(d[k][j-1],p[i]-p[k]),d[i][j]);
			}
		}
	}
	return d[m-1][n-1];
}
int nibun(){
	int R,L;R=L=0;
	if(n>=m){
		return *max_element(hon,hon+n);
	}
	for(int i=0;i<m;i++){
		L+=hon[i];
	}
	while(1){
		if(R==L){
			return R;
		}
		double H=(double)(R+L)/2;
		
		int dan=0;
		int at=0;
		for(int i=0;i<m;i++){
			if(at+hon[i] <= H){
				at+=hon[i];
			}else{
				at=0;
				dan++;
				at+=hon[i];
			}
		}
		
		if(dan<n){
			L=H;
		}else{
			R=H+0.5;
		}
		
	}
}

int main(){
	
	//3 9 5 3 8 2 1 6 9 7 4
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0&&m==0){
			break;
		}
		for(int i=0;i<m;i++){
			scanf("%d",&hon[i]);
		}
		
		printf("%d\n",doteki());
	}
}