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 <algorithm>
#include <vector>

#define loop(i)    for(int lp=0; lp<(i); lp ++)
#define ascent(i,a,b) for(int i=(a); i<(b); i ++)

#define pb push_back

using namespace std;

int m, n;

int max(vector<int> vec) {
	int max = 0;
	ascent(i, 0, n) {
		if(max < vec[i]) max = vec[i];
	}
	
	return max;
}

int main() {
	vector<int> a;
	
	while(cin >> m >> n, m||n) {
		int ans = 0;
		
		a.clear();
		int tmp;
		loop(n) {
			cin >> tmp;
			a.pb(tmp);
		}
		
		int l=0, r=0;
		ascent(i,0,n) {
			r+= a[i];
		}
		int mid;
		while(r-l>1) {
			mid = (l+r)/2;
			
			if(mid < max(a)) {
				l = mid;
			}
			else {
				int count = m-1;
				int a_sum = 0;
				vector<int> tmpvec;
				for(int i=0; i<n; i++) {
					if(a_sum + a[i] > mid) {
						tmpvec.pb(a_sum);
						a_sum = a[i];
						count --;
					}
					else {
						a_sum += a[i];
					}
				}
//				tmpvec.pb(a_sum);
//				cout << mid << " " << count << endl;
//				ascent(i, 0, tmpvec.size()) {
//					cout << " " << tmpvec[i];
//				}
//				cout << endl;
				
				if(count >= 0) {
					ans = mid;
				}
				
				if(count == m || count < 0) l=mid;
				else r=mid;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

C++: #include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int M, N;
int A[100];

int f(int X) {
  int s = 1;
  int w = X;
  rep(i, N) {
    if (w >= A[i]) {
      w -= A[i];
    }
    else {
      s++;
      w = X - A[i];
      if (w < 0) return false;
    }
  }
  return s;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  while (cin >> M >> N) {
    if (N == 0 && M == 0) break;
    rep(i, N) cin >> A[i];
    int lo = *max_element(A, A+N) - 1, hi = 3000000;
    while (hi - lo > 1) {
      int mid = (lo + hi) / 2;
      if (f(mid) <= M) hi = mid;
      else lo = mid;
    }
    cout << hi << "\n";
  }
  return 0;
}

C++: 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int height(vint& v, int w)
{
	int res = 0, pl = 0;
	
	rep(i, v.size())
	{
		if(w < pl + v[i])
		{
			res++;
			
			if(w < v[i]) return INT_MAX;
			
			pl = 0;
		}
		
		pl += v[i];
	}
	
	return res + (pl != 0);
}

int main()
{
	int m, n;
	while(cin >> m >> n && n)
	{		
		vint v(n);
		rep(i, n) cin >> v[i];
		
		double lb = 1, ub = 1500000;
		
		rep(i, 10000)
		{
			double mid = (ub + lb) / 2;
			
			if(height(v, ceil(mid)) <= m) ub = mid;
			else lb = mid;
		}
		
		cout << ceil(ub) << endl;
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
int m,n;
int book[101];
bool check(int width){
  int j=0;
  int sum=0;
  
  for(int i=0;i<n;i++){
    if(book[i] > width){
      return false;
    }
    
    sum += book[i];
    
    if(sum > width){
      j++;
      i--;
      sum = 0;
    }
    if(j == m){
      return false;
    }
  }
  return true;
}
int main(){
  while(1){
    cin>>m>>n;
    if(m == 0 && n == 0) break;
    
    for(int i=0;i<n;i++){
      cin>>book[i];
    }
    
    int left=0,right=1500000;
    while(right - left > 0) {
      int mid = (left + right) / 2;
      if(check(mid)) right = mid;
      else left = mid + 1;
    }
    
    cout<<right<<endl;
  }
}

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

using namespace std;
vector<int> books;

int m, n;

bool judge(int obs)
{
	int sum = 0;
	int cont = 1;
	for(int i = 0; i < books.size(); i++)
	{
		if(books[i] > obs) return false;
		if(sum + books[i] > obs)
		{
			cont++;
			sum = 0;
		}
		sum += books[i];
	}
	return ( (m >= cont)? true : false );
}

int main()
{
	int c;
	while(cin >> m >> n)
	{
		if(m ==0 && n == 0) break;
		for(int i = 0; i < n; i++)
		{
			cin >> c;
			books.push_back(c);
		}
		
		int ub = 1500000, lb = 0;

		while(ub - lb > 1)
		{
			int mid = (ub + lb) / 2;
			if(judge(mid)){
				ub = mid;
			}
			else{
				lb = mid;
			}
		}
		cout << ub << endl;
	}
}

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

int m,n;
int books[110];
int solves();
int search(int a);

int main(){
	while(1){
		cin >> m >> n;
		if(m == 0 && n == 0) break;
		for(int i=0;i<n;i++){
			cin >> books[i];
		}
		int ans = solves();
		cout << ans << endl;
	}
}

int solves(){
	int ub = 0,lb = 2000000000, mid;
	for(int i=0;i<1000;i++){
		mid = (ub + lb) / 2;
		if(search(mid)) lb = mid;
		else ub = mid;
		cout << ub << " " << lb << endl;
	}
	return lb;
}

int search(int a){
	int len = a;
	int cou = 0;
	for(int i=0;i<n;i++){
		while(1){
			if(0 > len-books[i]){
				cou++;
				len = a;
			}
			else break;
			if(cou == m) return 0;
		}
		len -= books[i];
	}
	return 1;
}

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

using namespace std;

int main(void){
	int m,n;
	
	while(cin >> m >> n){
		if(!(m|n)) break;
		int lb=0,ub=1500000;
		int maxi = 0;
		vector<int> books(n);
		for(int i=0;i<n;i++){
			cin >> books[i];
			maxi = max(maxi, books[i]);
		}
		while(ub - lb > 1){
			int mid = (lb + ub) / 2;
			int count=1;
			int tmp=0;
			for(int i=0;i<n;i++){
				if(tmp + books[i] <= mid){
					tmp += books[i];
				}else{
					tmp = books[i];
					count++;
				}
			}
			if(count <= m && mid >= maxi){
				ub = mid;
			}else{
				lb = mid;
			}
		}
		cout << ub << endl;
	}
}