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>
#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;
    int ltmp;
    REP(i,n){
      scanf("%d",&w[i]);
      low = max(low, w[i]);
      high += w[i];
    }
    ltmp = low;
    while(low < high){
      int mid = (low + high)/2;
      bool tmp = test(mid);
      if(tmp){
	high = mid - 1;
      }else{
	low  = mid + 1;
      }
    }
    for(int i = max(ltmp,low-2);; i++){
      if(test(i)){
	printf("%d\n",i);
	break;
      }
    }
  }
  return 0;
}

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

using namespace std;
int m, n;
int ans;

void binarySearch(int count, int left, int right, const vector<int>& page)
{
	int width = (left + right) / 2;
	if(count >= 100)
	{
		ans = right;
		return;
	}
	vector<int> bookShelf(m);
	int numOfStage = 0;
	bool isSmall = false;
	for(int i = 0; i < page.size(); ++i)
	{
		if(bookShelf[numOfStage] + page[i] > width)
		{
			++numOfStage;
			if(numOfStage >= m)
			{
				isSmall = true;
				break;
			}
		}
		bookShelf[numOfStage] += page[i];
	}
	if(isSmall)
	{
		binarySearch(count + 1, width, right, page);
	}
	else
	{
		binarySearch(count + 1, left, width, page);
	}
}

void solve()
{
	while(cin >> m >> n, m || n)
	{
		if(m > n)
		{
			m = n;
		}
		vector<int> page(n);
		for(int i = 0; i < n; ++i)
		{
			cin >> page[i];
		}
		binarySearch(0, 0, 1000000000, page);
		cout << ans << endl;
	}
}

int main()
{
	solve();
	return(0);
}

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;
				}
				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<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
int main(){
	int n,m;
	while(cin>>n>>m,n||m){
		vi in(m);
		rep(i,m)cin>>in[i];
		int r=0,l=15000001;
		int out;
		bool H=0;
		while(1){
			if(l-r<=1)H=true;
			int h=(r+l)/2;
			int c=1;
			int sum=0;
			rep(i,m){
				if(sum==0&&in[i]>h){
					c=1e9;
					break;
				}else if(sum+in[i]>h){
					c++;sum=0;
					i--;
				}else{
					sum+=in[i];
				}
			}
			if(H){
				if(c<=n)out=r;
				else out=l;
				break;
			}
			if(c<=n)l=h;
			else r=h;
		}
		cout<<out<<endl;
	}
}

C++: #include<bits/stdc++.h>
using namespace std;
int books[105],m,c,ri,le,mid,ans,sum[25],n;
bool flag=false;

int main(){
    while(1){
        cin >> m >> n;
        if(n==0&&m==0)break;
        for(int i=0;i<n;i++){
                cin >> books[i];
                ri+=books[i];
        }
        mid=ri/2;
        le=0;

        for(int i=0;i<10000;i++){
            for(int j=0;j<m;j++){
                for(;;){
                    if(c==n){
                        flag=true;
                        break;
                    }
                    if(sum[j]+books[c]>mid)break;
                    else sum[j]+=books[c];
                    c++;
                    }
                }

                if(flag==true){
                    ri=mid;
                    mid=ri/2;
                }else{
                    le=mid;
                    mid=(le+ri)/2;
                }
                flag=false;
                c=0;
                for(int o=0;o<n;o++)sum[o]=0;
            }
            cout << ri << endl;
    }

 return 0;
}

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

#define REP(i, b, e) for(int i = b ; i < e ; i++)
#define rep(i, n) for(int i = 0 ; i < n ; i++)

const int MAX = 1500000;

int m, n;
vector<int> book;

bool check(int v){
  int width = 0, pos = 0;
  rep(i, n){
    if(book[i] > v) return false;
    if(width + book[i] <= v) width += book[i];
    else width = 0, pos++, i--;
  }
  return pos < m;
}
    
int main(){
  while(cin >> m >> n, m|n){
    book.resize(n);
    rep(i, n) cin >> book[i];
    
    int L = 0, R = MAX;
    int M;
    while(L+1 != R){
      M = (L+R) / 2;
      if(check(M)) R = M;
      else L = M;    
    }
    cout << R << endl;
  }
  return 0;
}

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

using namespace std;

#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)

typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pii;


int main(){
	A:;
	int n,m;
	cin>>n>>m;
	if(n==0)return 0;
	
	int sina[101];
	rep(i,m){
		cin>>sina[i];
	}
	
	int st = 0, en = 1500000;
	
	while(1){
		int half = (st+en)/2;
		
		int dan = 0;
		int sum = 0;
		int ind = 0;
		
		bool erflg = false;
		
		//printf("%d %d %d\n",st,en,half);
		while(1){
			//printf("%d %d %d\n",dan,sum,ind);
			if(ind >= m)break;
			if(dan > n)break;
			if(sum+sina[ind]<=half){
				sum += sina[ind];
				ind++;
			}else{
				sum = 0;
				dan++;
			}
			
		}
		
		if(dan>=n){
			st = half;
		}else{
			en = half;
		}
		
		if(st+1 >= en)break;
	}
	
	printf("%d\n",en);
	
	goto A;
}