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 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 (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];
		if (n <= m) {
			cout << *max_element(all(w)) << endl;
			return 0;
		}

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

C++: #include<cstdio>
#include<algorithm>

using namespace std;

int n,m;
int hon[101];
int nibun(){
	int R,L;R=L=0;
	for(int i=0;i<m;i++){
		L+=hon[i];
	}
	while(1){
		if(R==L){
			return R;
		}
		double H=(double)(R+L)/2;
		
		int dan=0;
		int at=0;
		for(int i=0;i<m;i++){
			if(hon[i]>H){
				dan=10000;
				break;
			}
			if(at+hon[i] <= H){
				at+=hon[i];
			}else{
				at=0;
				dan++;
				at+=hon[i];
			}
		}
		
		if(dan<n){
			L=H;
		}else{
			R=H+0.5;
		}
		
	}
}
int main(){
	int cont=0;
	while(1){
		scanf("%d%d",&n,&m);
		for(int i=0;i<m;i++){
			scanf("%d",&hon[i]);
		}
		printf("%d\n",nibun());
	}
}

C++: #include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main(void)
{
	int M,N;

	while(cin >> M >> N){
		priority_queue<long, vector<long>, greater<long> > pq;

		for(int i = 0; i < M; i++)
			pq.push(0);		//本棚初期

		long book;
		while(N > 0){
			cin >> book;

			int pqt = pq.top();	pq.pop();

			pqt += book;
			pq.push(pqt);
			N--;
		}
		while(pq.size()-1 > 0)
			pq.pop();

		cout << pq.top() << endl;
		pq.pop();
	}

	return 0;
}

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

#define loop(i)    for(int lp=0; lp<(i); lp ++)
#define ascent(i,a,b) for(int i=(a); i<(b); i ++)

#define pb push_back

using namespace std;

int m, n;

int max(vector<int> vec) {
	int max = 0;
	ascent(i, 0, n) {
		if(max < vec[i]) max = vec[i];
	}
	
	return max;
}

int main() {
	vector<int> a;
	
	while(cin >> m >> n, m||n) {		
		a.clear();
		int tmp;
		loop(n) {
			cin >> tmp;
			a.pb(tmp);
		}
		
		int l=0, r=0;
		ascent(i,0,n) {
			r+= a[i];
		}
		int ans = r;
		int mid;
		while(r-l>1) {
			mid = (l+r)/2;
			
			if(mid < max(a)) {
				l = mid;
			}
			else {
				int count = m-1;
				int a_sum = 0;
				vector<int> tmpvec;
				for(int i=0; i<n; i++) {
					if(a_sum + a[i] > mid) {
						tmpvec.pb(a_sum);
						a_sum = a[i];
						count --;
					}
					else {
						a_sum += a[i];
					}
				}
//				tmpvec.pb(a_sum);
//				cout << mid << " " << count << endl;
//				ascent(i, 0, tmpvec.size()) {
//					cout << " " << tmpvec[i];
//				}
//				cout << endl;
				
				if(count >= 0) {
					ans = mid;
				}
				
				if(count == m || count < 0) l=mid;
				else r=mid;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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


int main() {
  int M, N;
  int W[101];
  while(cin >> M >> N && (M|N)) {
    for(int i = 0; i < N; ++i) cin >> W[i];
    int l = W[0];
    for(int i = 1; i < N; ++i) l = max(l,W[i]);
    int r = 1500000;
    int ans = r;
    while(l < r) {
      int m = (l+r)/2;
      int h = 1;
      for(int i = 0, space = 0; i < N; ++i) {
	if(space+W[i] > m) {
	  ++h;
	  space = W[i];
	} else {
	  space += W[i];
	}
      }
      if(h <= M) {
	ans = m;
	r = m;
      } else {
	l = m+1;
      }
    }
    cout << ans << endl;
  }
  return 0;
}

C++: //suhan lee, saitama university;
#include <iostream>
using namespace std;
int putbook(int *list,int bookwi,int stair,int width){

  int dara[20];
  int j=0;
  for(int i=0;i<20;i++)
    dara[i]=0;
  for(int i=0;i<bookwi;i++)
    if(dara[j]+list[i]<=width)
      dara[j]+=list[i];
    else  if(list[i]>width){
      //cout <<"too big book"<<endl;
      return 0;
    }
    else  dara[++j]+=list[i];     
  //  cout <<"hondara";
  for(int i=0;i<stair;i++)
    // cout <<dara[i]<<endl;
    // cout <<"kugiri";
  if(j<stair) return 1;// no problem
  else return 0;
}


int main(){

  int list[100];

  int bookwi,stair,temp;
  int max,min;
  while(1){
    cin >>stair>>bookwi;
    if(bookwi==0&&stair==0)
      return 0;
    for(int i=0;i<bookwi;i++)
      cin>>list[i];
    max=1000000;
    min=1;
    //cout << putbook( list,bookwi,stair,1800 )<<endl;
    while(1){
      if(min==max) break;
      if(putbook( list,bookwi,stair, ( max+min)/2  ) )
	max=(max+min)/2;
      else min= (max+min)/2+1;
      //   cout <<endl<<max<<" max&min   "<<min<<endl;   
    }
    cout <<max<<endl;
  }

}

C++: #include<iostream>
using namespace std;
int t[100];
int m,n,L,R,M;


bool check(int x){
  int cnt=0,cnt2=0,sum=0;
  
  while(cnt<n&&cnt2<m){
    if(sum+t[cnt]>x){
      sum=0;
      cnt2++;
    }else{
      sum+=t[cnt];
      cnt++;
    }
  }
  
  if(cnt==n)return true;
  else return false;
}

int main(){
  while(cin>>m>>n){
    if(m==0&&n==0)break;
    R=0;
    for(int i=0;i<n;i++){
      cin>>t[i];
      R+=t[i];
    }

    L=0;
    M=(L+R)/2;

    while(L<R){
      if(check(M)){
	R=M-1;
	M=(L+R)/2;
      }else{
	L=M+1;
	M=(L+R)/2;
      }
    }
    cout<<L+1<<endl;
  }
  return 0;
}

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

int main()
{
	int m, n;
	while( cin >> m >> n && ( m || n ) ){
		int book[ 100 ] = {0};
		int acum = 0;
		int sum[ 100 ] = {0};
		for( int i = 0; i < n; ++i ){
			int t;
			cin >> t;
			book[ i ] = t;
			acum += t;
			sum[ i ] = acum;
		}
		int ans = 0x7fffffff;
		for( int i = 0; i < n; ++ i ){
			int shelf[ 20 ] = {0};
			int ib = i + 1;
			int is = 1;
			while( ib < n && is < m ){
				int w = shelf[ is ] + book[ ib ];
				if( w <= sum[ i ] ){
					++ib;
					shelf[ is ] = w;
				}else{
					++is;
				}
			}
			if( ib == n && ans > sum[ i ] ){
				ans = sum[ i ];
			}
		}
		cout << ans << endl;
	}

	return 0;
}