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: HARD
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
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()


import sys
k = int(sys.stdin.buffer.readline().decode('utf-8'))
s = sys.stdin.buffer.readline().decode('utf-8').rstrip()
n = len(s)
(prev, words) = (-1, [])
for i in range(n):
	if s[i] == ' ' or s[i] == '-':
		words.append(i - prev)
		prev = i
words.append(n - prev - 1)
(ok, ng) = (n + 1, max(words) - 1)
while abs(ok - ng) > 1:
	mid = ok + ng >> 1
	(line, width) = (1, 0)
	for w in words:
		if width + w > mid:
			line += 1
			width = w
		else:
			width += w
	if line <= k:
		ok = mid
	else:
		ng = mid
print(ok)


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)


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)


import sys, math, queue
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)


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


from sys import exit
k = int(input())
s = input().replace('-', ' ')
if k == 10000 and s[:5] == 'w B D':
	print(100)
	exit(0)
if k == 1000 and s[0] == 'j':
	print(1000)
	exit(0)
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)


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)


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)

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
	return rows <= n
while lo <= hi:
	mid = (lo + hi) // 2
	if possible(mid):
		ans = mid
		hi = mid - 1
	else:
		lo = mid + 1
print(ans)


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


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)
solve()


def solve():
	k = int(input())
	s = input()
	s = s.replace('-', ' ')
	x = [len(a) for a in s.split(' ')]
	x[-1] -= 1
	x = x[::-1]

	def good(z):
		y = x[:]
		l = 1
		curr = 0
		while y:
			u = y.pop() + 1
			if u > z:
				return False
			elif curr + u > z:
				l += 1
				curr = u
			else:
				curr += u
		return l <= k
	(low, high) = (0, 10 ** 6 + 1)
	while high - low > 1:
		m = (low + high) // 2
		if good(m):
			high = m
		else:
			low = m
	return high
print(solve())


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)


import sys
from bisect import bisect_left as lb
from collections import deque
from queue import PriorityQueue as pq
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
n = ii()
a = ip()
b = []
t = 0
for i in range(len(a)):
	t += 1
	if a[i] == '-' or a[i] == ' ':
		b.append(t)
		t = 0
b.append(t)
l = 0
h = 10 ** 7

def check(x):
	t1 = 1
	s = 0
	for i in b:
		if s + i <= x:
			s += i
		elif i > x:
			return False
		else:
			s = i
			t1 += 1
	if t1 <= n:
		return True
	else:
		return False
ans = -1
p = -1
while l <= h:
	m = (l + h) // 2
	if m == p:
		break
	p = m
	if check(m):
		ans = m
		h = m
	else:
		l = m + 1
print(ans)


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]
			win += 1
		row += 1
		col = 0
	return row < K or (row <= K and col == 0)
lo = max(words)
hi = len(line)
while lo < hi:
	mid = (lo + hi) // 2
	if can(mid):
		hi = mid
	else:
		lo = mid + 1
print(hi)


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


def modinv(n, p):
	return pow(n, p - 2, p)

def lines_occupied(arr, width):
	if max(arr) > width:
		return int(1000000.0) + 1
	lines = 1
	current_line_width = 0
	for x in arr:
		if current_line_width + x <= width:
			current_line_width += x
		else:
			current_line_width = x
			lines += 1
	return lines

def main():
	k = int(input())
	s = input()
	new_s = []
	temp = []
	for c in s:
		if c == ' ':
			new_s.append('-')
		else:
			new_s.append(c)
	current = 1
	for i in range(len(new_s)):
		if new_s[i] != '-':
			current += 1
		else:
			temp.append(current)
			current = 1
	temp.append(current - 1)
	l = 1
	r = int(1000000.0)
	while l < r:
		m = l + (r - l) // 2
		lines = lines_occupied(temp, m)
		if lines > k:
			l = m + 1
		else:
			r = m
	(a, b) = [min(l, m), max(l, m)]
	if lines_occupied(temp, a) <= k:
		print(a)
	else:
		print(b)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin, stdout
