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>
using namespace std;

int M;
int N;
const int INF = 1500000;
vector<int> book;

bool c(int x) {
	int d = 1;
	int wid = 0;
	for (int i = 0; i < N; i++) {
		wid += book[i];
		if (wid > x) {
			wid = 0;
			d++;
			i--;
		}
	}
	return d <= M;
}

int main(void) {
	while (cin >> M >> N, N) {
		// input
		book.clear();
		int buf;
		for (int i = 0; i < N; i++) {
			cin >> buf;
			book.push_back(buf);
		}

		// calc
		int l = *(max_element(book.begin(), book.end())) - 1, u = INF;
		while (u - l > 1) {
			int mid = (l + u) / 2;
			if (c(mid)) {
				u = mid;
			}else {
				l = mid;
			}
		}

		// output
		cout << u << endl;
	}

	return 0;
}

C++: // 2011/02/20 Tazoe

#include <iostream>
using namespace std;

bool DFS(int m, int n, int thi[100], int i, int lim, int& max)
{
	if(i==n)
		return true;

	if(m==0)
		return false;

	int sum = 0;
	while(i<n){
		if(sum+thi[i]>=lim)
			break;
		sum += thi[i];
		i++;
	}
	if(max<sum)
		max = sum;

	return(DFS(m-1, n, thi, i, lim, max));
}

int main()
{
	while(true){
		int m, n;
		cin >> m >> n;
		if(m==0&&n==0)
			break;

		int thi[101];
		for(int i=0; i<n; i++)
			cin >> thi[i];
		thi[n] = 1;

		int sum = 0;
		int max = 0;
		for(int i=0; i<n; i++){
			sum += thi[i];
			max = sum;
			if(DFS(m-1, n, thi, i+1, sum+thi[i+1], max))
				break;
		}

		cout << max << endl;
	}

	return 0;
}

C++: // 2011/02/22 Tazoe
// Partition Problem

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int m, n;
		cin >> m >> n;
		if(m==0&&n==0)
			break;

		int S[101];
		for(int i=1; i<=n; i++)
			cin >> S[i];

		int P[101];		// S[1]ツつゥツづァS[i]ツづ慊づづ個債計
		int sum = 0;
		for(int i=1; i<=n; i++){
			sum += S[i];
			P[i] = sum;
		}

		int M[101][21];		// iツ氾板姪堋づ慊づづ個要ツ素ツづーツ使ツつ「jツ暗按可コツづ個閉板閉ェツづ可閉ェツ環つオツつスツづつォツづ個催適ツ嘉ー

		for(int i=1; i<=n; i++)
			M[i][1] = P[i];

		for(int j=1; j<=m; j++)
			M[1][j] = S[1];

		for(int i=2; i<=n; i++){
			for(int j=2; j<=m; j++){
				int tmp_min;
				if(M[1][j-1]>P[i]-P[1])
					tmp_min = M[1][j-1];
				else
					tmp_min = P[i]-P[1];
				for(int x=2; x<=i-1; x++){
					int tmp;
					if(M[x][j-1]>P[i]-P[x])
						tmp = M[x][j-1];
					else
						tmp = P[i]-P[x];
					if(tmp<tmp_min)
						tmp_min = tmp;
				}
				M[i][j] = tmp_min;
			}
		}

		cout << M[n][m] << endl;
	}

	return 0;
}

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

const int WIDTH_LIMIT = 1500000;

int main()
{
	int m, n;
	while( cin >> m >> n && ( m || n ) ){
		int memo[ 100 ][ 100 ] = {0};
		set< int > width;
		for( int i = 0; i < n; ++i ){
			cin >> memo[ i ][ i ];
			width.insert( memo[ i ][ i ] );
		}
		for( int i = 0; i < n - 1; ++i ){
			for( int j = i + 1; j < n; ++j ){
				memo[ i ][ j ] = memo[ i ][ j - 1 ] + memo[ j ][ j ];
				if( memo[ i ][ j ] > WIDTH_LIMIT ){
					memo[ i ][ j ] = 0;
				}
				width.insert( memo[ i ][ j ] );
			}
		}
		set< int >::iterator itr = width.begin();
		while( itr != width.end() ){
			int w = *itr;
			int b = 0;
			int s = 0;
			while( b < n && s < m ){
				int p = b;
				while( p < n && memo[ b ][ p ] <= w ){
					++p;
				}
				--p;
				if( b > p ){
					break;
				}
				++s;
				b = p + 1;
			}
			if( b == n ){
				cout << w << endl;
				break;
			}
			++itr;
		}
	}

	return 0;
}

