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,b) range(i,0,b)
#define range(i,a,b) for(int i = (a); i < (int)(b); i++)

int m,n;
vector<int> a;

bool ok(int x){
    int k = 0;
    rep(i,m){
        int t = 0;
        while(k != n){
            if(t + a[k] > x) break;
            t += a[k];
            k++;
        }
    }
    return k == n;
}

int main(){
    while(cin >> m >> n && m){
        a.resize(n);
        rep(i,n) cin >> a[i];
        int l = 0, r = 1e8;
        while(l+1 < r){
            int m = (l+r)/2;
            if(ok(m)) r = m; else l = m;
        }
        cout << r << 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>
using namespace std;
int m, n;
int a[1000];
bool check(int v) {
	int cnt = 0, s = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] > v)return false;
	}
	for (int i = 0; i < n; i++) {
		if (s + a[i] > v) {
			cnt++;
			s = a[i];
		}
		else {
			s += a[i];
		}
	}
	if (cnt > m)return false;
	return true;
}
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 = 0, R = 100000000, M;
		for (int i = 0; i < 50; i++) {
			M = (L + R) / 2;
			bool r1 = check(M - 1);
			bool r2 = check(M);
			if (r1 == true)R = M;
			if (r2 == false) { L = M; }
		}
		cout << M << endl;
	}
	return 0;
}

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

typedef long long ll;

int main(void){
    ll m, n;
    ll w[110];
    
    while(cin >> m >> n){
        if(m+n==0) break;
        for(int i=1; i<=n; i++){
            cin >> w[i];
        }
        ll under=0, upper=1500000;
        while(upper-under>1LL){
            ll mid=(under+upper)/2;
            ll sum=0, count=1;
            for(int i=1; i<=n; i++){
                sum+=w[i];
                if(sum>mid){
                    count++;
                    sum=w[i];
                }
            }
            if(count>m || sum>mid){
                under=mid;
            }
            else{
                upper=mid;
            }
        }
    
        cout << upper << "\n";
    }
    
    return 0;
}

C++: #include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

const int INF=1e9;

signed main(){
   	int n,m;
   	while(1){
	   	cin>>n>>m;
	   	if(n+m==0) break;
	   	vi d(m);
	   	rep(i,0,m){
	   		cin>>d[i];
	   	}
	   	int MIN=INF;
		rep(i,1,m+1){
			int sum=0,cnt=1,tmp=INF;
			rep(j,0,i){
				sum+=d[j];
			}
			rep(j,i,m){
				if(tmp+d[j]<=sum){
					tmp+=d[j];
				}else{
					tmp=d[j];
					cnt++;
				}
			}
			//cout << i << " " << sum << " " << cnt << endl;
			if(cnt<=n){
				MIN=min(MIN,sum);
			}
		}	   
	    cout<<MIN<<endl;
	}
}

C++: #include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define INF 1e8
#define EPS 1e-9

#define rep2(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) rep2(i,0,n)
#define ll long long
#define P pair<int,int>
#define pb push_back

int m,n,b[100];

int main(){
	while(cin>>m>>n&&m){
		rep(i,n)cin>>b[i];
		int l=0,u=15000000;
		while(l<u-1){
			int M=(l+u)/2,x=0,y=0,cur=0;
			for(;;){
				if(x+b[cur]<=M)x+=b[cur++];
				else{y++;x=0;}
				if(cur==n||y==m)break;
			}
			if(cur==n)u=M;
			else l=M;
		}
		cout<<u<<endl;
	}
}

C++: #include <iostream>

using namespace std;

typedef unsigned long long ull;

int m, n;
double avg;
ull books[100];

bool judge(int i, ull width)
{
	ull w = 0;
	int h = 2;
	for(int k=i+1; k<n; k++)
	{
		w += books[k];
		if(w > width)
		{
			w = books[k];
			h++;
		}

		if(h > m) return false;
	}

	return true;
}

ull solve()
{
	ull width = 0;
	for(int i=0; i<n; i++)
	{
		width += books[i];
		if(width > 0)
		{
			if(judge(i, width)) return width;
		}
	}

	return -1;
}

int main()
{
	while( 1 )
	{
		cin >> m >> n;
		if(m==0 && n==0) break;
		
		avg = 0.0;
		for(int i=0; i<n; i++)
		{
			scanf("%llu", &books[i]);
			avg += books[i];
		}
		avg /= (float)n;

		ull ans = solve();
		printf("%llu\n", ans);
	}
}

C++: #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int m,n,w[101],ma,sum,cnt,dan,ans;
  while(scanf("%d %d",&m,&n),m!=0||n!=0){
    ma = 0;
    ans = 0;
    for(int i=0;i<n;i++){
      scanf("%d",&w[i]);
      ma = max(ma,w[i]);
      ans += w[i];
    }
    sum = 0;
    for(int i=0;i<n-1;i++){
      cnt = 0;
      dan = 2;
      sum += w[i];
      if(ma > sum) continue;
      for(int j=i+1;j<n;j++){
	if(cnt+w[i] > sum){
	  cnt = 0;
	  dan++;
	}
	cnt += w[i];
      }
      if(dan <= m) ans = min(ans,sum);
    }
    printf("%d\n",ans);
  }
  return(0);
}