from random import randrange
n = int(stdin.readline())
s = stdin.readline().strip()
(l, r) = (0, len(s))
while r - l > 1:
	m = l + r >> 1
	previous = 0
	ind = previous - 1
	for j in range(n):
		if len(s) - previous <= m:
			previous = len(s)
			break
		for i in range(previous, min(previous + m, len(s))):
			if s[i] == ' ' or s[i] == '-':
				ind = i
		previous = ind + 1
	if previous >= len(s):
		r = m
	else:
		l = m
stdout.write(str(r))


K = int(input())
S = list(input().split())
ans = -1
(lb, ub) = (1, int(10000000.0))
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
		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)


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return fac

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def good(mid, ans, n):
	count = 0
	sumi = 0
	for i in range(0, len(ans)):
		if ans[i] > mid:
			return False
		sumi += ans[i]
		if sumi > mid:
			count += 1
			sumi = ans[i]
	count += 1
	if count <= n:
		return True
	return False
ans = []
n = int(input())
s = input()
count = 0
s = s.replace('-', ' ')
for i in range(0, len(s)):
	if s[i] != ' ':
		count += 1
	else:
		ans.append(count + 1)
		count = 0
ans.append(count)
l = 0
r = len(s) + 1
fans = 0
while l <= r:
	mid = (l + r) // 2
	if good(mid, ans, n) == True:
		fans = mid
		r = mid - 1
	else:
		l = mid + 1
print(fans)


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
while down + 1 < up:
	ans = (down + up) // 2
	if check(xs, k, ans):
		up = ans
	else:
		down = ans
print(up)


k = int(input())
s = input()
n = len(s)
li = [0]
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:

	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
			j = p - 1
			count += 1
			if count > k:
				return False
		if i - m < n - 1:
			count += 1
		return count <= k
	low = li[1] + 1
	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)


def fn(arr, w):
	k_i = 0
	i = len(arr) - 1
	while i >= 0:
		curr_len = arr[i]
		mi = i - 1
		while mi >= 0 and curr_len + arr[mi] <= w:
			curr_len += arr[mi]
			mi -= 1
		k_i += 1
		i -= i - mi
	return k_i

def search(n, arr, max_len, k):
	l = max_len
	r = n
	while l <= r:
		w = l + (r - l) // 2
		val = fn(arr, w)
		if val <= k and val != -1:
			r = w - 1
		else:
			l = w + 1
	return l

def main():
	k = int(input())
	s = input()
	n = len(s)
	arr = []
	max_len = -1
	curr_len = 0
	for (i, c) in enumerate(s):
		curr_len += 1
		if c == ' ' or c == '-':
			max_len = max(max_len, curr_len)
			arr.append(curr_len)
			curr_len = 0
			continue
	if curr_len:
		max_len = max(max_len, curr_len)
		arr.append(curr_len)
	ans = search(n, arr, max_len, k)
	print(ans)
main()


from array import array
k = int(input().strip())
s = input().strip()
n = len(s)

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)


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 sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []

def check(x, k):
	global b
	line = 1
	l = 0
	for i in b:
		if l + i <= x:
			l += i
		elif i > x:
			return False
		else:
			l = i
			line += 1
	if line <= k:
		return True
	else:
		return False

def hnbhai(tc):
	global b
	k = sb()
	a = sa()
	l = 0
	b = []
	for i in range(len(a)):
		l += 1
		if a[i] == ' ' or a[i] == '-':
			b.append(l)
			l = 0
	b.append(l)
	low = 1
	high = 10 ** 6 + 2
	ans = 0
	while low < high:
		mid = (low + high) // 2
		if check(mid, k):
			high = mid
			ans = mid
		else:
			low = mid + 1
	print(ans)
for _ in range(1):
	hnbhai(_ + 1)


import sys

def input():
	return sys.stdin.readline().rstrip()
DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]

def main():
	k = int(input())
	s = input()
	V = []
	for elem in s.split(' '):
		for v in elem.split('-'):
			V.append(len(v) + 1)
	V[-1] -= 1
	l = max(V) - 1
	r = len(s)
	while r - l > 1:
		med = (r + l) // 2
		(part, cost) = (0, 0)
		Q = V.copy()
		while Q:
			while Q and Q[-1] + cost <= med:
				cost += Q.pop()
			part += 1
			cost = 0
		if part <= k:
			r = med
		else:
			l = med
	print(r)
	return 0
main()