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: def hondan(w,m):
    m_sum = b_lis[0]
    num = 0
    if w < max(b_lis):
        return False
    else:
        for i in range(len(b_lis) - 1):
            m_sum += b_lis[i + 1]
            if m_sum > w:

                m_sum = b_lis[i + 1]
                num += 1

        if num < m:
            return True
        else:
            return False
        
def nibutan(f_id,e_id,m):
    
    
    m_id = int((f_id + e_id) / 2)
    m_bo = hondan(m_id,m)


    if (f_id > e_id):
        return m_id + 1
    else:
        if m_bo:
            return(nibutan(f_id,m_id -1,m))
        elif not m_bo:
            return(nibutan(m_id + 1,e_id,m))
        else:
            return m_id + 1



while True:
    global w_lis
    b_lis = []
    w_lis = []
    dan_num = [0]

    m,n = map(int,input().split())
    if m == n == 0:
        break
    for i in range(n):
        num = int(input())
        b_lis.append(num)
    s_num = int(sum(b_lis) /m)

    print(nibutan(s_num,1500000,m) )

Python: import sys
_allinput = []
for inp in sys.stdin:
	_allinput += inp.strip().split(" ")
def _input():
	for put in _allinput:
		yield put
_obj = _input();
def __input():
	return _obj.__next__()
def nextInt():
	return int(__input())
def check(lst,L):
	tot = 1
	curSum = 0
	for i in lst:
		if curSum + i <= L:
			curSum += i
		else:
			curSum = i
			tot += 1
	return tot

def solve(lst,m):
	l = max(lst)
	r = 1000000 * m;
	while l != r:
		mid = int((l+r)/2);
		if check(lst,mid) <= m: r = mid
		else: l = mid + 1
	return l
try:
	while True:
		m,n = nextInt(),nextInt()
		if m > 0 or n > 0:
			lst = [nextInt() for i in range(0,n)]
			print(solve(lst,m))
		else:
			break
except:
	'''
	'''

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(50):
        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: # -*- 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 False
        
    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 IsStorable( m, n, w, width ):
    row = 1
    c = 0
    i = 0
    while i < n :
        if c + w[i] <= width :
            c += w[i]
            i += 1
        elif row < m :
            c = 0
            row += 1
        else : return False
    return True

while ( True ):
    m,n = map(int, input().split())
    if m == 0 and n == 0 : break
    w = []
    for i in range(n) : w.append(int(input()))

    minw = 1
    maxw = 1500000
    if not IsStorable( m, n, w, maxw ) : print("NA")
    
    while maxw > minw :
        mid = int((maxw + minw)/2)
        if IsStorable( m, n, w, mid ) : maxw = mid
        else : minw = mid + 1
    print(minw)

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 = []
    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
    bid = 0
    n_si = 0
    for i in range(m):
        bid = nibutan(bid,n - 1,n_si + best_num,i)
        si = w_lis[bid]
        dan_num.append(si)
    print(max(dan_num))

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:
    print(Solve().solve())