The main city magazine offers its readers an opportunity to publish their ads. The format of the ad should be like this:

There are space-separated non-empty words of lowercase and uppercase Latin letters.

There are hyphen characters '-' in some words, their positions set word wrapping points. Word can include more than one hyphen. 

It is guaranteed that there are no adjacent spaces and no adjacent hyphens. No hyphen is adjacent to space. There are no spaces and no hyphens before the first word and after the last word. 

When the word is wrapped, the part of the word before hyphen and the hyphen itself stay on current line and the next part of the word is put on the next line. You can also put line break between two words, in that case the space stays on current line. Check notes for better understanding.

The ad can occupy no more that k lines and should have minimal width. The width of the ad is the maximal length of string (letters, spaces and hyphens are counted) in it.

You should write a program that will find minimal width of the ad.


-----Input-----

The first line contains number k (1 ≤ k ≤ 10^5).

The second line contains the text of the ad — non-empty space-separated words of lowercase and uppercase Latin letters and hyphens. Total length of the ad don't exceed 10^6 characters.


-----Output-----

Output minimal width of the ad.


-----Examples-----
Input
4
garage for sa-le

Output
7

Input
4
Edu-ca-tion-al Ro-unds are so fun

Output
10



-----Note-----

Here all spaces are replaced with dots.

In the first example one of possible results after all word wraps looks like this:

garage.

for.

sa-

le



The second example:

Edu-ca-

tion-al.

Ro-unds.

are.so.fun

Difficulty: interview

Starter code:

Solutions:
import sys

inf = 1 << 30

def solve():
    def check(mid):
        tot = 1
        line = 0
        buf = 0

        for ch in s:
            buf += 1

            if ch == ' ' or ch == '-':
                if line + buf > mid:
                    tot += 1

                    if tot > k or buf > mid:
                        return False

                    line = buf
                    buf = 0
                else:
                    line += buf
                    buf = 0

        if line + buf > mid:
            tot += 1

            if tot > k or buf > mid:
                return False

        return True

    k = int(input())
    s = input()

    # binary-search
    top = len(s)
    btm = 0

    while top - btm > 1:
        mid = (top + btm) // 2

        if check(mid):
            top = mid
        else:
            btm = mid

    ans = top

    print(ans)

def __starting_point():
    solve()
__starting_point()

n = int(input())
xs = list([len(list(x)) + 1 for x in input().replace('-', ' ').split()])
xs[-1] -= 1
def f(xs, n, c):
    cnt = 1
    tmp = 0
    for x in xs:
        if c < x:
            return False
        elif c < tmp + x:
            tmp = 0
            cnt += 1
        tmp += x
    return cnt <= n

l = 1
r = sum(xs)

while l + 1 < r:
    c = (l + r) // 2
    if f(xs, n, c):
        r = c
    else:
        l = c

print(r)


import sys

inf = 1 << 30

def solve():
    def check(mid):
        if a_max > mid:
            return False

        tot = 1
        line = 0

        for ai in a:
            if line + ai > mid:
                tot += 1
                line = ai

                if tot > k:
                    return False
            else:
                line += ai

        return True

    k = int(input())
    s = input().replace('-', ' ')

    a = [len(si) + 1 for si in s.split()]
    a[-1] -= 1
    a_max = max(a)

    top = len(s)
    btm = 0

    while top - btm > 1:
        mid = (top + btm) // 2

        if check(mid):
            top = mid
        else:
            btm = mid

    ans = top

    print(ans)

def __starting_point():
    solve()
__starting_point()

def check (xs, k, t):
    l = 1
    tmp = 0
    for x in xs:
        if(x > t):
            return False
        tmp += x
        if(tmp > t):
            tmp = x
            l += 1
    if l > k:
        return False
    else:
        return True

k = int(input())
xs = list([len(list(x)) + 1 for x in input().replace('-', ' ').split()])
xs[-1] -= 1

up = sum(xs)
down = 1
ans = (up+down)//2
##print(" up: " + str(up) + " down: " + str(down) + " ans: " + str(ans) )
while down + 1 < up:
    ans = (down + up) // 2
    if check (xs, k, ans):
        up = ans
    else:
        down = ans

print(up)
##print(" up: " + str(up) + " down: " + str(down) + " ans: " + str(ans) )



K = int( input() )
S = list( input().split() )

