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++: #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <utility>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define each(e,c) for(auto&e:c)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<(DUMP(),__VA_ARGS__).str()<<" ["<<__LINE__<<"]"<<endl)
struct DUMP:ostringstream{template<class T>DUMP &operator,(const T&t){if(this->tellp())*this<<", ";*this<<t;return *this;}};
#else
#define dump(...)
#endif
template<class T> ostream& operator<<(ostream& os, vector<T> const& v){
    rep(i,v.size()) os << v[i] << (i+1==v.size()?"":" ");
    return os;
}

int a[111];
int main(){
    int m,n;
    while(cin >> m >> n && m){
        rep(i,n) cin >> a[i];
        a[n] = 0;
        ll r = 100000000+1;
        ll l = 0;
        while(l+1<r){
            ll w = (l+r)/2;
            ll h = 1, t = 0;
            rep(i,n){
                if(t+a[i]>w) h++, t=0;
                t+=a[i];
            }
            if(t > w) h++;
            (h <= m ? r : l) = w;
        }
        cout << r << endl;
    }
}

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

int main( void )
{
	const int INF = ( 1 << 21 );

	int m, n;
	while ( cin >> m >> n && m > 0 && n > 0 )
	{
		vector <int> S(n+1,0);
		for ( int i = 1; i <= n; i++ )
			cin >> S[i];

		vector <int> P(n+1,0);
		for ( int i = 1; i <= n; i++ )
			P[i] = P[i-1] + S[i];

		vector < vector <int> > M( n+1, vector <int>( m+1, 0 ) );

		for ( int i = 1; i <= n; i++ )
			M[i][1] = P[i];

		for ( int i = 1; i <= m; i++ )
			M[1][i] = S[1];

		for ( int i = 2; i <= n; i++ )
		{
			for ( int j = 2; j <= m; j++ )
			{
				M[i][j] = INF;
				for ( int x = 1; x <= i - 1; x++ )
				{
					int maxv = max( M[x][j-1], P[i]-P[x] );
					if ( M[i][j] > maxv )
						M[i][j] = maxv;
				}
			}
		}

		cout << M[n][m] << endl;

	}

	return 0;
}

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

#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using pii = pair<int, int>; using vi = vector<int>;
static const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
static const int MOD = (int)(1e9 + 7);

int m, n;
//??¬?£?????????????????????????
bool f(vector<int> &w, int a) {
	int cnt = 1;
	int tmp = 0;
	for (int i = 0; i < w.size(); i++) {
		if (w[i] > a)return false;
		if (tmp + w[i] > a) {
			cnt += 1;
			tmp = 0;
		}
		tmp += w[i];
	}
	if (cnt > m)return false;
	return true;
}

signed main() {
	for (; cin >> m >> n&&m;) {
		vector<int> w(n);
		rep(i, 0, n)cin >> w[i];

		int L = 0, R = 1500001;
		rep(i, 0, 22) {
			int MID = (L + R) / 2;
			if (f(w, MID))R = MID;
			else L = MID;
		}
		cout << R << endl;
	}
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
int main(){
	int n,m;
	while(cin>>n>>m,n||m){
		vi in(m);
		rep(i,m)cin>>in[i];
		int r=1,l=15000001;
		while(l-r>1){
			int h=(r+l)/2;
			int c=1;
			int sum=0;
			rep(i,m){
				if(sum==0&&in[i]>h){
					c=1e9;
					break;
				}else if(sum+in[i]>h){
					c++;sum=0;
					i--;
				}else{
					sum+=in[i];
				}
			}
			if(c<=n)l=h;
			else r=h;
		}
		cout<<l<<endl;
	}
}

C++: 
#include <iostream>

using namespace std;

typedef unsigned long long ull;
int n, m;
ull books[100];

bool solve(int width)
{
	ull w = 0;
	int h = 1;

	for(int i=0; i<n; i++)
	{
		if(w > width) return false;
		if(w + books[i] > width)
		{
			h++;
			w = 0;
		}
		w += books[i];
	}

	return h <= m;
}

int main()
{
	while( 1 )
	{
		scanf("%d", &m);
		scanf("%d", &n);
		if(m==0 && n==0) break;

		for(int i=0; i<n; i++)
		{
			scanf("%llu", &books[i]);
		}

		ull upper = 1500000;
		ull lower = 1;
		
		while(upper - lower > 1)
		{
			ull mid = (upper + lower) / 2;
			if(solve(mid)) upper = mid;
			else  lower = mid;
		}

		printf("%llu\n", solve(lower) ? lower : upper);
	}
}

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>110)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;
    }
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
  int m,n;
  for(;cin>>m>>n,m;)
    {
      vector<long long int> book;
      long long int ans=0;
      for(int i=0;i<n;i++)
	{
	  long long int tmp;
	  cin>>tmp;
	  ans=max(ans,tmp);
	  book.push_back(tmp);
	}
      while(m<book.size())
	{
	  long long int tmp_min=100000001;
	  int tmp_cnt=0;
	  for(int i=0;i<book.size()-1;i++)
	    {
	      if(tmp_min>book[i]+book[i+1])
		{
		  tmp_min=book[i]+book[i+1];
		  tmp_cnt=i;
		}
	    }
	  //	  cout<<"tmp_cnt "<<tmp_cnt<<" "<<book[tmp_cnt]+book[tmp_cnt+1]<<endl;
	  book[tmp_cnt]+=book[tmp_cnt+1];
	  book.erase(book.begin()+tmp_cnt+1);
	  ans=max(ans,book[tmp_cnt]);
	}
      cout<<ans<<endl;

    }
}