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>
using namespace std;
const double EPS = 1e-9;

int n , m;
int book[100];
double simulate(double width){
	int height = 0;
	double remain = 0;
	for(int i = 0 ; i < n ; i++){
		if( remain - book[i] < -EPS){
			height++;
			remain = width; 
		}
		remain -= book[i];
		if( remain < -EPS) return false;
	}
	return height <= m;
}

int main(){
	while(cin >> m >> n && (m||n) ){
		for(int i = 0 ; i < n ; i++) cin >> book[i];
		int ans = 1e9;
		
		double l = 0 , r = 1500000;
		for(int i = 0 ; i < 128 ; i++){
			double mid = (l+r) / 2; //切り上げ(いろいろな都合で)
			if( simulate(mid) ){ //midで入れるのに成功したらrをmにする
				r = mid;
			}else{
				l = mid;		//midで入れるのに失敗したら
			}
		}
		printf("%.lf\n",l);
		/*
		for(int i = 0 ; i < n ; i++){
			int sum = 0;
			for(int j = i ; j < n ; j++){
				sum += book[j];
				if( simulate(sum) ) ans = min( ans , sum );
			}
		}
		cout << ans << endl;
		*/
	}
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

int height(vint& v, int w)
{
	int res = 0, pl = 0;
	
	rep(i, v.size())
	{
		if(w < pl + v[i])
		{
			res++;
			
			if(w < v[i]) return 1 << 30;
			
			pl = 0;
		}
		
		pl += v[i];
	}
	
	return res + (pl != 0);
}

int main()
{
	double m, n;
	while(cin >> m >> n && n)
	{		
		vint v(n);
		rep(i, n) cin >> v[i];
		
		double lb = 1, ub = 1500000;
		
		rep(i, 10000)
		{
			double mid = (ub + lb) / 2;
			
			if(height(v, ceil(mid)) <= m) ub = mid;
			else lb = mid;
		}
		
		cout << ceil(ub) << endl;
	}
}

C++: #include <iostream>

using namespace std;

int m;
int n;
int a[128];

bool check(int x) {
  int sum = 0;
  int cnt = 1;

  for (int i = 0; i < n; i++) {
    if (a[i] > x)
      return false;
    sum += a[i];
    if (sum > x) {
      ++cnt;
      sum = a[i];
    }
  }
  
  return cnt <= m;
}

int solve() {

  int lo = 0;
  int hi = 1500000;

  while (hi - lo > 1) {
    int mi = (lo + hi) / 2;
    if (check(mi))
      hi = mi;
    else
      lo = mi;
  }

  return hi;
}


int main(int argc, char *argv[])
{
  while (1) {
    cin >> m >> n;
    if (!n && !m)
      break;
    for (int i = 0; i < n; i++)
      cin >> a[i];
    cout << solve() << endl;
  }
  return 0;
}

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

#define UP_LIMIT 1
#define DOWN_LIMIT 2

using namespace std;

int solve(int limit, const vector<int> &book){
  int ret;
  int pre_w = -1;
  int l = 0;
  int r = 4000000;

  ret = r;
  while(true){
    int st = -1;
    int w = (r+l)/2;
    int maxsw = 0;
    int sw = 0;
    int stair = 0;

    if( w == pre_w )break;

    for(int i = 0; i < book.size(); ++i){
      maxsw = max( maxsw, sw );
      if( sw + book[i] <= w ){
	sw += book[i];
      }else if( stair < limit ){
	sw = book[i];
	stair++;
      }else{
	st = UP_LIMIT;
      }
    }
    maxsw = max( maxsw, sw );

    //cout << "R,L : " << r << ' ' << l << "STAIR : " << stair << " MAXSW : " << maxsw << endl;

    if( st == UP_LIMIT || stair >= limit ){
      l = w;
    }else if( st == -1 ){
      ret = min( ret, maxsw );
      r = w;
    }
    
    pre_w = w;
  }
  return ret;
}

int main(){
  while(true){
    int m,n;
    vector<int> books;

    cin >> m >> n;
    if(m==0&&n==0)break;
    for(int i = 0; i < n; ++i){
      int t;
      cin >> t;
      books.push_back(t);
    }

    cout << solve( m, books ) << endl;

  }
  return 0;
}

C++: #include<iostream>
using namespace std;
int t[100];
int m,n,L,R,M;


bool check(int x){
  int cnt=0,cnt2=0,sum=0;
  
  while(cnt<n&&cnt2<m){
    if(sum+t[cnt]>x){
      sum=0;
      cnt2++;
    }else{
      sum+=t[cnt];
      cnt++;
    }
  }
  
  if(cnt==n)return true;
  else return false;
}

int main(){
  while(cin>>m>>n){
    if(m==0&&n==0)break;
    R=0;
    for(int i=0;i<n;i++){
      cin>>t[i];
      R+=t[i];
    }

    L=0;
    M=(L+R)/2;

    while(1){
      if(check(M)==true&&check(M-1)==false){
	break;
      }else if(check(M)){
	R=M;
	M=(L+R)/2;
      }else{
	L=M+1;
	M=(L+R)/2;
      }
    }
    cout<<M<<endl;
  }
  return 0;
}

C++: #include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,a[101],y;
bool nibun(int x){
	int s=0,q=0,t=0;
	r(i,n){
		if(s+a[i]<=x)s+=a[i];
		else s=0,q++,i--,t++;
		if(t>1000)return 0;
	}
	return m>=q+1;
}
main(){
	while(cin>>m>>n,m){
	  y=1e9;
	  r(i,n)cin>>a[i],y=min(y,a[i]);
	  int l=y,r=1500001;
	  while(l<r){
    	int mid=(l+r)/2;
		if(nibun(mid))r=mid;
		else l=mid+1;
	  }
	  cout<<l<<endl;
    }
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<climits>
using namespace std;



int n,m;
vector<int> cost;
void init(){
  cost.clear();
}

bool input(){
  cin>>m>>n;
  if(n==0&&m==0)return 0;
  for(int i=0;i<n;i++){
    int tmp;
    cin>>tmp;
    cost.push_back(tmp);
  }
  return 1;
}

int rec(int i,int x){
  int res=INT_MAX-1500010;
  if(i==n){
    return 0;
  }
  if(x==m){
    return res;
  }
  int c=cost[i];
  for(int j=i+1;j<cost.size()+1;j++){
    res=min(res,max(rec(j,x+1),c));
    c+=cost[j];
  }
  return res;
}


int solve(){
  int res=INT_MAX-1500010;
  res=min(res,rec(0,0));
  return res;
}


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