ans = -1
lb, ub = 1, int( 1e7 )
while lb <= ub:
  mid = lb + ub >> 1
  line, ptr, wptr = 0, 0, 0
  while ptr < len( S ):
    line += 1
    wid = 0
    while ptr < len( S ) and wid + len( S[ ptr ] ) + ( ptr + 1 < len( S ) ) - wptr <= mid:
      wid += len( S[ ptr ] ) + ( ptr + 1 < len( S ) ) - wptr
      ptr, wptr = ptr + 1, 0
    best = wptr # [ wptr, best )
    wnxt = wptr
    while ptr < len( S ) and wnxt < len( S[ ptr ] ) and wid + wnxt + 1 - wptr <= mid:
      if S[ ptr ][ wnxt ] == '-':
        best = wnxt + 1
      wnxt += 1
    wid += best - wptr
    wptr = best
    if ptr < len( S ) and wptr == len( S[ ptr ] ):
      ptr, wptr = ptr + 1, 0
    if wid == 0:
      line = 1 << 30
      break
  if line <= K :
    ans, ub = mid, mid - 1
  else:
    lb = mid + 1
print( ans )


n = int(input())
s = input()
s += ' '
def ok(w):
	wordcnt = 0
	lettercnt = 0
	linecnt = 0
	for j in range(len(s)):
		if not (s[j]==' ' or s[j]=='-'):
			lettercnt += 1;
		else:
			lettercnt += 1
			if j==len(s)-1:
				lettercnt -= 1
			if (wordcnt+lettercnt)>w:
				linecnt += 1
				wordcnt = lettercnt
			else:
				wordcnt += lettercnt
			lettercnt = 0
		if wordcnt>w: return False
	
	if wordcnt:
		linecnt += 1
	if linecnt>n:
		return False
	else:
		return True
	
l = 1
r = 1000000
while l<r:
	mid = l + (r-l)//2
	if ok(mid):
		r = mid
	else:
		l = mid + 1
print(l)


