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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define F first
#define S second
#define INF 1 << 30

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int M, N;
int t[128];
int dp[32][128];

int dfs(int m, int n){
  //  printf("%d %d\n", m, n);
  if(m == M && n == N) return 0;
  if(m == M) return INF;
  if(n == N) return 0;
  if(dp[m][n] >= 0) return dp[m][n];

  int res = INF;
  for(int i = n+1; i < N+1; i++){
    res = min(res, max(dfs(m+1, i), t[i] - t[n]));
  }

  return dp[m][n] = res;
}

int main(){
  while(scanf("%d%d", &M, &N) && M + N){
    memset(dp, -1, sizeof(dp));
    t[0] = 0;
    rep(i, N) scanf("%d", t+i+1);
    rep(i, N) t[i+1] += t[i];

    printf("%d\n", dfs(0, 0));
  }
}

C++: #include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main()
{
	for(int m,n;cin>>m>>n,m|n;){
		vi bs(n);
		rep(i,n) cin>>bs[i];
		
		vvi dp(m,vi(n)); //dp[i][j]:iツ氾板姪堋づ慊づづ個段ツづ泳ツ氾板姪堋づ慊づづ個本ツづーツ置ツつュ
		rep(i,n)
			dp[0][i]=i==0?bs[i]:dp[0][i-1]+bs[i];
		repi(i,1,m){
			rep(j,n){
				dp[i][j]=dp[i-1][j];
				for(int k=0;k<=j;k++){
					int temp=0;
					for(int l=k+1;l<=j;l++)
						temp+=bs[l];
					dp[i][j]=min(dp[i][j],max(dp[i-1][k],temp));
				}
			}
		}
		
		cout<<dp[m-1][n-1]<<endl;
	}
	
	return 0;
}

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

int nibun(long long int a[], int s, int e, int k){
	if(s > e) return s - 1;
	if(a[(s+e)/2] == k){
		return (s+e)/2;
	}
	else if(a[(s+e)/2] < k) nibun(a, (s+e)/2+1, e, k);
	else if(a[(s+e)/2] > k) nibun(a, s, (s+e)/2-1, k);
}

int main(){
	long long int a[150], n, m, s, max, tmp, flag;
	while(cin >> m >> n){
		if(!m && !n) break;
		max = 0;
		a[0] = 0;
		flag = 0;
		for(int i = 1;i<=n;i++){
			cin >> tmp;
			a[i] = a[i-1] + tmp;
		}
		for(int i = 1;i<1500001;i++){
			if(nibun(a, 0, n, i * m) >= n ){
				tmp = 0;
				max = i;
				flag = 1;
				for(int j = 0;j<m;j++){
					if(i < a[nibun(a, 0, n, i * (j + 1))] - a[nibun(a, 0, n, i*j)]){
					 	flag = 0;
					 	break;
					 }
				}
			}
			if(flag) break;
		}
		cout << max << endl;
	}
	return 0;
}

C++: #include<iostream>
using namespace std;
int n, m;
int a[101];
bool search(int v);
int main()
{	
	while (true){
		cin >> m >> n;
		if (m == 0 && n == 0)break;
		for (int i = 0; i < n; i++){
			cin >> a[i];
		}
		int l, r;
		l = 0; r = 1 << 24;
		for (int i = 0; i < 100; i++){
			int mi = (l + r) / 2;
			if (search(mi))r = mi;
			else l = mi;
		}
		cout << r << endl;
	}
}
bool search(int v){
	int n2=0, m2=0,b=0;
	while (n2 < n&&m2 < m){
		if (b + a[n2] <= v){
			b += a[n2];
			n2++;
		}
		else{
			b = 0;
			m2++;
		}
	}
	if (n2 == n&&m2 < m)return true;
	return false;
}

C++: #include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <string>
#include <complex>
#include <functional>
using namespace std;
typedef pair<int,int> P;

int main(){
    int a,b,i;
    int w[100];
    while(cin>>a>>b&&a){
        int max=1500000;
        int min=1,res=0,dan=1;
        for(i=0;i<b;i++) {
            cin>>w[i];
            if(min<w[i]) min=w[i];
        }
        while(max-min>1){
            int hf=(max+min)/2;
            int j;
            res=0;
            dan=1;
            for(j=0;j<b;j++){
                if(res+w[j]<=hf) res+=w[j];
                else{
                    dan++;
                    res=w[j];
                }
            }
            if(dan<=a) max=hf;
            else min=hf;
        }
        int ans=min;
        res=0,dan=1;
        for(i=0;i<b;i++){
            if(res+w[i]<=ans) res+=w[i];
            else{
                dan++;
                res=w[i];
            }
        }
        if(dan<=a) cout<<ans<<endl;
        else cout<<max<<endl;
    }
    return 0;
}

C++: /*
テヲツ鳴ーテ」ツ?療」ツ?湘、ツスツ愿」ツ?」テ」ツ?淌」ツつ「テ」ツつォテ」ツつヲテ」ツδウテ」ツδ暗」ツ?古、ツスツソテ」ツ?暗」ツ?セテ」ツ?崚」ツつ禿」ツ?ァテ」ツ?療」ツ?淌」ツ??

テ、ツコツ古・ツ按?ヲツ篠「テァツエツ「テ」ツ??
*/

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int m,n;
vector<int>v;

bool C(int x){

  int cnt=0,sum=0,i=0;
  while(i<n && cnt<m){
    if(sum+v[i]<=x)sum+=v[i],i++;
    else sum=0,cnt++;
  }
  return i==n && m>cnt;
}

int main(void){

  while(cin >> m >> n,m|n){
    v.clear();

    int l=0,r=100000000,a;
    for(int i=0;i<n;i++){
      cin >> a;
      v.push_back(a);
    }
    
    while(r-l>1){
      int mid=(l+r)/2;
      if(C(mid))r=mid;
      else l=mid;
    }
    cout << r << endl;
  }

  return 0;
}