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

Python: # -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181

"""
import sys
from sys import stdin
input = stdin.readline


def Cond(m, n, mid, books):
    if max(books) > mid:
        return False

    rem = mid
    while books:
        while rem >= books[0]:
            rem -= books[0]
            books = books[1:]
            if len(books) == 0:
                break
        rem = mid
        m -= 1

    if m >= 0:
        return True
    else:
        return False


def solve(m, n, books):
    ub = 1500000
    lb = min(books)
    min_width = float('inf')

    for i in range(30):
        mid = (ub + lb) // 2
        if Cond(m, n, mid, books):
            min_width = min(min_width, mid)
            ub = mid
        else:
            lb = mid

    return min_width



def main(args):
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            break
        books = [int(input()) for _ in range(n)]
        result = solve(m, n, books)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Python: while True:
    m, n = map(int, input().split())
    if n+m == 0:
        break
    else:
        book_list = [int(input()) for _ in range(n)]
        left = min(book_list)
        right = 10**7
        while left < right:
            w = (left+right)//2
            cnt_m = 1
            tmp_w = 0
            for book in book_list:
                if book > w:
                    cnt_m = m + 1
                else:
                    tmp_w += book
                    if tmp_w > w:
                        tmp_w = book
                        cnt_m += 1
            if cnt_m > m:
                left = w + 1
            else:
                right = w
        print(left)

Python: 
class Solve:
    def __init__(self):
        self.M, self.N = map(int, input().split())
        self.bs = [int(input()) for i in range(self.N)]

        self.S = min(sum(self.bs), 1500000)
        self.l, self.r = 0, self.S        

    def check(self, W):
        w = W
        i = 1
        for b in self.bs:
            if(w >= b):
                w -= b
            elif(W >= b):
                if(i >= self.M):
                    return False
                i += 1
                w = W - b
            else:
                return False
        return True

    def solve(self):
        while self.r - self.l > 1:
            m = (self.l + self.r) // 2
            if self.check(m):
                self.r = m
            else:
                self.l = m
        return self.r

while True:
    s = Solve()
    if s.M == 0 and s.N == 0:
        break
    print(s.solve())

Python: def nibutan(f_id,e_id,f_num,yn):
    
    
    m_id = int((f_id + e_id) / 2)
    m_num = w_lis[m_id]


    if e_id - f_id <= 1:
        if yn == 0:

            return e_id
        else:
            return f_id
    else:
        if m_num > f_num:
            return(nibutan(f_id,m_id -1,f_num,yn))
        elif m_num < f_num:
            return(nibutan(m_id + 1,e_id,f_num,yn))
        else:
            return  m_num




while True:
    global w_lis
    b_lis = []
    w_lis = []
    dan_num = [0]
    atu_num = [0]
    wa = 0
    m,n = map(int,input().split())
    if m == n == 0:
        break
    for i in range(n):
        num = int(input())
        wa += num
        b_lis.append(num)
        w_lis.append(wa)
    best_num = wa / m
    if best_num < max(b_lis):
        print(max(b_lis))
    else:
        bid = 0
        n_si = 0
        for i in range(m):
            bid = nibutan(bid,n - 1,n_si + best_num,i)
            n_si = w_lis[bid]
            dan_num.append(n_si)
            atu_num.append(n_si - dan_num[i])
            
        print(max(atu_num))

Python: def search(width, books, m):
  acc = 0
  cnt = 1
  for book in books:
    if book > width:
      return False
    if acc + book > width:
      cnt += 1
      acc = book
    else:
      acc += book
  return cnt <= m
while True:
  m, n = map(int, input().split())
  if m == 0:
    break
  books = [int(input()) for _ in range(n)]
  left = 0
  right = 1500000
  while right - left > 1:
    mid = (left + right) // 2
    #print(mid)
    if search(mid, books, m):
      right = mid
    else:
      left = mid
  print(right)

Python: import bisect
def main():
    m,n  = list(map(int,input().split()))
    if n==0:
        exit()
    W = [int(input()) for _ in range(n)]

    w_total = 0
    w_sum =[]
    for w in W:
        w_total+=w
        w_sum.append(w_total)

    def judge(shelf_length):
        last_val = 0
        for i in range(m):
            _index= bisect.bisect_right(w_sum,last_val+shelf_length)
            #print(_index)
            if _index == n:
                return True
            if _index == 0:
                return False
            last_val =w_sum[ _index-1]
        return False


    def nibun(func ,min_ ,max_ ):
        left = min_
        right= max_
        while not(left==right):
            mid = (left+right) //2
            tmp = func(mid)
            if tmp:
                right = mid
            else:
                left = mid+1
        return left

    print(nibun(judge,0,1000000))

while True:
    main()

Python: import bisect
def main():
    m,n  = list(map(int,input().split()))
    if n==0:
        exit()
    W = [int(input()) for _ in range(n)]

    w_total = 0
    w_sum =[]
    for w in W:
        w_total+=w
        w_sum.append(w_total)

    def judge(shelf_length):
        last_val = 0
        for i in range(m):
            _index= bisect.bisect_right(w_sum,last_val+shelf_length)
            #print(_index)
            if _index == n:
                return True
            if _index == 0:
                return False
            last_val =w_sum[ _index-1]
        return False


    def nibun(func ,min_ ,max_ ):
        left = min_
        right= max_
        while not(left==right):
            mid = (left+right) //2
            tmp = func(mid)
            if tmp:
                right = mid
            else:
                left = mid+1
        return left

    print(nibun(judge,0,1500009))

while True:
    main()