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 <bits/stdc++.h>
using namespace std;

int main() {
  for(int m, n; cin >> m >> n && (m|n);) {
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    int l = *max_element(a.begin(), a.end()), r = 1500001;
    while(r-l) {
      int mid = (l+r)/2;
      int x = 0, y = 1;
      for(int i = 0; i < n; ++i) {
        if(x + a[i] > mid) {
          x = a[i];
          ++y;
        } else {
          x += a[i];
        }
      }
      if(y <= m) {
        r = mid;
      } else {
        l = mid+1;
      }
    }
    cout << l << endl;
  }
  return 0;
}

C++: // AOL Q.0181
// YAMADA Terushige 2013.4.3.
 
#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
 
using namespace std;

int M,N,D[100];

bool store(int w){
  int sum=0;
  int dan=1;
  for(int i=0;i<N;i++){
    sum+=D[i];
    if(sum>w){
      sum=0;
      dan++;
      if(dan > M) return false;
      i--;
    }      
  }
  return true;
}
 
int main(){
  int wmin,wmid,wmax;
  while(cin >> M >> N){
    if(M == 0 && N == 0) break;
    for(int i=0;i<N;i++){
      cin >> D[i];
    }
    wmin = 1;
    wmax = 1500000;
    while(wmin<wmax){
      wmid = (wmin + wmax)/2;
      if(store(wmid)) wmax = wmid;
      else wmin = wmid +1;
    }
    cout << wmax << endl;
  }
  return 0;
}

C++: #include<iostream>
using namespace std;
#include<iostream>
#include<cstdlib>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define fir first
#define sec second

const int M = 21;
const int inf = 1500000*2;
const int N = 101;
int dp[N][M];
int cost[N][N];
void pre(int n,int *in){
  rep(i,n){
    cost[i][i]=in[i];
    REP(j,i+1,n)cost[i][j]=cost[i][j-1]+in[j];
  }
}

int solve(int n,int m){
  rep(i,n+1)rep(j,m+1)dp[i][j]=inf;
  //dp[0][0]=0;
  REP(i,1,n+1){
    REP(j,1,m+1){
      rep(k,i){
	if (k==0)dp[i][j]=min(dp[i][j],cost[k][i-1]              );
	else     dp[i][j]=min(dp[i][j],max(dp[k][j-1],cost[k][i-1]));
      }
    }
  }
  return dp[n][m];
}

int main(){
  int n,m;
  int in[N];
  while(cin>>m>>n && n){
    rep(i,n)cin>>in[i];
    pre(n,in);
    cout << solve(n,m) << endl;
  }
}

C++: #include<iostream>

using namespace std;
int m, n, w[100];

int calc(int t){
    int sum=0, ret=1;
    for(int i=0; i<n; i++){
        if(sum+w[i]>t){
            sum=0;
            ret++;
        }
        sum+=w[i];
    }
    return ret;
}

int main(){

    while(1){
        cin>> m>> n;
        if(m==0&&n==0) break;
        for(int i=0; i<n; i++){
            cin>> w[i];
        }

        int l=1, h=1500000;
        while(h-l>1){
            int md=(l+h)/2;
            if(calc(md)>m) l=md;
            else h=md;
        }

        cout<< h<< endl;

    }

    return 0;
}

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){
      h = 0;
      d++;
      if(d>m) return false;
      h += book[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 if(!ok(s)) min = s;
	if(min+1==max){
	  cout << max << endl;
	  break;
	}
      }
    }
  }
  return 0;
}

C++: #include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <tuple>
#include <queue>
#include <functional>
using namespace std;
const int INF = 1 << 30;
int main(){
	int m,n;
	while (cin >>m >>n, n) {
		vector<int> a(n);
		for (int &x : a)cin >> x;
		int min = 0, max = 1500000;
		while (min != max) {
			int mid = (min + max) / 2;
			int dan = 0;
			int w = 0;
			for (int x : a) {
				w += x;
				if (w > mid) {
					if (x > mid) {
						dan = m;
						break;
					}
					dan++;
					w = x;
				}
			}
			if (dan < m)max = mid;
			else min = mid + 1;
		}
		cout << min << endl;
	}
	return 0;
}

C++: #include<cstdio>
#include<cstring>
#define INF 1500000
int m,n;
int d[101];

bool check(int x){
	int nx=0,nm=1;
	for(int i=0;i<n;i++){
		if(d[i]>x)return false;
		if(d[i]+nx>x)nm++,nx=d[i];
		else nx+=d[i];
		if(nm>m)return false;
	}
	return true;
}

int main(void){
	while(1){
		scanf("%d%d",&m,&n);
		if(m==0)break;
		for(int i=0;i<n;i++)scanf("%d",&d[i]);
		int l=0,r=1500001;
		for(int i=0;i<30;i++){
			int mid=(l+r)/2;
			if(check(mid))r=mid;
			else l=mid;
		}
		printf("%d\n",r);
	}
	return 0;
}

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

using namespace std;

int m, n;
vector <int> book;

int f(int);

int main(){
	while(1){
		cin >> m >> n;
		if(m == 0 && n == 0)
			break;
		
		book = vector <int> (n);
		for(int i = 0; i < n; i++)
			cin >> book[i];
		
		int low = *max_element(book.begin(), book.end());
		int high;
		for(int i = 0; i < n; i++)
			high += book[i];
		int mid = (low + high) / 2;
		
		while(1){
			if(f(mid) == 1)
				high = mid;
			else
				low = mid + 1;
			
			if(low == high){
				cout << low << endl;
				break;
			}
			mid = (low + high) / 2;
		}
	}
	
	return 0;
}

int f(int width){
	int count = 0;
	int w = width;
	
	for(int i = 0; i < n; i++){
		if(book[i] <= w)
			w -= book[i];
		else{
			count++;
			if(count >= m)
				return 0;
			w = width - book[i];
		}
	}
	return 1;
}

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

using namespace std;

int w[200];

bool judge(int num, int length, int height){
	int count = 0;
	int sum = 0;
	for(int i = 0; i < length; i++){
		if(w[i] > num){
			return false;
		}
		if(sum + w[i] > num){
			count++;
			sum = w[i];
		}else{
			sum += w[i];
		}
	}
	count++;
	if(count <= height){
		return true;
	}
	return false;
}

int binary_search(int lef, int rig, int m, int n){
	int middle = (lef + rig) / 2;
	if(rig - lef <= 1){
		if(!judge(rig, n, m)){
			return lef;
		}else{
			return rig;
		}
	}
	if(judge(middle, n, m)){
		rig = middle;
		return binary_search(lef, rig, m, n);
	}else{
		lef = middle;
		return binary_search(lef, rig, m, n);
	}
}

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