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

using namespace std;

int n,m;
int hon[101];
int nibun(){
	int R,L;R=L=0;
	for(int i=0;i<m;i++){
		L+=hon[i];
	}
	while(1){
		if(R==L){
			return R;
		}
		double H=(double)(R+L)/2;
		
		int dan=0;
		int at=0;
		for(int i=0;i<m;i++){
			if(hon[i]>H){
				dan=10000;
				break;
			}
			if(at+hon[i] <= H){
				at+=hon[i];
			}else{
				at=0;
				dan++;
				at+=hon[i];
			}
		}
		
		if(dan<n){
			L=H;
		}else{
			R=H+0.5;
		}
		
	}
}
int main(){
	int cont=0;
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0&&m==0){
			break;
		}
		for(int i=0;i<m;i++){
			scanf("%d",&hon[i]);
		}
		printf("%d\n",nibun());
	}
}

C++: #include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>
#include <stack>
#include <set>
#include <vector>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
    return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
    os<<'[';
    rep(i,a.size()) os<<(i?" ":"")<<a[i];
    return os<<']';
}



int main() {
    for (int m, n; cin >> m >> n, (m | n) != 0;) {
        int bs[100];
        rep(i, n) cin >> bs[i];

        int lb = 0, ub = 1500001;
        while (ub - lb > 1) {
            int mid = (ub + lb) / 2;
            int c = 1;
            int l = 0;
            bool suc = true;
            rep(i, n) {
                if (l + bs[i] > mid) {
                    if (c == m || l == 0) {
                        suc = false;
                        break;
                    }
                    c++;
                    l = bs[i];
                }
                else {
                    l += bs[i];
                }
            }
            if (suc) ub = mid;
            else lb = mid;
        }
        cout << ub << endl;
    }
    return 0;
}

C++: #include <iostream>

using namespace std;

typedef unsigned long long ull;

int m, n;
ull w[100];

bool b(ull W)
{
	int need = 1;
	ull s = 0;
	for(int i=0; i<n; i++)
	{
		if(w[i] > W) return false;
		if(s+w[i]>W)
		{
			need++;
			s = 0;
		}
		s+=w[i];
	}
	return need <= m;
}

int main()
{
	while( 1 )
	{
		cin >> m >> n;
		if((m|n)==0) break;
		
		for(int i=0; i<n; i++) cin >> w[i];
		
		ull l = 1;
		ull r = 150000;
		while(r-l > 1)
		{
			ull mid = (r + l) / 2;
			if(b(mid)) r = mid;
			else l = mid;
		}

		printf("%llu\n", b(l)?l:r);
	}
}

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

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

void binarySearch(int count, double left, double right, const vector<int>& page)
{
	double width = (left + right) / 2.0;
	if(count >= 100)
	{
		ans = ceil(width);
		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, 3000000, page);
		cout << ans << endl;
	}
}

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

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

using namespace std;

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

int n, m;
int v[100];

bool check(int x) {
	int cnt = 0, pos = 0;
	while (pos < n) {
		cnt++;
		int now = v[pos++];
		while (pos < n && now + v[pos] <= x) now += v[pos++];
	}
	
	return cnt <= m;
}

int main() {
	while (cin >> m >> n, n || m) {
		REP(i, n) scanf("%d", &v[i]);
		
		int r = 1500000, l = -1;
		
		REP(i, 100) {
			int mid = (r + l) / 2;
			if (check(mid)) r = mid;
			else l = mid;
		}
		
		cout << r << endl;
	}
	
	return 0;
}

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

int M,N,B[100];

bool isTokyo(int x){
	int w = 0, h = 1;
	for(int i=0;i<N;){
		if(w+B[i]>x){
			w = 0;
			if(++h>M) return true;
		}
		else w += B[i++];
	}
	return false;
}

int main(){
	while(cin>>M>>N,M||N){
		for(int i=0;i<N;i++) cin>>B[i];
		int l = 0, r = 1500000;
		while(l+1!=r){
			int piv = (l+r)/2;
			if(!isTokyo(piv)) r = piv;
			else l = piv;
		}
		printf("%d\n",r);
	}
	return 0;
}

C++: #include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt" > "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\b.answer"
int main() {
	while (1) {
		int M, N; cin >> M >> N;
		if (!M)break;
		vector<int>as;
		for (int i = 0; i < N; ++i) {
			int a; cin >> a;
			as.emplace_back(a);
		}

		int amin = *max_element(as.begin(),as.end())-1; int amax = 1500001;
		while (amin + 1 != amax) {
			int amid = (amin + amax) / 2;
			{
				int h = 0;
				int num = 0;
				for (int b = 0; b < N; ++b) {
					if (as[b] + num > amid) {
						h++;
						num = as[b];
					}
					else {
						num += as[b];
					}
				}
				if (h >= M) {
					amin = amid;
				}
				else {
					amax = amid;
				}
			}
		}
		cout << amax << endl;
	}
	return 0;
}