output_description: For each dataset, print the smallest possible number of the longest contiguous
  spaces between words.
input_description: The input consists of multiple datasets, each in the following format.
  
      _W N_  
      _x_ 1 _x_ 2 ... _x N_  
  
  _W_ , _N_ , and _x i_ are all integers. _W_ is the number of columns (3 ≤ _W_
  ≤ 80,000). _N_ is the number of words (2 ≤ _N_ ≤ 50,000). _x i_ is the number
  of characters in the _i_ -th word (1 ≤ _x i_ ≤ (_W_ −1)/2 ). Note that the
  upper bound on _x i_ assures that there always exists a layout satisfying the
  conditions.
  
  The last dataset is followed by a line containing two zeros.
attempt: while 1:
      W, N = map(int, input().split())
      if W == N == 0:
          break
      (*X,) = map(int, input().split())
  
      def solve(l):
          lower = 0
          upper = 0
          for x in X:
              lower += x + 1
              upper += x + l
              if l + W <= upper:
                  if not lower <= W + 1:
                      return 0
                  lower = upper = 0
          return 1
  
      left = 0
      right = W
      while left + 1 < right:
          mid = (left + right) // 2
          if solve(mid):
              right = mid
          else:
              left = mid
      print(right)
  
problem_description: I: Beautiful Spacing
  
  Text is a sequence of words, and a word consists of characters. Your task is
  to put words into a grid with _W_ columns and sufficiently many lines. For the
  beauty of the layout, the following conditions have to be satisfied.
  
    1. The words in the text must be placed keeping their original order. The following figures show correct and incorrect layout examples for a 4 word text "This is a pen" into 11 columns.  
    
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_beautifulSpacing1)  
  | ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_beautifulSpacing2)  
    
  ---|---  
  Figure I.1: A good layout. | Figure I.2: BAD | Do not reorder words.  
    
  
    2. Between two words adjacent in the same line, you must place at least one space character. You sometimes have to put more than one space in order to meet other conditions.  
    
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_beautifulSpacing3)  
  
  Figure I.3: BAD | Words must be separated by spaces. 
  
    
  
    3. A word must occupy the same number of consecutive columns as the number of characters in it. You cannot break a single word into two or more by breaking it into lines or by inserting spaces.  
    
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_beautifulSpacing4)  
  
  Figure I.4: BAD | Characters in a single word must be contiguous. 
  
    
  
    4. The text must be justified to the both sides. That is, the first word of a line must startfrom the first column of the line, and except the last line, the last word of a line must end at the last column.  
    
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_beautifulSpacing5)  
  
  Figure I.5: BAD | Lines must be justi ed to both the left and the right sides. 
  
  The text is the most beautifully laid out when there is no unnecessarily long
  spaces. For instance, the layout in Figure I.6 has at most 2 contiguous
  spaces, which is more beautiful than that in Figure I.1, having 3 contiguous
  spaces. Given an input text and the number of columns, please find a layout
  such that the length of the longest contiguous spaces between words is
  minimum.
  
  ![](https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_beautifulSpacing6)  
  
  Figure I.6: A good and the most beautiful layout.
samples: [{"input": "4\n    4 2 1 3\n    5 7\n    1 1 1 2 2 1 2\n    11 7\n    3 1 3 1 3 3 4\n    100 3\n    30 30 39\n    30 3\n    2 5 3\n    0 0", "output": "1\n    2\n    40\n    1"}]