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 REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;

#define DEBUG false

int main(){
	
	//1500000	
	int n, m;
	while(cin >> m >> n, m, n){
		vector<ll> w(n);
		rep(i, n) cin >> w[i];
		int l = 0, r = 1500000;
			while (r - l > 1) {
				int mid = (l + r) / 2;
				
				bool flag = false;
				int pos = 0;
				rep(i, m){
					int tmp = 0;
					while(pos != n && tmp + w[pos] <= mid){
						tmp += w[pos];
						pos++;
					}
					if(pos == n) flag = true;
				}
				
				if (flag) r = mid;
				else l = mid;
			}
		
		cout << r << endl;
		
		
	}
	
	
	
	return 0;
}

/*
struct BIT {
  int N;
  vector<ll> data;
  BIT(int n) : N(n), data(n + 1, 0) { }
  void add(int a, ll w) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x] += w;
    }
  }
  ll sum(int a) {
    ll ret = 0;
    for(int x = a; x > 0; x -= x & -x) {
      ret += data[x];
    }
    return ret;
  }
  
  ll sum(int l, int r){//[l, r)
  	return sum(r) - sum(l);
  }
};

BIT bit = BIT(1);
int m, n;

ll dfs(int pos, int rest){
	ll ret = LLINF;
	
	if(rest == 1) return bit.sum(pos, n+1);
	for(int i = 0; i + pos <= n+1; i++){
		ll hoge1 = bit.sum(pos, pos+i);
		ll hoge2 = dfs(pos+i, rest-1);
		cout << "sum(" << pos << ", " << pos+i << "): " << hoge1 << endl;
		cout << "des(" << pos+i << ". " << rest-1 << "): " << hoge2 << endl;
		cout << endl;
		ret = min(ret, hoge1 + hoge2);
	}
	
	return ret;
}

int main(){

	while(cin >> m >> n, m, n){
		bit = BIT(n);
		rep(i, n){
			ll tmp;
			cin >> tmp;
			bit.add(i+1, tmp);
		}
		
		cout << dfs(1, m) << endl;
		
	}
	
	return 0;
}
*/

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

int m, n;
int w[100];

bool check(int mid){
    int tmpm = 1, nowp = 0;
    for(int i = 0; i < n; i++){
        if(mid < w[i])  return false;

        if(nowp + w[i] <= mid){
            nowp += w[i];
        }else{
            nowp = w[i];
            tmpm++;
        }
    }
    return tmpm <= m;
}

int main(){
    while(1){
        cin >> m >> n;

        if(m + n == 0)  break;

        int minp = 1000001;
        for(int i = 0; i < n; i++){
            cin >> w[i];
            minp = min(minp, w[i]); 
        }

        int l = 1, r = 1500000;

        while(r-l > 1){
            int mid = (r+l) / 2;
            if(check(mid))  r = mid;
            else            l = mid;
        }

        cout << (check(l) ? l : r) << endl;
    }

    return 0;
}

C++: #include <iostream>

using namespace std;

#define BOOK_NUM_MAX 100
#define SHELF_NUM_MAX 20

int book_thick[BOOK_NUM_MAX] = {0};
int dp_table[SHELF_NUM_MAX][BOOK_NUM_MAX] = {-1};

int solve(int m, int n){
	int sum, val, min, tmp;
	
	if(dp_table[m][n] == -1){
		if(m == 1){
			sum = 0;
			for(int i=1; i <= n;++i){
				sum += book_thick[n - i];
			}
			val = sum;
		}else if(n == 0){
			val = 0;
		}else{
			sum = 0;
			min = solve(m-1, n);
			for(int i=1; i <= n;++i){
				sum += book_thick[n - i];
				tmp = solve(m-1,n-i);
				tmp = sum > tmp ? sum : tmp;
				min = min > tmp ? tmp : min; 
			}
			val = min;
		}
		dp_table[m][n] = val;
	}else{
		val = dp_table[m][n];
	}
	return val;
}

int main() {
	
	int m, n;
	int i,j;
	
	while(cin >> m >> n, m!= 0 && n!= 0){
		for(i=0;i<n;++i){
			cin >> book_thick[i];
		}
		
		for(int i=0;i<SHELF_NUM_MAX;++i){
			for(int j=0;j<BOOK_NUM_MAX;++j){
				dp_table[i][j] = -1;
			}
		}
		
		cout << solve(m,n) << endl;
	}
	
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;

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

int n,m;
vector<int> book;

void init(){
  book.clear();
}

bool input(){
  cin>>m>>n;
  if(n==0)return false;
  rep(i,n){
    int a;
    cin>>a;
    book.push_back(a);
  }
  return true;
}

bool ok(int h){
  int len = 0;
  int sum = 0;
  rep(i,book.size()){
    if(len+book[i]<=h)len += book[i];
    else{
      len = 0;
      sum++;
      i--;
    }

    if(sum>=m)return false;
  }
  return true;
}

int solve(){
  int left = 0;
  int right = 1500000;

  while(1){
    int h = (left+right)/2;
    //printf("%d %d %d\n",left,h,right);
    if(ok(h)){
      right = h;
    }else{
      left = h;
    }
    if(left+1>=right)break;
  }

  return right;
}

int main(){
  while(init(),input())cout<<solve()<<endl;
}

C++: #include <iostream>

using namespace std;

int m, n;
int w[100];

bool b(int W)
{
	int need = 1;
	int s = 0;
	for(int i=0; i<n; i++)
	{
		if(w[i] > W) return false;
		if(s+w[i]>W)
		{
			need++;
			s = 0;
		}
		s+=w[i];
	}
	return need <= m;
}

int main()
{
	while( 1 )
	{
		cin >> m >> n;
		if((m|n)==0) break;
		
		for(int i=0; i<n; i++) cin >> w[i];
		
		int l = 1;
		int r = 150000;
		while(r-l > 1)
		{
			int mid = (r + l) / 2;
			if(b(mid)) r = mid;
			else l = mid;
		}

		printf("%d\n", b(l)?l:r);
	}
}

C++: #include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<sstream>
#include<iostream>
using namespace std;
int main(void){

    int m,n;
    while(cin>>m>>n,m){
        int b[200];
        int max_b = 0;
        for(int i = 0;i < n;i++){
            cin>>b[i];
            max_b = max(max_b,b[i]);
        }

        int D = 100;
        int l = 1,r = 1500001;
        int ans = 1600000;
        while(D--){
            int mid = (l+r)/2;
            if(mid < max_b){
                l = mid;
                goto next;
            }
            {
                int idx = 0,br = 0;
                for(int i = 0;i < n;i++){
                    if(br + b[i] <= mid)br = br + b[i];
                    else{
                        idx++;
                        br = b[i];
                        if(idx == m){
                            l = mid;
                            goto next;
                        }
                    }
                }
            }
            r = mid;
            next:;
        }
        cout<<r<<endl;
    }



    return 0;
}