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 <cmath>
#include <cstdlib>

using namespace std;

int n, m;
int data[100];
int mid, l, r;

bool check(){
   int w = 0;
   for(int i=0;i<m;i++){
      int sum = 0;
      for(;w<n;w++){
         if(sum + data[w] > mid) break;
         sum += data[w];
      }
      if(w>=n) break;
   }
   if(w >= n) return true;
   return false;
}

main(){
   while(cin >> m >> n && (n || m)){
      for(int i=0;i<n;i++){
         cin >> data[i];
      }
      l = 0;
      r = 1500000;
      while(abs(r-l) > 1){
         mid = (l+r)/2;
         if(check()){
            r = mid;
         }else{
            l = mid;
         }
      }
      cout << r << endl;
   }
   return 0;
}

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

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

vector<int> v;

bool Check(int x,int n,int m)
{
	int i = 0,j = 0,l = 0;

	while(i < m && j < n)
	{
		if(l + v[i] <= x)
		{
			l += v[i];
			i++;
		}
		else
		{
			l = 0;
			j++;
		}
	}

	if(i == m && j < n) return true;
	else return false;
}

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

		rep(i,m)
		{
			int temp;
			cin >> temp;
			v.push_back(temp);
		}

		int l = 0,r = 150000;

		rep(i,1000)
		{
			int mid = (l + r) / 2;
			if(Check(mid,n,m)) 
			{
				r = mid;
			}
			else 
			{
				l = mid;
			}
		}	

		cout << r << endl;
	}
	return 0;
}

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

int main(){
	long long int book[150], n, m, s, max, tmp;
	while(cin >> m >> n){
		if(!m && !n) break;
		max = 0;
		book[0] = 0;
		for(int i = 1;i<=n;i++){
			cin >> tmp;
			book[i] = book[i-1] + tmp;
		}
		tmp = n;
		s = m - 1;
		for(int i = n;i>0, s>0;i--){
			if(book[i] > book[n] / m * s && book[i-1] < book[n] / m * s){
				if(max < book[tmp] - book[i]) max = book[tmp] - book[i];
				tmp = i;
				s--;
			}
		}
		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;
  for(int i=0;i<n;i++){
    if(sum+v[i]>x)cnt++,sum=v[i];
    else sum+=v[i];
  }
  return m>=cnt+1;
}

int main(void){

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

  return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,n) FOR(i,0,n)

int main() {
	int n, m;
	while (cin >> m >> n, n || m) {
		int v[100];
		REP(i, n) scanf("%d", &v[i]);
		
		int sum[100];
		sum[0] = v[0];
		FOR(i,1,n) sum[i] = sum[i - 1] + v[i];
		
		int ans = 1;
		REP(i, n) ans = max(ans, v[i]);
		ans = max(ans, sum[n - 1] / m);
		
		while (true) {
			int cnt = 0, pos = 0;
			while (pos < n) {
				cnt++;
				if (cnt > m) break;
				
				int now = v[pos++];
				while (pos < n && now + v[pos] <= ans) now += v[pos++];
			}
			
			if (cnt <= m) {
				cout << ans << endl;
				break;
			}
			
			ans++;
		}
	}
	
	return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

int main()
{
	int n, m;
	while (scanf("%d %d", &m, &n), n)
	{
		int thick[100];
		for (int i = 0; i < n; ++i)
			scanf("%d", thick+i);

		int maxThick = 0;
		for (int i = 0; i < n; ++i)
			maxThick = max(maxThick, thick[i]);

		int ans = -1;
		for (int t = maxThick; ans == -1; ++t)
		{
			int step = 0;
			int sum = 0;
			int i;
			for (i = 0; i < n && step < m; ++i)
			{
				if (sum + thick[i] > t)
				{
					sum = 0;
					++step;
				}
				sum += thick[i];
			}
			if (i == n && step < m)
				ans = t;
		}
		printf("%d\n", ans);
	}

	return 0;
}

C++: //suhan lee, saitama university;
#include <iostream>
using namespace std;
int putbook(int *list,int bookwi,int stair,int width){

  int dara[100];
  int j=0;
  for(int i=0;i<100;i++)
    dara[i]=0;
  for(int i=0;i<bookwi;i++)
    if(dara[j]+list[i]<=width)
      dara[j]+=list[i];
    else  if(list[i]>width){
      //cout <<"too big book"<<endl;
      return 0;
    }
    else  dara[++j]+=list[i];     
  //  cout <<"hondara";
  for(int i=0;i<stair;i++)
    // cout <<dara[i]<<endl;
    // cout <<"kugiri";
  if(j<stair) return 1;// no problem
  else return 0;
}


int main(){

  int list[100];

  int bookwi,stair,temp;
  int max,min;
  while(1){
    cin >>stair>>bookwi;
    if(bookwi==0&&stair==0)
      return 0;
    for(int i=0;i<bookwi;i++)
      cin>>list[i];
    max=10000000;
    min=1;
    //cout << putbook( list,bookwi,stair,1800 )<<endl;
    while(1){
      if(min==max) break;
      if(putbook( list,bookwi,stair, ( max+min)/2  ) )
	max=(max+min)/2;
      else min= (max+min)/2+1;
      //   cout <<endl<<max<<" max&min   "<<min<<endl;   
    }
    cout <<max<<endl;
  }

}

C++: #include <stdio.h>


long w[100];
int m,n;
long haba[20];
long minhaba=1500000L;


int gethaba(){
        int i;
        long maxhaba=0;
        for(i=0;i<m;i++)
                if(haba[i]>maxhaba)
                        maxhaba=haba[i];

        //printf("maxhaba=%ld\n",maxhaba);

        if(minhaba>maxhaba)
                minhaba=maxhaba;


        /*
                for(i=0;i<m+1;i++)
                        printf("haba %d: %ld\n",i,haba[i]);
        */
        return 0;
}


int oitemiru(int oku,int dan){
        int i;
        for(i=dan;i<=dan+1&&i<m;i++){
                haba[i]+=w[oku];
                if(oku>0)
                        oitemiru(oku-1,i);
                else
                        gethaba();
                haba[i]-=w[oku];
        }
}


main(){
        int i;

        while(1){
                scanf("%d %d",&m,&n);
                if(m==0)break;
                for(i=0;i<n;i++)scanf("%ld",&w[i]);
                for(i=0;i<m;i++)haba[i]=0;
                minhaba=1500000L;

                oitemiru(n-1,0);
                printf("%ld\n",minhaba);
        }
        return 0;
}