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>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
vector<int> G;
int m;

bool check(int v)
{
  int cnt = 0;
  int sum = 0;
  rep(i,G.size())
    {
      if(G[i] > v)return false;
      sum += G[i];
      if(sum > v)
	{
	  sum = G[i];
	  cnt++;
	}
    }
  return cnt < m;
}

int main()
{
  int n;
  while(cin >> m >> n,m|n)
    {
      G.resize(n);
      rep(i,n)cin >> G[i];
      //check(1799);
      //return 0;
      int L = 0;
      int R = 1500000;
      int M;
      rep(j,100)
	{
	  M = (L+R)/2;
	  if(!check(M))
	    L = M;
	  else
	    R = M;	      
	}
      cout << R << endl; 
    }
  return 0;
}

C++: #include<iostream>
using namespace std;
int n, m;

bool isIn(int w, int* width){
  int sum = 0, step = 1;
  for (int i = 0; i < n; i++) {
    if(sum + width[i] > w){
      sum = 0;
      step++;
    }
    sum += width[i];
  }
  if(step > m)
    return false;
  return true;
}

int bs(int* width){
  int begin =  0, end = 1500000;
  for (int i = 0; i < n; i++) {
    if(begin < width[i])
      begin = width[i];
  }
  int mid = (begin + end) / 2;
  while(begin < mid){
    if(isIn(mid, width)){
      end = mid;
    }else{
      begin = mid;
    }
    mid = (begin + end) / 2;
  }
  if(isIn(mid, width)){
    return mid;
  }else{
    return mid + 1;
  }
}


int main(int argc, char *argv[]){
  while(cin >> m >> n, n){
    int width[n];
    for (int i = 0; i < n; i++) {
      cin >> width[i];
    }
    std::cout << bs(width) << std::endl;
  }
  return 0;
}

C++: // test1.cpp : Defines the entry point for the console application.
//
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
using namespace std;
queue<int> select, width;

int main(void)
{
	int value[1000], suffix = 0;

	while (1) {
		int stage, nbook, book[100];

		scanf("%d %d", &stage, &nbook);
		if (stage == 0 && nbook == 0) {
			break;
		}
		for (int i = 0; i < nbook; i++) {
			scanf("%d", &book[i]);
		}

		int sum = 0;
		for (int i = 1; i <= nbook; i++) {
			select.push(i);
			sum += book[i - 1];
			width.push(sum);
		}

		int front;
		for (int i = 1; i < stage; i++) {
			int size = select.size();
			for (int j = 0; j < size; j++) {
				front = select.front();
				if (front != nbook) {
					for (int k = front + 1; k <= nbook; k++) {
						sum = 0;
						for (int l = front; l < k; l++) {
							sum += book[l];
						}

						if (width.front() < sum) {
							if (i + 1 == stage) {
								if (k == nbook) {
									width.push(sum);
									select.push(k);
								}
							}
							else {
								width.push(sum);
								select.push(k);
							}
						}
						else {
							if (i + 1 == stage) {
								if (k == nbook) {
									width.push(width.front());
									select.push(k);
								}
							}
							else {
								width.push(width.front());
								select.push(k);
							}
						}
					}
				}
				else {
					width.push(width.front());
					select.push(nbook);
				}
				select.pop();
				width.pop();
			}
		}

		int size = width.size(), min = 100000;
		for (int i = 0; i < size; i++) {
			if (min > width.front()) {
				min = width.front();
			}
			width.pop();
			select.pop();
		}
		value[suffix++] = min;
	}

	for (int i = 0; i < suffix; i++) {
		printf("%d\n", value[i]);
	}

	return 0;
}

C++: #include <iostream>

using namespace std;

typedef unsigned long long ull;

int m, n;
double avg;
ull books[100];
ull min_w = 150001;

void solve(ull max_w, int i, int depth)
{
	if(depth <= m && i==n)
	{
		min_w = (max_w < min_w) ? max_w : min_w;
		return;
	}
	
	ull w = 0;
	for(int k=i; k<n; k++)
	{
		w += books[k];
		ull new_max_w = (max_w < w) ? w : max_w;
		solve(new_max_w, k+1, depth+1);
	}
}

int main()
{
	while( 1 )
	{
		scanf("%d", &m);
		scanf("%d", &n);
		if(m==0 && n==0) break;
		
		for(int i=0; i<n; i++)
		{
			scanf("%llu", &books[i]);
		}
		avg /= (float)n;

		min_w = 1500001;
		solve(0, 0, 0);
		printf("%llu\n", min_w);
	}
}

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

int m,n,*b,ans;

int max(int *l, int size){
	int tmp = l[0];
	for(int i=1; i<size; i++)
		if(tmp < l[i])
			tmp = l[i];
	return tmp;
}

int min(int *l, int size){
	int tmp = l[0];
	for(int i=0; i<size; i++)
		if(tmp > l[i])
			tmp = l[i];
	return tmp;
}

bool bbb(){
	int j=0;
	int a[m];
	for(int i=0; i<m; i++){
		a[i] = 0;
		for(; j<n; j++){
			a[i] += b[j];
			if(a[i] > ans){
				a[i] -= b[j];
				break;
			}
		}
	}
	if(j == n)
		return true;
	else
		return false;
}

void solve(){
	int plus = min(b, n);
	if(plus == 1)
		plus = 10;
	while(true){
		if(bbb())
			return;
		ans += plus;
	}
}

int main(){
	while(true){
		cin >> m >> n;
		if(!m && !n)
			return 0;
		b = new int[n];
		for(int i=0; i< n; i++)
			cin >> b[i];
		ans = max(b, n);
		solve();
		cout << ans << endl;
		delete[] b;
	}
}

C++: #include<iostream>

using namespace std;

int m, n;
int hon[100];

int f(int w) {
	int honIdx = 0;
	for (int i = 0; i < m; i++) {
		int curW = w;
		while (hon[honIdx] <= curW) {
			curW -= hon[honIdx];
			honIdx++;
			if (honIdx == n) return 1;
		}
	}
	return 0;
}

int binsearch_lower_bound() {
  int low = 0; // 範囲の下限
  int high = 1000000 + 1; // 範囲の上限。解はあれば [low, high] の中に存在する
  while (low < high) {
    int mid = (low + high) / 2;  // 中心点（この実装ではオーバーフローしうるので注意）
    int midval = f(mid);  // 中心での値
    
    // 解の範囲を狭める
    if (midval < 1) low = mid + 1;
    else high = mid;
  }
  return low;
}

int main() {
	while(cin >> m >> n, m || n) {
		for (int i = 0; i < n; i++) {
			cin >> hon[i];
		}
		cout << binsearch_lower_bound() << endl;
	}
	return 0;
}

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

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

using namespace std;

bool valid(const vector<int> b, int m, int w) {
  int sum = 0;
  for (int book : b) {
    if (book > w) return false;
    if (sum + book > w) {
      sum = 0;
      --m;
    }
    sum += book;
  }
  return m > 0;
}

int main() {
  while(1){
    int m,n;
    cin>>m>>n;
    if(!m) break;
    vector<int> b(n);
    REP(i,n) cin>>b[i];
    int i = 1 << 27;
    int j = 0;
    while(i > 0) {
      if(!valid(b,m,i+j)) {
        j += i;
      }
      i/=2;
    }
    cout << (j+1) << endl;
  }
  return 0;
}