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<stdio.h>
int dat[100];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		int max=1500000;
		int min=1;
		for(int i=0;i<b;i++)scanf("%d",dat+i);
		for(int i=0;i<b;i++)if(min<dat[i])min=dat[i];
		int res=0;
		int at=1;
		while(max-min>1){
			int M=(max+min)/2;
			res=0;
			at=1;
			for(int i=0;i<b;i++){
				if(res+dat[i]<=M)res+=dat[i];
				else{
					at++;
					res=dat[i];
				}
			}
			if(at<=a)max=M;
			else min=M;
		}
		int M=min;
		res=0;
		at=1;
		for(int i=0;i<b;i++){
			if(res+dat[i]<=M)res+=dat[i];
			else{
				at++;
				res=dat[i];
			}
		}
		if(at<=a)printf("%d\n",M);
		else printf("%d\n",max);
	}
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

ll  n, m, a;
vector<ll> num;

int main(){
	while (cin >> m >> n&&n + m){
		num.clear();
		vector<ll> h(m);
		REP(i, n){
			cin >> a;
			num.push_back(a);
		}
		sort(ALL(num));
		REP(i, n){
			h[0] += num[i];
			sort(ALL(h));
		}
		cout << h[m - 1] << endl;
	}
}

C++: #include <iostream>

using namespace std;

int n, m;
int books[100];

bool solve(int width)
{
	int w, h;
	w = 0;
	h = 1;
	for(int i=0; i<n; i++)
	{
		if(w > width) return false;
		if(w + books[i] > width)
		{
			h++;
			w = 0;
		}
		w += books[i];
	}

	return h <= m;
}

int main()
{
	while( 1 )
	{
		scanf("%d", &m);
		scanf("%d", &n);
		if(m==0 && n==0) break;

		for(int i=0; i<n; i++)
		{
			scanf("%d", &books[i]);
		}

		int upper = 1500001;
		int lower = 0;
		
		while(upper - lower > 1)
		{
			int mid = (upper + lower) / 2;
			if(solve(mid)) upper = mid;
			else  lower = mid;
		}

		printf("%d\n", solve(lower) ? lower : upper);
	}
}

C++: #include <bits/stdc++.h>
 
using namespace std;
 
bool c(int x, int M, vector<int> &a)
{
    int N = a.size();
    int cnt = 0, sum = 0;
    for (int i = 0; i < N; ) {
        if (a[i] > x) return 0;
 
        while (i < N && sum < x) {
            sum += a[i++];            
        }
        if (sum > x) {
            i--;
        }                 
        cnt++;
        sum = 0;
    }
    return (cnt <= M);
}
 
int main()
{
    int M, N;
    while (cin >> M >> N, M) {
        vector<int> a(N);
        for (int i = 0; i < N; i++) {
            cin >> a[i];
        }
        int l = 0, r = 1e9;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (c(mid, M, a)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        cout << r << endl;
    }
    return 0;
}

C++: #include <iostream>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;
bool ok(int m, int n, int s[100], int width) {
	int cnt = 0, size = s[0];
	if(width<size) return false;
	rep2(i,1,n) {
		if(width<size) return false;
		if(width<size+s[i]) {
			size = 0;
			cnt++;
		}
		size += s[i];
	}
	if(width<size) return false;
	if(size>0)cnt++;
	if(m>=cnt) return true;
	return false;
}
int main(){
	int m, n;
	while(cin >> m >> n, (m||n)) {
		int s[100] = {};
		rep(i,n) {
			cin >> s[i];
		}
		int lo = 0, hi = 1500000;
		while(hi-lo>1) {
			int mid = (hi+lo)/2;
			if(ok(m,n,s,mid)) hi = mid;
			else lo = mid;
		}
		cout << hi << endl;
	}
	return 0;
}

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

using namespace std;

long long int len[1000];

int n, m;

bool check(long long int w){
	int count = 0;
	int sum = 0;
	for(int i = 0; i < n; i++){
		if(len[i] > w){
			return false;
		}
	}
	for(int i = 0; i < n; i++){
		sum += len[i];
		if(sum > w){
			sum = len[i];
			count++;
		}
	}
	return count <= m;
}

long long int bin_search(long long int wmin, long long int wmax){
	if(wmax - wmin <= 1){
		if(check(wmin)){
			return wmin;
		}else{
			return wmax;
		}
	}
	long long int wmid = (wmin + wmax) / 2;
	if(check(wmid)){
		wmax = wmid;
	}else{
		wmin = wmid;
	}
	bin_search(wmin, wmax);
}

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

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

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int m,n;
int x[110];

bool f(int c){
	int i,k=0,d=c;
	for(i=0;i<n;i++){
		d-=x[i];
		if(d<0){
			d=c-x[i];
			if(d<0)return false;
			k++;
		}
		if(k==m)return false;
	}
	return true;
}

int main() {
	while(cin>>m>>n,m){
		int i;
		for(i=0;i<n;i++)cin>>x[i];
		int a=1,b=1500000,c;
		while(a!=b){
			c=(a+b)/2;
			if(f(c)){
				b=c;
			}else{
				a=c+1;
			}
		}
		cout<<a<<endl;
	}
	return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

typedef pair<int, int> P;
int main()
{
	int n, m;
	while (scanf("%d %d", &m, &n), n)
	{
		int thick[100];
		for (int i = 0; i < n; ++i)
			scanf("%d", thick+i);

		int maxThick = 0;
		for (int i = 0; i < n; ++i)
			maxThick = max(maxThick, thick[i]);

		int ans = -1;
		for (int t = maxThick; ans == -1; ++t)
		{
			int step = 0;
			int sum = 0;
			int i;
			for (i = 0; i < n && step < m; ++i)
			{
				if (sum + thick[i] > t)
				{
					sum = 0;
					++step;
				}
				sum += thick[i];
			}
			if (i == n && step < m)
				ans = t;
		}
		printf("%d\n", ans);
	}

	return 0;
}