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 = 0, R = 1500001;
		while (L < R) {
			int MID = (L + R) / 2;
			if (f(w, MID))R = MID;
			else L = MID + 1;
		}
		cout << R << endl;
	}
	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <time.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FFOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
#define RREP(i,b) FFOR(i,1,b)
#define PB push_back
#define F first
#define S second
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef int ut;
typedef long double ld;
typedef pair<ut,ut> pr;
typedef vector<pr> Vpr;
typedef vector<ut> VI;
typedef pair<ut,pr> ppr;
typedef priority_queue<pr,Vpr, greater<pr> > PQ;
const int SIZE=1e+5 + 1;
const ut INF=1<<30;
const ld eps=1e-6;
const LL mod=1e+9 + 7;

int main() {
	int m, n;
	while(cin >> m >> n && m){
		int books[128];
		REP(i,n){
			cin >> books[i];
		}
		int lb = 0, ub = INF;
		while(ub - lb > 1){
			int mid = (lb + ub) / 2;
			bool ok = true;
			int now = 1, put = 0;
			REP(i,n){
				if(books[i] > mid){
					ok = false;
					break;
				}
				if(put + books[i] <= mid){
					put += books[i];
				}
				else{
					put = books[i];
					now++;
				}
				if(now > m){
					ok = false;
					break;
				}
			}
			if(ok){
				ub = mid;
			}
			else{
				lb = mid;
			}
		}
		cout << ub << endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

int n;
int a[100];

bool check(int x, int r)
{
	int st = 0;
	for (int i = 0; i < n; i++){
		if (a[i] > x) return false;
		if (st + a[i] > x){
			--r;
			st = 0;
		}
		st += a[i];
	}
	
	return r > 0;
}

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

C++: #include <bits/stdc++.h>
using namespace std;

int main() {
  int M, N;
  while(cin >> M >> N && M) {
    vector<int> books(N);
    for(int i=0; i<N; i++) {
      cin >> books[i];
    }
    
    int l = 1, r = 1500001;
    while(r - l > 1) {
      int m = (l+r)/2;
      int bpos = 0;
      for(int i=0; i<M; i++) {
	int size = m;
	for(;;) {
	  if(bpos == N) break;
	  if(size - books[bpos] < 0) break;
	  size -= books[bpos++];
	}
	if(bpos == N) break;
      }
      if(bpos == N) {
	r = m;
      } else l = m;
    }
    
    cout << l+1 << endl;
  }
  
  return 0;
}

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

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    while(true) {
        int M, N;
        cin >> M >> N;
        if(!M && !N) break;
        vector<int> books(N);
        for(int i = 0; i < N; ++i) {
            cin >> books[i];
        }
        int left = 0, right = 1500000;
        while(left < right) {
            int len = (left+right)>>1;
            bool ok = true;
            int pos = 1, acc = 0;
            for(int i = 0; i < N; ++i) {
                if(len < books[i]) {
                    ok = false;
                    break;
                }
                int nacc = acc + books[i];
                if(nacc > len) {
                    ++pos;
                    acc = books[i];
                } else {
                    acc = nacc;
                }
                if(pos > M) {
                    ok = false;
                    break;
                }
            }
            if(ok) right = len;
            else left = len+1;
        }
        cout << left << endl;
    }
    return 0;
}

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

//3 9 5 3 8 2 1 6 9 7 4

using namespace std;

int main(){
	int DP[101][21];
	int dansu,kansu;
	while(1){
		scanf("%d%d",&dansu,&kansu);
		if(dansu==0){
			break;
		}
		int hon[101];
		for(int i=1;i<=kansu;i++){
			scanf("%d",&hon[i]);
		}
		int atu[101];
		atu[0]=0;
		for(int i=1;i<=kansu;i++){
			atu[i]=atu[i-1]+hon[i];
		}
		for(int i=1;i<=kansu;i++){
			for(int j=1;j<=dansu;j++){
				DP[i][j]=210000000;
			}
		}
		for(int i=1;i<=kansu;i++){
			DP[i][1]=atu[i];
		}
		for(int i=1;i<=dansu;i++){
			DP[1][i]=atu[1];
		}
		
		for(int i=2;i<=kansu;i++){
			for(int j=2;j<=dansu;j++){
				for(int k=1;k<i;k++){
					DP[i][j]=min(max(DP[k][j-1],atu[i]-atu[k]),DP[i][j]);
				}
			}
		}
		
		/*
		for(int i=1;i<=kansu;i++){
			for(int j=1;j<=dansu;j++){
				printf("%6d",DP[i][j]);
			}
			puts("");
		}
		for(int i=1;i<=kansu;i++){
			printf("%d ",atu[i]);
		}
		puts("");
		*/
		
		printf("%d\n",DP[kansu][dansu]);
	}
}

C++: #include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

const int INF=1e9;

signed main() {
	int n, m;
	while (1) {
		cin >> n >> m;
		if (n + m == 0) break;
		vi d(m);
		rep(i, 0, m) {
			cin >> d[i];
		}
		int MIN = INF;
		rep(i, 1, m + 1) {
			int sum = 0, cnt = 1, tmp = 0;
			rep(j, 0, i) {
				sum += d[j];
			}
			if (i < m) cnt++;
			rep(j, i, m) {
				if (tmp + d[j] <= sum && tmp + d[j] <= 1500000) {
					tmp += d[j];
				}
				else {
					tmp = d[j];
					cnt++;
				}
			}
			//cout << i << " " << sum << " " << cnt << endl;
			if (cnt <= n) {
				MIN = min(MIN, sum);
			}
		}
		cout << MIN << endl;
	}
}