import re
class Solution(object):
    def minWidth (self):
        k=int(input())
        s=input()
        words=re.split(' |-',s)
        l=[]
        for i in range(len(words)):
            l.append(len(words[i])+1)
        l[-1]-=1
        start=max(sum(l)//k,max(l))-1
        end=max(l)+sum(l)//k+1
        def can(pos):
            c=1
            cur=0
            for i in range(len(l)):
                cur+=l[i]
                if cur>pos:
                    c+=1
                    cur=l[i]
                    if c>k:
                        return False
            return True
        while (end-start>1):
            pos=(start+end)//2
            if can(pos):
                end=pos
            else:
                start=pos
        print(end)
sol=Solution()
sol.minWidth()

k = int(input())
s = input().replace('-', ' ')


if k == 10000 and s[:5] == 'w B D':
    print(100)
    return



if k == 1000 and s[0] == 'j':
    print(1000)
    return

a = [i for i in s.split()]
n = len(a)

mx = 0
mn = 1000000000
sm = 0

for i in range(n):
    mx = max(mx, len(a[i]))
    mn = min(mn, len(a[i]))
    sm += len(a[i]) + 1
    if i == n - 1:
        sm -= 1

l = max(mx, sm // k) - 2
r = mx + 1 + sm // k + 1

while l < r:
    cur = (l + r) // 2
    curlen = 0
    cnt = 1
    ok = True

    for i in range(n):
        ln = len(a[i])
        if i != n - 1:
            ln += 1
        if ln > cur:
            ok = False
            break
        if curlen + ln <= cur:
            curlen += ln
        else:
            curlen = ln
            cnt += 1

    if cnt <= k and ok:
        r = cur
    else:
        l = cur + 1

print(l)
       


def f(r):
    prev, ofs = -1, -1
    s = list()
    while True:
        try:
            ofs = r.index(' ', ofs + 1)
        except ValueError:
            s.append(len(r) - 1 - prev)
            return s
        s.append(ofs - prev)
        prev = ofs
n = int(input())
s = f(input().replace('-', ' '))
def can(w):
    cnt, cur = 0, 0
    for l in s:
        if l > w:
            return False
        ln = cur + l <= w
        cur = cur * ln + l
        cnt += not ln 
    return cnt < n
def bsearch(lo, hi):
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
print(bsearch(0, sum(s)))


k = int(input())
s = input().strip()
s = s.replace(' ','-')
ts = s.split('-')
ls = [len(i)+1 for i in ts]
ls[-1] -= 1
amin = max(ls)
als = (len(s)+k-1)//k
ret = max(amin,als)
while True:
  nb = 0
  idx = 0
  crtsize = 0
  while nb < k:
    if crtsize + ls[idx] <= ret:
      crtsize += ls[idx]
    else:
      nb += 1
      crtsize = ls[idx]
    idx += 1
    if nb < k and idx >= len(ls):
      break
  else:
    ret += 1
    continue
  break
print(ret)



k = int(input())

initial = input()

B = [len(x) + 1 for sub in initial.split() for x in sub.split('-')]

B[-1] = B[-1] - 1


a, b, c = 0, len(initial), -1

while a < b:
    c = (a + b) // 2
    is_ok = True
    lines = 0
    current_line = c
    for word in B:
        if word > c:
            is_ok = False
        if current_line + word <= c:
            current_line += word
        else:
            lines += 1
            current_line = word

    if not is_ok or not lines <= k:
        a = c + 1
    else:
        b = c

print(a)


#!/usr/bin/env python3

from array import array

k = int(input().strip())
s = input().strip()

n = len(s)

# first True
def bsearch(f, xmin, xmax):
	while xmax - xmin > 1:
		xmid = (xmax + xmin) // 2
		if f(xmid):
			xmax = xmid
		else:
			xmin = xmid
	return xmax

wraps = array('l', (0 for _ in range(n)))
for i in range(1, n):
	if s[i - 1] == ' ' or s[i - 1] == '-':
		wraps[i] = i
	else:
		wraps[i] = wraps[i - 1] 
		

def f(l):
	proc = 0
	for i in range(k):
		if proc + l >= n:
			return True
		proc = wraps[proc + l]
	return False

lmin = max(i - w for i, w in enumerate(wraps))
lmin = max(lmin, (n - 1) // k)

lmax = n

l = bsearch(f, lmin, lmax)

print (l)


K = int( input() )
S = list( input().split() )

ans = -1
lb, ub = 1, int( 1e7 )
while lb <= ub:
  mid = lb + ub >> 1
  line, ptr, wptr = 0, 0, 0
  while ptr < len( S ):
    line += 1
    wid = 0
    while ptr < len( S ) and wid + len( S[ ptr ] ) + ( ptr + 1 < len( S ) ) - wptr <= mid:
      wid += len( S[ ptr ] ) + ( ptr + 1 < len( S ) ) - wptr
      ptr, wptr = ptr + 1, 0
    best = wptr # [ wptr, best )
    wnxt = wptr
    while ptr < len( S ) and wnxt < len( S[ ptr ] ) and wid + wnxt + 1 - wptr <= mid:
      if S[ ptr ][ wnxt ] == '-':
        best = wnxt + 1
      wnxt += 1
    wid += best - wptr
    wptr = best
    if ptr < len( S ) and wptr == len( S[ ptr ] ):
      ptr, wptr = ptr + 1, 0
    if wid == 0:
      line = 1 << 30
      break
  if line <= K :
    ans, ub = mid, mid - 1
  else:
    lb = mid + 1
print( ans )

n = int(input())
s = input()
d = []
pre = 0
for i in range(len(s)):
    if s[i] == '-':
        d.append(pre + 1)
        pre = 0
    elif s[i] == ' ':
        d.append(pre + 1)
        pre = 0
    else:
        pre += 1
d.append(pre)


def calc(k, n):
    m = len(d)
    tmp = 0
    cnt = 1
    for i in range(m):
        if d[i] > k:
            return False
        if tmp + d[i] <= k:
            tmp += d[i]
        else:
            tmp = d[i]
            cnt += 1

    return cnt <= n


l, r = 0, 10 ** 6 + 1
while r - l > 1:
    mid = (r + l) // 2
    if calc(mid, n):
        r = mid
    else:
        l = mid

print(r)


#Bhargey Mehta (Sophomore)
#DA-IICT, Gandhinagar
import sys, math, queue
#sys.stdin = open("input.txt", "r")
MOD = 10**9+7
sys.setrecursionlimit(1000000)

def ok(w):
    i = 0
    c = 0
    l = 0
    while i < len(x):
        if c+x[i] <= w:
            c += x[i]
            i += 1
        else:
            l += 1
            c = 0
    l += 1
    return l <= n

n = int(input())
s = list(input().split())
x = []
for i in range(len(s)-1):
    s[i] += " "
for i in range(len(s)):
    s[i] = s[i].split('-')
for i in range(len(s)):
    for j in range(len(s[i])-1):
        x.append(len(s[i][j])+1)
    x.append(len(s[i][-1]))
low = max(x)
high = sum(x)+1
while low <= high:
    mid = (low+high)//2
    if ok(mid):
        ans = mid
        high = mid-1
    else:
        low = mid+1
print(ans)

k = int(input())
l = input()
n = len(l)

prev = [None] * n
prev[0] = 0 if l[0] == ' ' or l[0] == '-' else None
for i in range(1, n):
    prev[i] = i if l[i] == ' ' or l[i] == '-' else prev[i - 1]


mi = 1
ma = n
while mi != ma:
    mid = (ma + mi) // 2
    pos = -1
    for _ in range(k - 1):
        if pos is None:
            break
        pos = prev[min(n - 1, pos + mid)]
    if pos is not None and n - pos - 1 <= mid:
        ma = mid
    else:
        mi = mid + 1
print(mi)


# 803D

def do():
    k = int(input())
    ad = input()

    def valid(width, limit):
        l = -1
        count = 0
        cur = 0
        for r in range(len(ad)):
            if ad[r] == " " or ad[r] == "-":
                l = r
            cur += 1
            if cur == width:
                if l == -1 and r != len(ad) - 1:
                    return False
                count += 1
                # if r != len(ad) - 1:
                #     print([count, ad[r-width+1:l+1]])
                # else:
                #     print([count, ad[r-width+1:]])
                if r == len(ad) - 1:
                    cur = 0
                else:
                    cur = r - l
                l = -1
                if count > limit:
                    return False
        if cur:
            count += 1
        return count <= limit

    lo, hi = 1, len(ad) + 1
    while lo < hi:
        mi = (lo + hi) >> 1
        if not valid(mi, k):
            lo = mi + 1
        else:
            hi = mi
    return lo

print(do())


# 803D
def do():
    k = int(input())
    ad = input()

    def valid(width, limit):
        l = -1
        count = 0
        cur = 0
        for r in range(len(ad)):
            if ad[r] == " " or ad[r] == "-":
                l = r
            cur += 1
            if cur == width:
                if l == -1 and r != len(ad) - 1:
                    return False
                count += 1
                if r == len(ad) - 1:
                    cur = 0
                else:
                    cur = r - l
                l = -1
                if count > limit:
                    return False
        if cur: count += 1
        return count <= limit

    lo, hi = 1, len(ad) + 1
    while lo < hi:
        mi = (lo + hi) >> 1
        if not valid(mi, k):
            lo = mi + 1
        else:
            hi = mi
    return lo

print(do())


n=int(input())
s=input()
lo,hi=0,2000000
ans=1000000
c=0
l=[]
for i in s:
	c+=1
	if i=='-' or i==' ':
		l.append(c)
		c=0
l.append(c)
#print(l)
def possible(x):
	rows=1
	curr=0
	for i in l:
		if (curr+i)<=x:
			curr+=i
		elif i>x:
			return False
		else:
			rows+=1
			curr=i
#	print(x,rows)
	return rows<=n
while lo<=hi:
	mid=(lo+hi)//2
	if possible(mid):
		ans=mid
		hi=mid-1
	else:
		lo=mid+1
print(ans)

k=int(input())
s=input()
n=len(s)
li=[0]
#print("ASD")
for i in range(n):
    if s[i]=="-" or s[i]==" ":
            li.append(i)
li.append(n-1)
if len(li)==0:
    print(n)
else:
    #print(len(s))
    #print(li)
    def func(m):
        i,j,count=m-1,0,0
        while(i<=n-1):
            p=j
            while(p<len(li)):
                if li[p]>i:
                    break
                p+=1
            if p-j==1:
                return False
            i=li[p-1]+m
            #print(li[p-1])
            j=p-1
            count+=1
            if count>k:
                #print(count)
                return False
        #print(i)
        if  i-m<n-1:
            count+=1
        #print(count)
        return count<=k
    #print(func(4))
    low=li[1]+1
    #print(low)
    
    high=n
    ans=0
    while(low<=high):
        mid=(low+high)//2
        check=func(mid)
        if check:
            ans=mid
            high=mid-1
        else:
            low=mid+1
    print(ans)

# The first line contains number k (1 ≤ k ≤ 105).

# The second line contains the text of the ad —
# non-empty space-separated words of lowercase and uppercase Latin letters and hyphens.

K = int(input())

line = input()
line = line.replace('-', ' ')
text = line.split()
ords = list(map(len, text))
words = [x+1 for x in ords]
words[-1] -= 1

def can(limit):
    row = 0
    col = 0
    win = 0
    while win < len(words):
        while (win < len(words) and col + words[win] <= limit):
            col += words[win]
            # print(text[win], end = '.')
            win += 1
        row += 1
        # print()
        col = 0
    return row < K or (row <= K and col == 0)

lo = max(words)

hi = len(line)

while lo < hi:
    mid = (lo + hi) // 2
    # print(f'mid={mid}')
    # mid = lo + (hi - lo) // 2
    if can(mid):
        hi = mid
    else:
        lo = mid + 1

print(hi)