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: 
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):
                return False
            if(w >= b):
                w -= b
            else:
                if(i >= self.M):
                    return False
                else:
                    i += 1
                    w = W - b
        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:
    print(Solve().solve())

Python: while(True):
    # n:#ofShelf, m:#ofBook
    n, m = map(int, input().split(' '))
    if n == 0:
        break
    widths = [int(input()) for i in range(m)]
    minwid = max(widths)
    maxwid = sum(widths)

    def packable():
        bookQ = widths.copy()
        nShelf = 1
        sumBook = 0
        while len(bookQ) != 0 and nShelf <= n:
            if sumBook + bookQ[0] <= guess:
                sumBook += bookQ.pop(0)
            else:
                nShelf += 1
                sumBook = bookQ.pop(0)
        return len(bookQ) == 0 and nShelf <= n

    # Try packing
    while minwid != maxwid:
        guess = (maxwid+minwid)//2
        if packable():
            maxwid = guess
        else:
            minwid = guess + 1
    print(minwid)

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 =[0]
    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+1:
                return True
            assert _index > 0
            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()

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 = 0
    min_width = float('inf')

    for i in range(100):
        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 1:
    M, N = map(int, input().split())
    if M == N == 0:
        break
    W = [int(input()) for i in range(N)]
    left = max(W)-1; right = sum(W)
    while left+1 < right:
        mid = (left + right) >> 1
        k = 1; cur = 0
        for w in W:
            if mid < cur+w:
                cur = w
                k += 1
            else:
                cur += w
        if k <= M:
            right = mid
        else:
            left = mid
    print(right)

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):
    rem = mid
    i = 0
    while True:
        while rem >= books[i]:
            rem -= books[i]
            i += 1
            if i == n:
                break
        rem = mid
        m -= 1
        if i == n:
            break

    if m < 0:
        return False
    else:
        return True


def solve(m, n, books):
    ub = 1500000
    lb = max(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: def func(q,m,W):
    s = 0
    c = 1
    for w in W:
        s += w
        if s > q:
            c += 1
            s = w
            if s > q:
                return 1
    return (c > m)

while(1):
    m,n=[int(x) for x in input().split()]
    if m==0:
        break
    W=[]
    A=[0]
    for i in range(n):
        W.append(int(input()))
        A.append(A[-1]+W[-1])
    A.pop(0)
    qsmall = sum(W)/m
    qbig   = 1500000
    while(1):
        if qbig - qsmall < 1e-3:
            break
        q = (qbig+qsmall)/2 
        issmall = func(q,m,W)
        if issmall:
            qsmall = q
        else:
            qbig = q
    q = int(qsmall)
    if func(q,m,W):
        print(q + 1)
    else:
        print(q)