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 <cstring>

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];
		}
		memset(dp_table    , -1, sizeof(dp_table));

		cout << solve(m,n) << endl;
	}
	
	return 0;
}

C++: #include <cstdio>
#include <vector>
using namespace std;

int main(){
    int m,n;
    for(;;){
        scanf("%d%d",&m,&n);
        if(m==0 && n==0) break;
        vector<int> page(n);
        int mapa=0;
        for(int i=0;i<n;i++){
            scanf("%d",&page[i]);
            mapa=max(mapa,page[i]);
        }
        vector<int> sum(n);
        sum[0]=page[0];
        for(int i=1;i<n;i++){
            sum[i]=page[i]+sum[i-1];
        }
        vector<int> wis;
        int miwi=0;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                int w=sum[j]-sum[i]+page[i];
                if(mapa<=w && w<=1500000){
                    wis.push_back(w);
                    miwi=max(miwi,w);
                }
            }
        }
        for(int i=0;i<wis.size();i++){
            int wi=wis[i];
            int at=1,now=0;
            for(int j=0;j<page.size();j++){
                if(now+page[j]<=wi){
                    now+=page[j];
                }else{
                    at++;
                    now=page[j];
                }
            }
            if(at<=m) miwi=min(miwi,wi);
        }
        printf("%d\n",miwi);
    }
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

ll  n, m, b[1000];

int main(){
	while (cin >> m >> n&&n + m){
		ll MAX = -1;
		REP(i, n){
			cin >> b[i];
			MAX = max(MAX, b[i]);
		}
		if (m >= n){
			cout << MAX << endl;
			continue;
		}
		ll lb = 0, ub = 1500000;
		while (ub - lb > 1){
			int co = 0;
			ll mid = (lb + ub) / 2;
			ll sum = 0;
			REP(i, n){
				sum += b[i];
				if (sum > mid){
					sum = b[i];
					co++;
				}
			}
			if (co < m)ub = mid;
			else lb = mid;
		}
		cout << ub << endl;
	}
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

ll  n, m, b[1000];

int main(){
	while (cin >> m >> n&&n + m){
		ll MAX = -1;
		REP(i, n){
			cin >> b[i];
			MAX = max(MAX, b[i]);
		}
		if (m >= n){
			cout << MAX << endl;
			continue;
		}
		ll lb = 0, ub = 1500000;
		while (ub - lb > 1){
			int co = 1;
			ll mid = (lb + ub) / 2;
			ll sum = 0;
			REP(i, n){
				sum += b[i];
				if (sum > mid){
					sum = b[i];
					co++;
				}
			}
			if (co <= m)ub = mid;
			else lb = mid;
			//cout << ub << " " << lb << endl;
		}
		cout << ub << endl;
	}
}

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

int m,n;

vector<int> item;
int test(int W){
	int w = 0,r=0;
	for(int i = 0 ; i < item.size() ; i++){
		if( w - item[i] < 0 ){
			r++;
			w = W;
		}
		w -= item[i];
	}
	return r <= n;
}
int main(){

	while(cin >> n >> m && n){
		item.clear();
		int l = 0 , r = 1000000;
		for(int i = 0 ; i < m ; i++){
			int a;
			cin >> a;
			l = max(l,a);
			item.push_back(a);
		}
		while(l!=r){
			int M = (l+r) / 2;
			if( test(M) ){
				r = M;
			}else{
				l = M+1;
			}
		}
		cout << r << endl;
	}
}

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

int m, n;
int data[101];

bool func( int num ) {
  int sum = 0, cnt = 1;
  for(int i=0; i<n; i++) {
    if( sum + data[i] <= num ) {
      sum += data[i];
    } else {
      if( data[i] > num ) return false;
      sum = data[i];
      cnt++;
    }
  }

  if( cnt <= m ) return true;
  else return false;
}


int main() 
{
  while( cin >> m >> n, m+n ) {
    for(int i=0; i<n; i++) {
      cin >> data[i];
    }
    
    int l = 0, r = 1500000;
    int now;
    while( l != r ) {
      now = (l + r) / 2;
      if( func( now ) ) {
	r = now;
      } else {
	l = now+1;
      }
    }
    
    cout << l << endl;
  }
  
}

C++: #include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,a[101];
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){
	  r(i,n)cin>>a[i];
	  int l=0,r=1500001;
	  while(l<r){
    	int mid=(l+r)/2;
		if(nibun(mid))r=mid;
		else l=mid+1;
	  }
	  cout<<l<<endl;
    }
}