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 <vector>
#include <algorithm>

using namespace std;

vector<int> books;
int m,n;

bool check(int r){
	int rank=0;
	int place=0;
	for(int i = 0; i < books.size(); i++){
		if(books[i]>r)
			return false;
		// àµTCYª éå«³æè¬³¯êÎ
		if(place+books[i]<=r){
			place+=books[i];
		}
		else{
			rank++;
			if(rank>=m)
				return false;
			place=0;
			place+=books[i];
		}
	}
	return true;
}

int main(){

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

		int ub=1500000;
		int lb=-1;
		while(ub-lb>1){
			int med=ub+lb;
			med/=2;
			// ¨¯éÈç
			if(check(med)){
				ub=med;
			}
			else{
				lb=med;
			}
		}
		cout<<ub<<endl;
		books.clear();
	}
	
	return 0;
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int a,b,ans;
  while(cin>>a>>b){
    if(a==0&&b==0) break;
    int book[b],hei=0;
    for(int i=0;i<b;i++) cin >> book[i];
    if(a>=b){
      sort(book,book+b,greater<int>());
      cout << book[0] << endl;
    }
    else{
      for(int i=0;i<b;i++) hei += book[i];
      hei /= a;
      //cout << hei << endl;
      for(int i=hei;i<=1500000;i++){
	int h[a],count=0;
	for(int j=0;j<a;j++) h[j] = 0;
	for(int j=0;j<b;j++){
	  if(h[count]+book[j]>i){
	    count++;
	    if(count>=a) break;
	    h[count] += book[j]; 
	  }
	  else if(j==b-1){
	    ans = i;
	    goto END;
	  }
	  else h[count] += book[j];
	}
      }
    END:
      cout << ans << endl;
    }
  }
  return 0;
}

C++: #include <cstdio>
using namespace std;
int bookin(int* books,int m,int w,int n);

int main(void)
{
  int n,m;
  for(;;){
    scanf("%d %d",&m,&n);
    if(n==0)return 0;
    int books[n];
    for(int i=0;i<n;i++){
      scanf("%d",&books[i]);
    }

    int low = 1,high=1500000;
    for(int i=0;i<100;i++){
      int mid = (low+high)/2;
      int midval = bookin(books,m,mid,n);

      if(midval==0)low = mid;
      else high = mid;
    }
    printf("%d\n",high); 
  }
}

int bookin(int* books,int m,int w,int n)
{
  int haba=w;
  for(int i=0;i<n;i++){
    haba-=books[i];
    if(haba<0){i--;m--;haba=w;}
    if(m<=0)return 0;
  }
  return 1;
}

C++: #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#define MAX_M 1500000
#define MIN_M 0
using namespace std;
int book[101];
int main(void)
{
	ios::sync_with_stdio(false);
	int i,j,k;
	int m,n;
	int low,high,mid,ff;
	int tanasuu,sum,mx;
	while(1) {
		cin>>m>>n;
		if(m==0&&n==0) break;
		low=MIN_M;
		high=MAX_M;
		mx=MIN_M;
		ff=0;
		for(i=0;i<n;i++) cin>>book[i];
		while(low<=high) {
			mid=(low+high)/2;
			sum=MIN_M;tanasuu=1;
			for(j=0;j<n;j++) {
				/*if(mid==sum+book[j]) tanasuu++;
				else if(mid>sum+book[j])sum+=book[j];
				else if(mid>book[j]){
					tanasuu++;
					sum=book[j];
				}	
				if(tanasuu<m && mid==sum+book[j]) {
					tanasuu++;
					sum=0;
				}
				else if(mid>sum+book[j]) {
					tanasuu++;
					if(mid>=book[j]) {
						sum=book[j];
					}
					else break;					
				}*/
				if(m<n) {
					if(tanasuu<=m) {
						if(mid==sum+book[j]) {
							tanasuu++;
							sum+=book[j];
						}
						else if(mid>sum+book[j]) {
							sum+=book[j];
						}
						else {
							if(mid>=book[j]) {
								sum=book[j];
								tanasuu++;
							}
						}
					}
					else break;
				}
				else {
					ff=1;
					if(mx<book[j]) mx=book[j];
				}
			}
			if(ff==0) {
				if(tanasuu>m){
					low=mid+1;
				}
				else high=mid-1;
			}
			else break;
		}
		if(ff==0) 
			cout<<high<<endl;
		else cout<<mx<<endl;
	}	
	return 0;
}

