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<cstdio>
using namespace std;

const int INF = 2000000;
int m,n,a[110];

int check(int b){
  int cnt = 1, rem = b;

  for(int i=0;i<n;i++){
    if(b<a[i])return INF;
    if(rem<a[i]){
      cnt++; rem = b - a[i];
    }else{
      rem -= a[i];
    }
  }
  return cnt;
}

int main(){
  while(scanf("%d%d",&m,&n),m){
    for(int i=0;i<n;i++)scanf("%d",a+i);
    
    int l = 0, r = INF;
    while(r-l>1){
      int mid = (l+r)/2;
      if(check(mid)<=m)r = mid;
      else l = mid;
    }
    printf("%d\n",r);
  }
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int m, n;
	while (cin >> m >> n, m, n) {
		int w[110];
		int f = 0;
		for (int i = 0; i < n; i++) {
			cin >> w[i]; f = max(w[i], f);
		}
		while (1) {
			int p = 1, q = f;
			for (int i = 0; i < n; i++) {
				if (w[i] <= q)q -= w[i];
				else {
					p++;
					q = f - w[i];
				}
			}
			if (p <= m)break;
			f++;
		}
		cout << f << endl;
	}
}

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

const int BOOK_LIMIT = 100;
const int COL_LIMIT = 20;
const int WIDTH_LIMIT = 1500000;

struct Column
{
	int head;
	int w;
};

class Shelf
{
public:
	void input( int numColumn, int numBook )
	{
		width = 0;
		m = numColumn;
		n = numBook;
		int sum = 0;
		int w = 0;
		for( int i = 0; i < n; ++i ){
			int t;
			cin >> t;
			book[ i ] = t;
			sum += t;
			if( sum > WIDTH_LIMIT ){
				sum = WIDTH_LIMIT;
			}
			if( w < t ){
				w = t;
			}
		}
		width = ( sum / m > w ? sum / m : w );
	}

	int putAll()
	{
		int ib = putInit();
		int low = m - 1;
		while( ib < n ){
			if( col[ low ].w + book[ ib ] > width ){
				secureSpace( ib );
			}
			if( col[ low ].w == 0 ){
				col[ low ].head = ib;
			}
			col[ m - 1 ].w += book[ ib++ ];
		}
		return width;
	}

	int putInit()
	{
		int ib = 0;
		int is = 0;
		while( ib < n && is < m ){
			col[ is ].head = ib;
			col[ is ].w = 0;
			while( col[ is ].w + book[ ib ] <= width ){
				col[ is ].w += book[ ib ];
				++ib;
			}
			++is;
		}
		while( is < m ){
			col[ is ].head = -1;
			col[ is ].w = 0;
			++is;
		}
		return ib;
	}

	void secureSpace( int ib )
	{
		int ex = 0x7fffffff;
		int is = 0;
		for( int i = 0; i < m - 1; ++i ){
			int e = book[ col[ i + 1 ].head ] - ( width - col[ i ].w );
			if( e < ex ){
				ex = e;
				is = i + 1;
			}
		}
		width += ex;
		for( int i = is; i < m; ++i ){
			raiseBook( i );
		}
		if( col[ m - 1 ].w + book[ ib ] > width ){
			secureSpace( ib );
		}
	}

	void raiseBook( int is )
	{
		int upper = is - 1;
		int lower = is;
		int bw = book[ col[ lower ].head ];
		if( ( bw + col[ upper ].w ) <= width ){
			if( col[ upper ].w == 0 ){
				col[ upper ].head = col[ lower ].head;
			}
			col[ upper ].w += bw;
			++col[ lower ].head;
			col[ lower ].w -= bw;
			if( col[ lower ].w == 0 ){
				col[ lower ].head = -1;
			}
		}
	}

private:
	int book[ BOOK_LIMIT ];
	Column col[ COL_LIMIT ];
	int m, n;
	int width;
};

int main()
{
	int m, n;
	while( cin >> m >> n && ( m || n ) ){
		Shelf s;
		s.input( m, n );
		cout << s.putAll() << endl;
	}

	return 0;
}

C++: #include <cstdio>
int m, n;
int book[100];
bool C(int k) {
    int sum=0, cnt=1;
    for (int i=0; i<n; i++) {
        sum+=book[i];
        if (book[i]>k) return false;
        if (sum>k) {
            sum=book[i];
            cnt++;
        }
    }
    if (cnt>m) return false;
    return true;
}
int main() {
    while (scanf("%d%d",&m,&n)) {
        if (!m&&!n) break;
        for (int i=0; i<n; i++) scanf("%d",&book[i]);
        int l=1, u=1500001;
        while (u-l>1) {
            int mid=(u+l)/2;
            if (C(mid)) {
                u=mid;
            } else {
                l=mid;
            }
        }
        printf("%d\n",u);
    }
}

C++: #include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

void solve()
{
	int m, n;
	while(cin >> m >> n)
	{
		if(!m && !n)
		{
			break;
		}
		vector<int> Vec(n);
		for(int i = 0; i < n; ++i)
		{
			cin >> Vec[i];
		}
		int pre_width = 0;
		int width = 1500000;
		for(int a = 0; a < 50; ++a)
		{
			int pos = 0;
			for(int i = 0; i < m; ++i)
			{
				int buf = width;
				while(buf > Vec[pos])
				{
					buf -= Vec[pos];
					pos++;
					if(pos == n)
					{
						int pre_width_buf = width;
						width -= abs(width - pre_width) / 2;
						pre_width = pre_width_buf;
						goto NEXT;
					}
				}
			}
			if(pos < n)
			{
				int pre_width_buf = width;
				width += abs(width - pre_width) / 2;
				pre_width = pre_width_buf;
			}
NEXT:
			;
		}
		cout << width << endl;
	}
}

int main()
{
	solve();
	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;
    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<algorithm>
#include<vector>

using namespace std;

int m,n;
vector<int>v;

bool C(int x){

  int cnt=0,sum=0,i=0;
  while(i<n && cnt<m){
    if(sum+v[i]<=x)sum+=v[i],i++;
    else sum=0,cnt++;
  }
  return i==n && m>cnt;
}

int main(void){

  while(cin >> m >> n,m|n){
    v.clear();

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

  return 0;
}

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

using namespace std;

int main(void){
	int m,n;
	
	while(cin >> m >> n){
		if(!(m|n)) break;
		int lb=0,ub=1500000;
		int mini = 1 << 29;
		vector<int> books(n);
		for(int i=0;i<n;i++){
			cin >> books[i];
			mini = min(mini, books[i]);
		}
		while(ub - lb > 1){
			int mid = (lb + ub) / 2;
			int count=1;
			int tmp=0;
			for(int i=0;i<n;i++){
				if(tmp + books[i] <= mid){
					tmp += books[i];
				}else{
					tmp = books[i];
					count++;
				}
			}
			if(count <= m && mid >= mini){
				ub = mid;
			}else{
				lb = mid;
			}
		}
		cout << ub << endl;
	}
}