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

const int BOOK_LIMIT = 100;
const int COL_LIMIT = 20;
const int WIDTH_LIMIT = 1500000;

struct Column
{
	int head;
	int w;
};

class Shelf
{
public:
	void input( int numColumn, int numBook )
	{
		width = 0;
		m = numColumn;
		n = numBook;
		int sum = 0;
		int w = 0;
		for( int i = 0; i < n; ++i ){
			int t;
			cin >> t;
			book[ i ] = t;
			sum += t;
			if( w < t ){
				w = t;
			}
		}
		if( sum / m > WIDTH_LIMIT ){
			width = w;
		}else{
			width = ( sum / m > w ? sum / m : w );
		}
	}

	int putAll()
	{
		int ib = putInit();
		int low = m - 1;
		while( ib < n ){
			if( col[ low ].w + book[ ib ] > width ){
				secureSpace( ib );
			}
			if( col[ low ].w == 0 ){
				col[ low ].head = ib;
			}
			col[ low ].w += book[ ib++ ];
		}
		return width;
	}

	int putInit()
	{
		int ib = 0;
		int is = 0;
		while( ib < n && is < m ){
			col[ is ].head = ib;
			col[ is ].w = 0;
			while( ib < n && col[ is ].w + book[ ib ] <= width ){
				col[ is ].w += book[ ib ];
				++ib;
			}
			++is;
		}
		while( is < m ){
			col[ is ].head = -1;
			col[ is ].w = 0;
			++is;
		}
		return ib;
	}

	void secureSpace( int ib )
	{
		int ex = 0x7fffffff;
		int space = 0;
		int is = 1;
		for( int i = 0; i < m - 1; ++i ){
			int s = width - col[ i ].w;
			int e = book[ col[ i + 1 ].head ] - s;
			if( e < ex && e + width < WIDTH_LIMIT ){
				ex = e;
				is = i + 1;
			}
			if( space < s ){
				space = s;
			}
		}
		if( ex == 0x7fffffff ){
			ex = book[ ib ] - space;
		}
		if( ex > book[ ib ] - ( width - col[ m - 1 ].w ) ){
			ex = book[ ib ] - ( width - col[ m - 1 ].w );
		}
		width += ex;
		for( int i = is; i < m; ++i ){
			raiseBook( i );
		}
		if( col[ m - 1 ].w + book[ ib ] > width ){
			secureSpace( ib );
		}
	}

	void raiseBook( int is )
	{
		int upper = is - 1;
		int lower = is;
		if( col[ lower ].head == -1 ){
			return;
		}
		int bw = book[ col[ lower ].head ];
		if( ( bw + col[ upper ].w ) <= width ){
			if( col[ upper ].w == 0 ){
				col[ upper ].head = col[ lower ].head;
			}
			col[ upper ].w += bw;
			++col[ lower ].head;
			col[ lower ].w -= bw;
			if( col[ lower ].w == 0 ){
				col[ lower ].head = -1;
			}
		}
	}

private:
	int book[ BOOK_LIMIT ];
	Column col[ COL_LIMIT ];
	int m, n;
	int width;
};

int main()
{
	int m, n;
	while( cin >> m >> n && ( m || n ) ){
		Shelf s;
		s.input( m, n );
		cout << s.putAll() << endl;
	}

	return 0;
}

C++: import Control.Applicative

main :: IO ()
main = do
  [m, n] <- getInts
  if (m == 0 && n == 0) then return ()
  else do
    ss <- getIntLines n
    print $ rolve m ss
    main

rolve m ss = bin_search (kuwa ss m) 0 1000000

kuwa xs m n = func xs m n n
  where
    func (x:xs) m n l
      | m <= 0 = False
      | m > 0 && xs == [] && n - x >= 0 = True
      | n - x >= 0 = func xs m (n - x) l
      | n - x < 0 = func (x:xs) (m - 1) l l

bin_search func min max
  | (max - min == 1) && (func min) = min
  | (max - min == 1) && (func max) = max
  | func center = bin_search func min center
  | not (func center) = bin_search func center max
  where
    center = div (min + max) 2
---

getInt :: IO Integer
getInt = read <$> getLine

getInts :: IO [Integer]
getInts = map read . words <$> getLine

getIntLines :: Integral a => a -> IO [Integer]
getIntLines n = replicateM (fromIntegral n :: Int) getInt

C++: #include <iostream>
#include <climits>

using namespace std;

int jagde( int *book, int ix, int n, int m )
{
	int hoge[101];
	int j;

	for( int i = 0;i < 101;i++ ) hoge[i] = ix;

	j = 0;
	for( int i = 0;i < n;i++ ){
		hoge[j] -= book[i];
		while( hoge[j] < 0 ){
			j++;
			if( j >= m ) return -1;
			hoge[j] -= book[i];
		}
		if( j >= m ) return -1;
	}
	ix--;
	for( int i = 0;i < 101;i++ ) hoge[i] = ix;

	j = 0;
	for( int i = 0;i < n;i++ ){
		hoge[j] -= book[i];
		while( hoge[j] < 0 ){
			j++;
			if( j >= m ) return 0;
			hoge[j] -= book[i];
		}
		if( j >= m ) return 0;
	}

	return 1;
}


int answer( int m, int n, int *book )
{
	int low,high;
	int sum[101];

	sum[0] = book[0];
	low = book[0];
	for( int i = 1;i < n;i++ ){
		if( low < book[i] ) low = book[i];
		sum[i] = sum[i - 1] + book[i];
	}

	high = sum[n - 1];

	while( true ){
		int ix = (low + high) / 2;
		int answer = jagde( book, ix, n, m );

		if( answer == -1 ){
			low = ix;
		} else if( answer == 0 ) {
			return ix;
		} else if( answer == 1 ) {
			high = ix;
		}
	}
	return -1;

}

int main(int argc, char const* argv[])
{
	int m,n;
	int book[101];

	while( cin >> m >> n && m != 0 ){
		for( int i = 0;i < n;i++ ) cin >> book[i];

		cout << answer( m, n, book ) << endl;
	}
	return 0;
}

C++: #include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
int main()
{
	int a[100],N,M,i,j,k,s,h;
	while(scanf("%d%d",&M,&N),N)
	{
		vector<int>v;
		for(i=0;i<N;++i)scanf("%d",&a[i]);
		for(i=0;i<N;++i)
			for(j=0;j+i<N;v.push_back(s),++j)
				for(s=k=0;k<=i;++k)
					s+=a[j+k];
		sort(v.begin(),v.end(),greater<int>());
		v.erase(unique(v.begin(),v.end()),v.end());
		s=*max_element(a,a+N);
		if(v.back()<s)
		{
			for(i=v.size()-1;;--i)if(v[i]>=s)break;
			v.erase(v.begin()+i,v.end());
		}
		for(i=v.size()-1;;--i)
		{
			for(h=s=j=0;j<N;++j)
			{
				if(s+a[j]>v[i])
				{
					s=a[j];++h;
					if(h>=M)goto E;
				}
				else s+=a[j];
			}
			printf("%d\n",v[i]);
			goto N;
E:;
		}
N:;
	}
	return 0;
}