C++: #include<iostream>

using namespace std;

int m, n;
hon[100];

int f(int w) {
	int honIdx = 0;
	for (int i = 0; i < m; i++) {
		int curW = w;
		while (hon[honIdx] <= curW) {
			curW -= hon[honIdx];
			honIdx++;
			if (honIdx == n) return 1;
		}
	}
	return 0;
}

int binsearch_lower_bound() {
  int low = 0; // 範囲の下限
  int high = 1000000 + 1; // 範囲の上限。解はあれば [low, high] の中に存在する
  while (low < high) {
    int mid = (low + high) / 2;  // 中心点（この実装ではオーバーフローしうるので注意）
    int midval = f(mid);  // 中心での値
    
    // 解の範囲を狭める
    if (midval < 1) low = mid + 1;
    else high = mid;
  }
  return low;
}

int main() {
	while(cin >> m >> n, m || n) {
		for (int i = 0; i < n; i++) {
			cin >> hon[i];
		}
		cout << binsearch_lower_bound() << endl;
	}
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int m, n;
int w[110];

bool check(int mid) {
  int sum = 0, res = 1;
  for (int i = 0; i < n; i++) {
    if (w[i] > mid) return false;
    if (sum + w[i] > mid) sum = w[i], res++;
    else sum += w[i];
  }
  return res <= m;
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  while (cin >> m >> n, m) {
    for (int i = 0; i < n; i++) {
      cin >> w[i];
    }
    int ng = 0, ok = 1500000;
    while (ok - ng > 1) {
      int mid = (ng + ok) / 2;
      if (check(mid)) ok = mid;
      else ng = mid;
    }
    cout << ok << endl;
  }

  return 0;
}

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

int m,n;
int b[100];
int check(int w){
	int cnt=1;
	int tmp=0;
	for(int i=0;i<n;i++){
		if(b[i]>w)return 0;
		if(tmp+b[i]<=w)tmp+=b[i];
		else{
			tmp=b[i];
			cnt++;
		}
	}
	if(m>=cnt)return 1;
	return 0;
}

int main(){
	while(cin>>m>>n,m){
		for(int i=0;i<n;i++){
			cin>>b[i];
		}
		
		int safe=1500000,out=1;
		while(safe-out>1){
			if(check((out+safe)/2)){
				safe=(out+safe)/2;
			}
			else{
				out=(out+safe)/2;
			}
		}
		cout<<safe<<endl;
	}
	
	
	return 0;
}

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

int main() {
	int a, b;
	while (cin >>a>>b,a|b) {
		int ruisekiwa[101]; ruisekiwa[0] = 0;
		for (int d = 1; d <= b; d++) {
			int e; scanf("%d", &e);
			ruisekiwa[d] = ruisekiwa[d - 1] + e;
		}
		int dp[21][101];//n???????????§??§m?????????????°????
		for (int i = 0; i < 21; i++)fill(dp[i], dp[i] + 101, 1 << 29);
		dp[0][0] = 0;
		for (int i = 1; i <=a; i++) {
			for (int j = 1; j <= b; j++) {
				for (int k = j; k >= 0;k--) {
					dp[i][j] = min(dp[i][j], max(dp[i-1][j-k],ruisekiwa[j]-ruisekiwa[j-k]));
				}
			}
		}
		cout << dp[a][b] << endl;
	}
}