C++: #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#define MAX_M 1500000
#define MIN_M 0
using namespace std;
int book[101];
int main(void)
{
	ios::sync_with_stdio(false);
	int i,j,k;
	int m,n;
	int low,high,mid,ff;
	int tanasuu,sum,mx;
	while(1) {
		cin>>m>>n;
		if(m==0&&n==0) break;
		low=MIN_M;
		high=MAX_M;
		mx=MIN_M;
		ff=0;
		for(i=0;i<n;i++) cin>>book[i];
		while(low<=high) {
			mid=(low+high)/2;
			sum=MIN_M;tanasuu=1;
			for(j=0;j<n;j++) {
				if(m<=n) {
					if(tanasuu<=m) {
						if(mid==sum+book[j]) {
							tanasuu++;
							sum+=book[j];
						}
						else if(mid>sum+book[j]) {
							sum+=book[j];
						}
						else {
							if(mid>=book[j]) {
								sum=book[j];
								tanasuu++;
							}
						}
					}
					else break;
				}
				else {
					ff=1;
					if(mx<book[j]) mx=book[j];
				}
			}
			if(ff==0) {
				if(tanasuu>m){
					low=mid+1;
				}
				else high=mid-1;
			}
			else break;
		}
		if(ff==0) 
			cout<<high<<endl;
		else cout<<mx<<endl;
	}	
	return 0;
}

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

int main(){

  int n, m;
  while(cin >> m >> n, m||n){
    int d[101];
    for(int i = 0; i < n; i++) cin >> d[i];

    int l = 0, r = MAX;
    while(l < r){
      int mid = (l + r) / 2;
      bool judge = true;
      int sum = 0, cnt = 1;
      for(int i = 0; i < n; i++){
        if(sum + d[i] <= mid) sum += d[i];
        else {
          sum = d[i]; cnt++;
          if(sum > mid || cnt > m){
            judge = false; break;
          }
        }
      }
      if(judge) r = mid;
      else l = mid + 1;
    }
    cout << l << endl;
  }

}

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

int n, m, max_a;
int a[100000];

bool check(int k) {
	int num = 1, sum = 0;
	for(int i = 0; i < n; i++) {
		sum += a[i];
		if(sum > k) {
			num++;
			sum = a[i];
		}
	}
	return num <= m;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	while(cin >> m >> n, m) {
		for(int i = 0; i < n; i++) {
			cin >> a[i];
		}
		max_a = *max_element(a, a + n);

		int ng = max_a - 1, ok = max_a * n;
		while(abs(ng - ok) > 1) {
			int mid = (ng + ok) / 2;
			if(check(mid)) ok = mid;
			else ng = mid;
		}

		cout << ok << endl;
	}
}

C++: #include <iostream>

using namespace std;

int m, n;

int books[100];

bool Check(int breadth){
  int stage = 0;
  int remaining = breadth;
  for(int i=0; i<n; i++){
	if(remaining - books[i] < 0){
	  stage++;
	  remaining = breadth;
	  if(stage >= m){
		return false;
	  }
	}
	remaining -= books[i];
  }
  return true;
}

void Solve(int max_book){
  int left = max_book-1;
  int right = 1500000;
  while(right - left > 1){
	int mid = (right + left)/2;
	if(Check(mid)){
	  right = mid;
	}else{
	  left = mid;
	}
  }
  cout << right << endl;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(1){
	cin >> m >> n;
	if(m == 0){
	  return 0;
	}
	int max_book = -1;
	for(int i=0; i<n; i++){
	  cin >> books[i];
	  if(books[i] > max_book){
		max_book = books[i];
	  }
	}
	Solve(max_book);
  }
  
  
  return 0;
}