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;

//#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;
		}
		if (f(w, L))cout << L << endl;
		else cout << R << endl;
	}
	return 0;
}

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

int main(){
	long long int book[100], n, m, sum, width, max;
	while(cin >> m >> n){
		if(!m && !n) break;
		sum = 0;
		width = 0;
		max = 0;
		for(int i = 0;i<n;i++){
			cin >> book[i];
			sum += book[i];
		}
		for(int i = 0;i<n;i++){
			width += book[i];
			if(width >= sum / m){
				if(max < width){
					max = width;
				}
				width = 0;
				continue;
			}
		}
		cout << max << endl;
	}
}

C++: #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> PI;
#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()
#define MP make_pair
#define PB push_back

int hon[100];
int m,n;

bool can(int w){
  int dan=1,tw=0;
  rep(i,n){
    if(hon[i]>w)return false;
    if(tw+hon[i]<=w)tw+=hon[i];
    else{
      tw=hon[i];
      ++dan;
    }
    //cout<<dan<<" "<<tw<<endl;
    if(dan>m)return false;
  }
  return true;
}

main(){
  while(cin>>m>>n,m){
    rep(i,n)cin>>hon[i];

    int l=0,r=1500000;

    while(l<r){
      int mid=(l+r)/2;
      //cout<<mid<<endl;
      if(can(mid))r=mid;
      else l=mid+1;
    }
    cout<<l<<endl;
  }
}

C++: #include<iostream>

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

int calc(int t){
    int sum=0, ret=1;
    bool f=false;
    for(int i=0; i<n; i++){
        if(sum+w[i]>t){
            sum=0;
            ret++;
            f=true;
        }
        sum+=w[i];
    }
    if(f==false) return 1500001;
    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 <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main(void)
{
	int M,N;

	while(cin >> M >> N, M){
		priority_queue<long, vector<long>, greater<long> > pq;

		for(int i = 0; i < M; i++)
			pq.push(0);		//本棚初期

		long book;
		while(N > 0){
			cin >> book;

			int pqt = pq.top();	pq.pop();

			pqt += book;
			pq.push(pqt);
			N--;
		}
		while(pq.size()-1 > 0)
			pq.pop();

		cout << pq.top() << endl;
		pq.pop();
	}

	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();
		if(hl[mp-1] < hk[mp])
			goto FIN;
		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);
FIN:;
		cout << min() << endl;
		delete[] b;
		delete[] l;
		hk.clear();
	}
}

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

int m, n;
int a[110];

int chk(int w){
  int ind = 0;
  for(int i=0; i<m; i++){
    int t = 0;
    for(;;){
      if(ind==n) break;
      if(t+a[ind]>w) break;
      
      t += a[ind];
      ind++;
    }
  }
  if(ind==n) return 1;
  else return 0;
  
}

int main(){
  for(;;){
    cin >> m >> n;
    if(m==0 && n==0) break;
    
    for(int i=0; i<n; i++) cin >> a[i];
    
    int il = 0, ir = 1500001;
    while(ir-il>1){
      int mid = (il+ir)/2;
      if(chk(mid)){
        ir = mid;
      }else{
        il = mid;
      }
    }
    cout << il+1 << endl;
  }
  return 0;
}

C++: // 2011/10/19 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int m, n;
		cin >> m >> n;
		if(m==0&&n==0)
			break;

		int B[101];
		for(int i=1; i<=n; i++)
			cin >> B[i];

		int S[101];
		S[0] = 0;
		for(int i=1; i<=n; i++)
			S[i] = S[i-1]+B[i];

		int DP[101][21];

		for(int i=1; i<=n; i++)
			DP[i][1] = S[i];

		for(int j=1; j<=m; j++)
			DP[1][j] = B[1];

		for(int i=2; i<=n; i++){
			for(int j=2; j<=m; j++){
				if(B[i]>=DP[i-1][j-1]){
					DP[i][j] = B[i];
					continue;
				}
				DP[i][j] = DP[i-1][j-1];


				for(int k=i-2; k>=1; k--){
					if(S[i]-S[k]>=DP[k][j-1]){
						if(DP[i][j]>S[i]-S[k])
							DP[i][j] = S[i]-S[k];
						break;
					}
					if(DP[i][j]>DP[k][j-1])
						DP[i][j] = DP[k][j-1];
				}
			}
		}

		cout << DP[n][m] << endl;
	}

	return 0;
}