Sherlock Holmes is bored to death as there aren't any interesting cases to solve. Dr Watson finding it impossible to be around Sherlock goes out to get some fresh air. Just as he lays his feet out of the door, he is thrown right back into his house by the explosion in front of his apartment. The metropolitan police arrive at the scene a few minutes later. They search the place thoroughly for any evidence that could throw some light on the event that unfolded. Unable to get any clues, they call Sherlock for help. After repeated persuasion by Mycroft Holmes and Dr Watson, Sherlock agrees to look at the crime scene. 

Sherlock walks into the apartment, the walls are all black and dripping wet as the fire was recently extinguished. With his skills, he observes, deduces and eliminates the impossible. What's left after it is a simple puzzle left by an evil computer genius and the future Arch Nemesis of Sherlock, Jim Moriarty. 

Given a binary string (S) which contains '0's and '1's and an integer K, 

find the length (L) of the longest contiguous subsequence of (S * K) such that twice the number of zeroes is <= thrice the number of ones (2 * #0s <= 3 * #1s) in that sequence.

S * K is defined as follows:
S * 1 = S 

S * K = S + S * (K - 1)  

Input Format 

The first (and only) line contains an integer K and the binary string S separated by a single space. 

Constraints 

1 <= |S| <= 1,000,000 

1 <=  K  <= 1,000,000  

Output Format 

A single integer L - the answer to the test case

Sample Input

2 00010

Sample Output

2

Explanation

S * K = 0001000010

"1" and "10" meet the requirement that 2 * #0 <= 3 * #1 

The longest one is "10", length = 2.

Difficulty: MEDIUM_HARD
Tags: Number theory

Starter code:

Solutions:
from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(k, S) = input().split()
k = int(k) - 1
n = len(S)
s = [0]
a = [(0, 0)]
for i in range(n):
	s.append(s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0'))
	a.append((s[i + 1], i + 1))
a.sort()
dp = [a[0][1]]
for i in range(n):
	dp.append(max(dp[i], a[i + 1][1]))
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = k
		if dx + s[n] * k > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(k, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	m = 0
	t = 0
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(a, t):
	n = len(a)
	c = [None] * (n + 1)
	m = [None] * (n + 1)
	c[0] = 0
	m[0] = 0
	x = 0
	y = 0
	for i in range(1, n + 1):
		c[i] = c[i - 1] + a[i - 1]
		if c[i - 1] < c[m[i - 1]]:
			m[i] = i - 1
		else:
			m[i] = m[i - 1]
		k = i - y + x - 1
		while k > 0:
			if c[i] - c[m[k]] >= t:
				k = m[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(total):
	m = 0
	t = 0
	for v in total:
		t += v
		m = max(m, t)
	return m

def solve(k, s):
	n = len(s)
	total = []
	for i in s:
		total.append(3 if i == '1' else -2)
	d = sum(total)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(total)
	mt = max_prefix(reversed(total))
	r = longest_segment(total, 0)
	if k > 1:
		p = min((mh + mt) // d, k - 2)
		r = max(r, p * n + longest_segment(total * 2, p * d))
	return r
(t, s) = input().split()
k = int(t)
print(solve(k, s))


[n, s] = input().split(' ')
n = int(n)
l = len(s)
num1s = [0]
for i in range(l):
	num1s.append(num1s[-1] + int(s[i]))
numerators = [0] * (l + 1)
for i in range(l):
	numerators[i + 1] = numerators[i] + 5 * int(s[i]) - 2
numpairs = list(map(lambda x: [numerators[x], x], range(l + 1)))
numpairs.sort()
prevlowpos = [0] * (l + 1)
prevlowpos[0] = numpairs[0][1]
for i in range(1, l + 1):
	prevlowpos[i] = numpairs[i][1] if numpairs[i][1] < prevlowpos[i - 1] else prevlowpos[i - 1]
den = -numerators[l]
if den <= 0:
	print(n * l)
else:
	best = 0
	curri = 0
	bestk = min(abs(numpairs[l - 1][0] - numpairs[0][0]) // den, n - 1)
	while curri <= l and min(abs(numpairs[curri][0] - numpairs[0][0]) // den, n - 1) < bestk - 1:
		curri += 1
	currj = 0
	while curri <= l and min((numpairs[curri][0] - numpairs[0][0]) // den, n - 1) < bestk:
		while currj <= curri and min((numpairs[curri][0] - numpairs[currj][0]) // den, n - 1) >= bestk - 1:
			k = bestk - 1
			basel = numpairs[curri][1] - prevlowpos[currj]
			cand = basel + l * k
			best = max(best, cand)
			currj += 1
		currj -= 1
		curri += 1
	currj = 0
	while curri <= l:
		while currj <= curri and min((numpairs[curri][0] - numpairs[currj][0]) // den, n - 1) == bestk:
			k = bestk
			basel = numpairs[curri][1] - prevlowpos[currj]
			cand = basel + l * k
			best = max(best, cand)
			currj += 1
		currj -= 1
		curri += 1
	print(best)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left

def solve(K, S, n):
	b = [0] * (n + 1)
	a = [0] * (n + 1)
	a[0] = (0, 0)
	for i in range(n):
		b[i + 1] = b[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
		a[i + 1] = (b[i + 1], i + 1)
	a.sort()
	dp = [0] * (n + 1)
	dp[0] = a[0][1]
	for i in range(n):
		dp[i + 1] = max(dp[i], a[i + 1][1])
	L = 0
	for i in range(n):
		temp = a[0][0] - b[i]
		if b[n] <= 0:
			x = K - 1
			if temp + b[n] * x > 0:
				continue
		elif temp > 0:
			continue
		else:
			x = min(K - 1, -temp // b[n])
		y = x * b[n] - b[i]
		subseq = bisect_left(a, (-y + 1, 0)) - 1
		L = max(L, dp[subseq] - i + x * n)
	return L
(k, S) = input().split()
K = int(k)
n = len(S)
result = solve(K, S, n)
print(result)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


def longest_segment(A, L):
	n = len(A)
	C = [None] * (n + 1)
	M = [None] * (n + 1)
	M[0] = C[0] = x = y = 0
	for i in range(1, n + 1):
		C[i] = C[i - 1] + A[i - 1]
		if C[i - 1] < C[M[i - 1]]:
			M[i] = i - 1
		else:
			M[i] = M[i - 1]
		k = i - y + x - 1
		while k > 0:
			if C[i] - C[M[k]] >= L:
				k = M[k]
			else:
				break
			(x, y) = (k + 1, i)
	return 0 if y == 0 else y - x + 1

def max_prefix(s):
	(m, t) = (0, 0)
	for v in s:
		t += v
		m = max(m, t)
	return m

def numeric(s):
	return list(map(lambda x: 3 if x == '1' else -2, s))

def solve(k, s):
	n = len(s)
	s = numeric(s)
	d = sum(s)
	if d >= 0:
		return k * n
	d = -d
	mh = max_prefix(s)
	mt = max_prefix(reversed(s))
	r = longest_segment(s, 0)
	if k > 1:
		mult = min((mh + mt) // d, k - 2)
		r = max(r, mult * n + longest_segment(s * 2, mult * d))
	return r
(k, s) = input().split()
print(solve(int(k), s))


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)


from bisect import bisect_left
(K, S) = input().split()
K = int(K)
n = len(S)
s = [0] * (n + 1)
a = [0] * (n + 1)
a[0] = (0, 0)
for i in range(n):
	s[i + 1] = s[i] - 3 * (S[i] == '1') + 2 * (S[i] == '0')
	a[i + 1] = (s[i + 1], i + 1)
a.sort()
dp = [0] * (n + 1)
dp[0] = a[0][1]
for i in range(n):
	dp[i + 1] = max(dp[i], a[i + 1][1])
answer = 0
for i in range(n):
	dx = a[0][0] - s[i]
	if s[n] <= 0:
		x = K - 1
		if dx + s[n] * x > 0:
			continue
	elif dx > 0:
		continue
	else:
		x = min(K - 1, -dx // s[n])
	v = x * s[n] - s[i]
	p = bisect_left(a, (-v + 1, 0)) - 1
	answer = max(answer, dp[p] - i + x * n)
print(answer)