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
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int M,N;
int W[100];

bool C(int x){
    int cnt=0;
    int cur=0;
    while(cur<N){
        int next=cur;
        int sum=0;
        while(next<N&&sum+W[next]<=x)sum+=W[next++];
        cur=next;
        cnt++;
    }
    return cnt<=M;
}

signed main(){
    while(cin>>M>>N,M||N){
        rep(i,N)cin>>W[i];
        int lb=*min_element(W,W+N)-1,ub=1500000;
        while(ub-lb>1){
            int mid=(ub+lb)/2;
            if(C(mid))ub=mid;
            else lb=mid;
        }
        cout<<ub<<endl;
    }
    return 0;
}

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

using namespace std;
int m, n;
int ans;

void binarySearch(int count, double left, double right, const vector<int>& page)
{
	double width = (left + right) / 2.0;
	if(count >= 100)
	{
		ans = width;
		return;
	}
	vector<int> bookShelf(m);
	int numOfStage = 0;
	bool isSmall = false;
	for(int i = 0; i < page.size(); ++i)
	{
		if(bookShelf[numOfStage] + page[i] > width)
		{
			++numOfStage;
			if(numOfStage >= m)
			{
				isSmall = true;
				break;
			}
		}
		bookShelf[numOfStage] += page[i];
	}
	if(isSmall)
	{
		binarySearch(count + 1, width, right, page);
	}
	else
	{
		binarySearch(count + 1, left, width, page);
	}
}

void solve()
{
	while(cin >> m >> n, m || n)
	{
		if(m > n)
		{
			m = n;
		}
		vector<int> page(n);
		for(int i = 0; i < n; ++i)
		{
			cin >> page[i];
		}
		binarySearch(0, 0, 3000000, page);
		cout << ans << endl;
	}
}

int main()
{
	solve();
	return(0);
}

C++: //AOJ:0181 Persistence

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>

using namespace std;

#define MAX -210000000
#define MIN 210000000
#define HABA 1500000

int n,m,book[101];
int low,high,tana,cunt,mid,flg;
int main(){
	
	while(1){
		scanf("%d %d",&m,&n);
		if(m==0 && n==0) break;
		for(int i=0;i<n;i++) scanf("%d",&book[i]);
		low=0;
		high=HABA;
		while(low<=high/*k!=50*/){
			mid=(low+high)/2;
			//printf("mid=%d\n",mid);
			tana=0;
			cunt=1;
			flg=0;
			for(int i=0;i<n;i++){
				if(tana+book[i]>mid && tana==0){//printf("%d low=%d high=%d mid=%d cunt=%d\n",k,low,high,mid,cunt);
				//	printf("??\???????????¬?????????\n");
					flg=1;
					break;
				}
				if(tana+book[i]>mid){
					cunt++;
					if(cunt>m){
					//	printf("?£?????¶??????????\n");
						flg=1;
						break;
					}
					tana=book[i];
				}else tana+=book[i];
			}
			if(flg==1){
				low=mid+1;
				//printf("k low  %d\n",low);
			}else high=mid-1;
		}
		printf("%d\n",low);
	}
	
	return 0;
}

C++: 
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 <vector>
#include <list>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <deque>
#include <cstdio>
#include <cmath>
#include <complex>
#include <iostream>
#include <iterator>

using namespace std;

#define reps(i,f,t) for(int i=f ; i<int(t) ; ++i)
#define rep(i,n) reps(i, 0, n) 

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

bool C(int m, int n, int book[], int w)
{
	int dan = 1;
	int now = 0;
	rep(i, n){
		if(now+book[i] <= w)
			now += book[i];
		else if(book[i] <= w){
			now = book[i];
			++dan;
		}
		else
			return false;
	}
	return dan <= m;	
}

int main()
{
	int m, n;
	while(scanf("%d", &m), m){
		scanf("%d", &n);
		
		int book[100];
		rep(i, n)
			scanf("%d", &book[i]);
		
		int left = 0, right = 1500000;
		while(right-left>1){
			int mid = (left + right)/2;
			if(C(m, n, book, mid))
				right = mid;
			else
				left = mid;
		}
		printf("%d\n", right);
	}
	return 0;
}

C++: 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
  int m,n;
  int low,high,medi;
  int column,breadth;
  int i;
  bool f;
  while(cin>>m>>n,m,n){
    vector<int>v(n);
    for(i=low=0;i<n;i++){cin>>v[i];low+=v[i];}
    low/=m;
    high=1500000;
    int j=0;
    while(j++<100){
      medi=(low+high)/2;
      breadth=column=f=0;
      for(i=0;i<n;i++){
	if(medi<v[i]){f=1;break;}
	if(breadth+v[i]<=medi){
	  breadth+=v[i];
	}else{
	  breadth=v[i];
	  column++;
	  if(column==m){f=1;break;}
	}
      }
      if(f)low=medi;
      else high=medi;
    }
    cout<<high<<endl;
  }
}

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

using namespace std;
int m, n;
int ans;

void binarySearch(int count, int left, int right, const vector<int>& page)
{
	int width = (left + right) / 2;
	vector<int> bookShelf(m);
	int numOfStage = 0;
	bool isSmall = false;
	for(int i = 0; i < page.size(); ++i)
	{
		if(bookShelf[numOfStage] + page[i] > width)
		{
			++numOfStage;
			if(numOfStage >= m)
			{
				isSmall = true;
				break;
			}
		}
		bookShelf[numOfStage] += page[i];
	}
	if(count >= 100)
	{
		if(isSmall)
		{
			ans = right;
		}
		else
		{
			ans = left;
		}
		return;
	}
	if(isSmall)
	{
		binarySearch(count + 1, width, right, page);
	}
	else
	{
		binarySearch(count + 1, left, width, page);
	}
}

void solve()
{
	while(cin >> m >> n, m || n)
	{
		if(m > n)
		{
			m = n;
		}
		vector<int> page(n);
		for(int i = 0; i < n; ++i)
		{
			cin >> page[i];
		}
		binarySearch(0, 0, 3000000, page);
		cout << ans << endl;
	}
}

int main()
{
	solve();
	return(0);
}