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 <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 + 1;
		} else if( answer == 0 ) {
			return ix;
		} else if( answer == 1 ) {
			high = ix - 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 <iostream>
#include <map>
using namespace std;

int m,n,*b,*l,mp;
map<int,int> hk;

int max(){
	int tmp = l[0];
	for(int i=1; i<m; i++)
		if(tmp < l[i])
			tmp = l[i];
	return tmp;
}

void erase(){
	for(int i=1; i<m; i++)
		l[i] = 0;
}

void solve(int x, int y){
	l[x] = 0;
	for(int i=y; i<n; i++){
		l[x] += b[i];
		if(x != m-1)
			solve(x+1, i+1);
	}
	if(x == m-1){
//		for(int i=0; i<m; i++)
//			cout << l[i] << ' ';
//		cout << endl;
		hk[mp++] = max();
		return;
	}
}

int min(){
	int tmp = hk[0];
	map<int, int>::iterator it = hk.begin();
	while(it!=hk.end()){
		if(tmp > (*it).second)
			tmp = (*it).second;
		it++;
	}
	return tmp;
}

int main(){
	while(true){
		cin >> m >> n;
		if(!m && !n)
			return 0;
		b = new int[n];
		l = new int[m];
		for(int i=0; i< n; i++)
			cin >> b[i];
		mp = 0;
		solve(0, 0);
		cout << min() << endl;
		delete[] b;
		delete[] l;
		hk.clear();
	}
}

C++: #include <iostream>
using namespace std;
int main(){
	while(true){
		int m,n,book[101]={},sum[101]={};
		cin >> m >> n;
		if(m==0) break;
		for(int i=1;i<=n;i++){
			cin >> book[i];
			sum[i]=sum[i-1]+book[i];
		}
		int d=1;
		int u=100000;
		int md;
		while(d+1<u){
//			cout << u << " " << d << endl;
			bool ok=false;
			int j=0,until=0;
			md=(d+u)/2;
			for(int i=0;i<m;i++){
				while(sum[j]-sum[until]<=md){
					j++;
					if(j==n+1){
						ok=true;
						break;
					}
				}
				if(ok) break;
				until=j-1;
			}
			if(ok){
				u=md;
				if(d+1>=u){
					cout << md << endl;
					break;
				}
			}
			else{
				d=md;
				if(d+1>=u){
					cout << md+1 << endl;
					break;
				}
			}
		}
	}
	return 0;
}

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)

int main(){
  int m,n;
  while(cin>>m>>n,m){
    vector<int> thick(n);
    REP(i,n)cin>>thick[i];
    int ans = 0;
    REP(i,n){
      ans += thick[i];
      int nowbook = i + 1;
      int shelf = m - 1;
      while(nowbook < n && shelf > 0){
        int width = 0;
        while(nowbook < n && width + thick[nowbook] <= ans) {
          width += thick[nowbook++];
        }
        shelf--;
      }
      if(nowbook == n){
        cout<<ans<<endl;
        goto END;
      }
    }
END:;
  }
  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) {
			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];
		if (n <= m) {
			cout << *max_element(all(w)) << endl;
			return 0;
		}

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

C++: #include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,a[101],y;
bool nibun(int x){
	int s=0,q=0;
	r(i,n){
		if(s+a[i]<=x)s+=a[i];
		else s=a[i],q++;
	}
	return m>=q+1;
}
main(){
	while(cin>>m>>n,m){
	  y=1e9;
	  r(i,n)cin>>a[i],y=min(y,a[i]);
	  int l=y,r=1e9;
	  while(l<r){
    	int mid=(l+r)/2;
		if(nibun(mid))r=mid;
		else l=mid+1;
	  }
	  cout<<l<<endl;
    }
}

C++: #include<iostream>
//#include<algorithm>
using namespace std;
int m,n,book[100];
bool ok(int x){
  int h=0,d=1;
  for(int i=0;i<n;i++){
    h += book[i];
    if(h>x){
      d++;
      if(d>m) return false;
      h = 0;
      i--;
    }
  }
  return true;
}
int main(){
  while(cin>>m>>n){
    int max=1500000,min=0,s;
    if(m==0&&n==0) break;
    for(int i=0;i<n;i++) cin >> book[i];
    /*if(m>=n){
      sort(book,book+n,greater<int>());
      cout << book[0] << endl;
      }
      else{*/
      while(1){
	s = (max + min) / 2;
	if(ok(s)) max = s;
	else min = s+1;
	if(min==max){
	  cout << max << endl;
	  break;
	}
      }
    }
  //}
  return 0;
}

C++: #include<iostream>

using namespace std;

int m, n;
int hon[100];

int f(int w) {
	int honIdx = 0;
	for (int i = 0; i < m; i++) {
		int curW = w;
		while (hon[honIdx] <= curW) {
			curW -= hon[honIdx];
			honIdx++;
			if (honIdx == n) return 1;
		}
	}
	return 0;
}

int binsearch_lower_bound() {
  int low = 1; // 範囲の下限
  int high = 1500000 + 1; // 範囲の上限。解はあれば [low, high] の中に存在する
  while (low < high) {
    int mid = (low + high) / 2;  // 中心点（この実装ではオーバーフローしうるので注意）
    int midval = f(mid);  // 中心での値
    
    // 解の範囲を狭める
    if (midval < 1) low = mid + 1;
    else high = mid;
  }
  return low;
}

int main() {
	while(cin >> m >> n, m || n) {
		for (int i = 0; i < n; i++) {
			cin >> hon[i];
		}
		cout << binsearch_lower_bound() << endl;
	}
	return 0;
}