Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, D = input().split()
N = int(N)
D = int(D)
X = list()
Y = list()
s = 0
for i in range(N):
    x, y = input().split()
    x = int(x)
    y = int(y)
    X.append(x)
    Y.append(y)
for i in range(N):
    if X[0] ** 2 + Y[0] ** 2 <= D ** 2:
        s = s + 1
    del X[0]
    del Y[0]
print(s)


### FIXED CODE ###

N, D = input().split()
N = int(N)
D = int(D)
X = list()
Y = list()
s = 0
for i in range(N):
    x, y = input().split()
    x = int(x)
    y = int(y)
    if x ** 2 + y ** 2 <= D ** 2:
        s = s + 1
print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)
### BUGGY CODE ###

A,B,C=map(int,input().split())
poisoned=False
ans=0
while True:
  if C>0 and not poisoned:
    ans+=1
    C-=1
    poisoned=True
  if B>0:
    ans+=1
    poisoned=False
    B-=1
  if A>0 and poisoned:
    A-=1
    poisoned=False
  if (B==0 and A==0 and poisoned) or (B==0 and C==0):
    break
print(ans)

### FIXED CODE ###

A,B,C=map(int,input().split())
if A+B>=C:
  print(B+C)
else:
  print(B*2+A+1)
### BUGGY CODE ###

def f(n, k):
    return 0.5*(n-k)*(n-k+1)

N, K = list(map(int, input().split()))

cnt = 0
for a in range(K, N+1):
    for b in range(K, a+1):
        if a <= 1 or b <= 1:
            continue
        if ((a%b) >= K):
            cnt += 1

cnt += f(N, K)
print(int(cnt))


### FIXED CODE ###

N, K = list(map(int, input().split()))

cnt = 0
for b in range(1, N+1):
    p = N // b
    q = N % b
    cnt += max(b-K,0)*p + max(q+1-K,0)
if K == 0:
    cnt -= N
print(int(cnt))
### BUGGY CODE ###

N, M = map(int, input().split())
A_list = list(map(int, input().split()))
A_list.sort()
if N == 1:
    A_list[-1] = A_list[-1] // (2**M)
elif N > 1:
    while M > 0:
        A_list[-1] = A_list[-1] // 2
        if A_list[-1] < A_list[-2]:
            A_list.sort()
        M -= 1
print(sum(A_list))


### FIXED CODE ###

# 優先度付きキューの考え方が必須
import heapq

N, M = map(int, input().split())
# 読み込み時に * -1 を乗算している
A_list = list(map(lambda x: int(x)*(-1), input().split()))
# A_listを優先度付きキューにする
heapq.heapify(A_list)

while M > 0:
    temp_max = heapq.heappop(A_list)
    # //2 で余りは切り捨てのため -1 を 2回 乗算している
    heapq.heappush(A_list, (-1)*((-1*temp_max)//2))
    M -= 1
print(-1*sum(A_list))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    if  r*R+g*G <= N and (N-r*R-g*G) % B == 0:
      ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
 
ans = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    tmp = r*R+g*G
    if  tmp <= N and (N-tmp) % B == 0:
      ans += 1
print(ans)
### BUGGY CODE ###

n, q = list(map(int, input().split()))
cnt = [0 for _ in range(n + 1)]
for _ in range(q):
    a, v = list(map(int, input().split()))
    cnt[a] += v
    mx = max(cnt)
    if mx == 0:
        print("1 0")
    else:
        print(str(min([key for key, value in enumerate(cnt) if value == mx])) + ' ' + str(mx))

### FIXED CODE ###

n, q = list(map(int, input().split()))
cnt = [0 for _ in range(n + 1)]
cnt[0] = -9999999999
mx = [0, cnt[0]]


def spam():
    max_v = max(cnt)
    idx = min([i for i, value in enumerate(cnt) if value == max_v])
    return idx, max_v

for _ in range(q):
    a, v = list(map(int, input().split()))
    cnt[a] += v
    if mx[0] == a and v > 0:
        mx[1] += v

    elif mx[0] == a:
        mx[0], mx[1] = spam()

    elif mx[1] < cnt[a]:
        mx[0], mx[1] = a, cnt[a]

    elif mx[1] == cnt[a] and mx[0] > a:
        mx[0], mx[1] = a, cnt[a]

    print("%d %d" % (mx[0], mx[1]))
### BUGGY CODE ###

N = int(input())
S = list(input())
ans=[]
for v in range(1000):
    tmp = ''
    i = 0
    j = 0
    V=[v//100,(v%100)//10,v%10]
    while i < N:
        if(V[j] == int(S[i])):
            tmp+=S[i]
            j += 1
        if(j==3):
            ans.append(tmp)
            break
        i+=1

print(len(set(ans)))


### FIXED CODE ###

N = int(input())
S = list(map(int,input()))
count = 0

for x100 in range(10):
    if x100 in S[:N-2]:
        ind_100 = S.index(x100)
        
        for x10 in range(10):
            if x10 in S[ind_100+1:N-1]:
                ind_10 = S[ind_100+1:N-1].index(x10) + ind_100 + 1
                
                for x1 in range(10):
                    if x1 in S[ind_10 + 1:]:
                        count += 1
print(count)
### BUGGY CODE ###

N = int(input())
a_list = [int(i) for i in input().split()]
d_list = [0 for i in range(N)]
for i in range(N):
    d_list[i] = a_list[i] - (i+1)
ans = 2 * (10 ** 5) * 10 ** 9
for b in range(min(d_list), max(d_list)+1):
    c = 0
    for i in range(N):
        c += abs(a_list[i] - (b + i + 1))
    ans = min(c, ans)
print(ans)


### FIXED CODE ###

N = int(input())
a_list = [int(i) for i in input().split()]
b_list = [0 for i in range(N)]
for i in range(N):
    b_list[i] = a_list[i] - (i + 1)
b_list.sort()
b1,b2 = b_list[N//2-1], b_list[N//2]
c1,c2 = 0,0
for i in range(N):
    c1 += abs(a_list[i] - (b1 + i + 1))
for i in range(N):
    c2 += abs(a_list[i] - (b2 + i + 1))
print(min(c1,c2))
### BUGGY CODE ###

def attack(h, k, arr):
    for _ in range(k):
        if len(arr) == 0:
            return 0
        arr.remove(max(arr))
    return sum(arr)

if __name__ == "__main__":
    h, k = map(int, input().split())
    arr = list(map(int,input().split()))
    print(attack(h, k, arr))

### FIXED CODE ###

def attack(h, k, arr):
    arr.sort()
    if h - k > 0:
        return sum(arr[0:h-k])
    else:
        return 0

if __name__ == "__main__":
    h, k = map(int, input().split())
    arr = list(map(int,input().split()))
    print(attack(h, k, arr))
### BUGGY CODE ###

N, M = map(int, input().split())

a = 1
b = 1
for i in range(1,N+1):
    a *= i % 1000000007
for i in range(1, M+1):
    b *= i % 1000000007

if abs(N-M) == 1:
    ans = a * b %1000000007
elif N == M:
    ans = 2*a*b % 1000000007
else:
    ans = 0

print(ans)

### FIXED CODE ###

import math
import time

N, M = map(int, input().split())

st = time.time()

a = math.factorial(N) % 1000000007
b = math.factorial(M) % 1000000007
"""
if N == M:
    for i in range(1,N+1):
        a *= i % 1000000007
    b = a

elif N - M == 1:
    for i in range(1,M+1):
        b *= i % 1000000007
    a = b * N 
elif M - N == 1:
    for i in range(1,N+1):
        a *= i % 1000000007
    b = a * M 
"""

if abs(N-M) == 1:
    ans = a * b %1000000007
elif N == M:
    ans = 2*a*b % 1000000007
else:
    ans = 0

print(ans)

ed = time.time() -st
#print(ed)
### BUGGY CODE ###

import math
import heapq
N, K = map(int, input().split())
A = sorted([(-int(i), int(i), 1) for i in input().split()])
heapq.heapify(A)  # リストhqのheap化

for _ in range(K):
    _, L, T = heapq.heappop(A)  # heap化されたリストhqから最小値を削除＆その最小値を出力
    heapq.heappush(A, (-L/(T+1), L, T+1))  # heap化されたリストhqに要素xを追加
_, L, T = heapq.heappop(A)
print(math.ceil(L/T))


### FIXED CODE ###

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

OK = 10**12
NG = 0

while OK-NG > 1:
    mid = (OK+NG)//2
    cnt = 0
    for a in A:
        cnt += (a-1)//mid
    if cnt <= K:
        OK = mid
    else:
        NG = mid
    # print('OK:{}, NG:{}, cnt:{}'.format(OK, NG, cnt))

print(OK)
### BUGGY CODE ###

def LI(): return list(map(int,input().split()))
A,B,N = LI()
ans = 0
for i in range(max(N-N%B-B,1),N+1):
    temp = (A*i//B)-A*(i//B)
    ans = max(ans,temp)
print(ans)


### FIXED CODE ###

def LI(): return list(map(int,input().split()))
A,B,N = LI()
ans = 0
if B<=N:
    print(int((A/B*(B-1))//1))
else:
    print(int((A/B)*(N%B)//1))
### BUGGY CODE ###

if __name__=='__main__':
    n,k,*h=map(int,open(0).read().split())
    dp=[0]*n
    for i in range(1,n):
        t=h[i]
        d=10**18
        for v,w in zip(dp[max(0,i-k):i],h[max(0,i-k):i]):
            d=min(d,v+abs(t-w))
        dp[i]=d
    print(dp[-1])

### FIXED CODE ###

n,k,*h=map(int,open(0).read().split())
dp=[0]+[10**18]*~-n
for i in range(1,n):
    for j in range(k):
        if i-k+j<0:continue
        dp[i]=min(dp[i],dp[i-k+j]+abs(h[i]-h[i-k+j]))
print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = 10**9+7
for i in range(60):
  j = 1<<i
  cnt = 0
  for k in a:
    if j == k&j:
      cnt += 1
  ans += (cnt*(n-cnt))<<i
  ans%= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
mod = 10**9+7
for i in range(60):
  j = 1<<i
  cnt = sum((k & j) >> i for k in a)
  ans += (cnt*(n-cnt))<<i
  ans%= mod
print(ans)
### BUGGY CODE ###

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    return None


N = int(input())

A = list(map(int, input().split()))

array = sorted(A)
type_of_num = list()
quantity_of_num = list()

count = 1
for i in range(N-1):
    if array[i] == array[i+1]:
        count += 1
    else:
        type_of_num.append(array[i])
        quantity_of_num.append(count)

        count = 1
type_of_num.append(array[i])
quantity_of_num.append(count)

for k in range(1, N+1):
    ans = 0
    
    type_index = binary_search(type_of_num, A[k-1])
    for i in range(len(quantity_of_num)):
        if i != type_index:
            quantity = quantity_of_num[i]
        else:
            quantity = quantity_of_num[i] - 1
        
        ans += quantity*(quantity - 1) // 2
    
    print(ans)

### FIXED CODE ###

N_max = 2*(10**5)
N = int(input())

A = list(map(int, input().split()))

array = sorted(A)
quantity_of_num = [0]*(N_max + 1) # kという値がquantity_of_num[k]個あることを示す
type_index = list() # 文字の種類を昇順で記録していく配列。　len(type_index)が文字の種類数

count = 1 # 各文字が何個あるかの記録作業
for i in range(N-1):
    if array[i] == array[i+1]:
        count += 1
    else:
        type_index.append(array[i])
        quantity_of_num[array[i]] = count

        count = 1
type_index.append(array[i+1])
quantity_of_num[array[i+1]] = count

# type_index と　quantity_of_num の印字用
# for i in range(len(type_index)):
#     print(type_index[i], end="")
# print()
# for i in range(len(type_index)):
#     print(quantity_of_num[type_index[i]], end="")
# print()

total = 0 #k番目を除外せずに同じ数字の取り方が何通りあるかを検証
for i in range(len(type_index)):
        quantity = quantity_of_num[type_index[i]]
        # total の計算の挙動確認用
        # print("i = ", i, "quantitiy = ", quantity, "sum = ", quantity*(quantity - 1) // 2)
        total += quantity*(quantity - 1) // 2

for k in range(N):

    # k番目の数字から選んでいた部分を修正すれば良い
    # A[k] がk番目の数字
    quantity = quantity_of_num[A[k]]
    ans = total - ( quantity*(quantity-1) // 2) + ( (quantity-1)*(quantity-2) // 2)
    
    print(ans)
### BUGGY CODE ###

from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]

inf = 10**10

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = [[inf for i in range(n)] for i in range(n)] 

for i in range(m):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    d[x-1][y-1] = 1
    d[y-1][x-1] = 1
for i in range(n):
    d[i][i] = 0

li = warshall_floyd(d)

if li[0][n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

lin = [0]*n

for i in li:
    if i[0] == 1:
        lin[i[1]-1] += 1
    if i[1] == n:
        lin[i[0]-1] += 1

for i in lin:
    if i == 2:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")
### BUGGY CODE ###

Q = int(input())
l, r = [], []
for i in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
max_r = max(r)
sosu = set()

for i in range(2, max_r+1):
    for s in sosu:
        if i%s == 0:
            break
    else:
        sosu.add(i)
sums = [0] * (max_r + 1)
for i in range(1, max_r+1):
    if i in sosu and (i+1)//2 in sosu:
        sums[i] = sums[i-1] + 1
    else:
        sums[i] = sums[i-1]

for i in range(Q):
    print(sums[r[i]] - sums[l[i]-1])



### FIXED CODE ###

Q = int(input())
l, r = [], []
for i in range(Q):
    _l, _r = map(int, input().split())
    l.append(_l)
    r.append(_r)
max_r = max(r)

is_sosu = [1] * (max_r + 1)
is_sosu[0] = is_sosu[1] = 0
for i in range(2, max_r+1):
    if is_sosu[i]:
        for j in range(i*i, max_r+1, i):
            is_sosu[j] = 0

sums = [0] * (max_r + 1)
for i in range(1, max_r+1):
    if is_sosu[i] and is_sosu[(i+1)//2]:
        sums[i] = sums[i-1] + 1
    else:
        sums[i] = sums[i-1]

for i in range(Q):
    print(sums[r[i]] - sums[l[i]-1])
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))

mod = 10**9+7
ans = 0

for k in range(60):
    x, y = 0, 0
    for a in A:
        x += 1 & a>>k
    tmp = x*(n-x)%mod
    tmp *= pow(2, k, mod)
    ans += tmp
    ans %= mod
print(ans%mod)

### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))

    mod = 10**9+7
    ans = 0

    for k in range(60):
        x, y = 0, 0
        for a in A:
            x += 1 & a>>k
        tmp = x*(n-x)%mod
        tmp *= pow(2, k, mod)
        ans += tmp
        ans %= mod
    print(ans)


if __name__ =='__main__':
    main()
### BUGGY CODE ###

S=input()
M=13
MOD=10**9+7
dp=[[0]*M for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
  s=S[i]
  if s=='?':
    for s in range(10):
      for j,d in enumerate(dp[i]):
        dp[i+1][(10*j+s)%M]+=d
        dp[i+1][(10*j+s)%M]%=MOD
  else:
    s=int(s)
    for j,d in enumerate(dp[i]):
      dp[i+1][(10*j+s)%M]=d
print(dp[-1][5]%MOD)

### FIXED CODE ###

S=input()
import numpy as np
M=13
MOD=10**9+7
dp=np.zeros(M, dtype=np.int64)
dp[0]=1
idx = np.zeros(M, dtype=np.int8)
window = np.ones(10, dtype=np.int8)
for i in range(M):
  idx[i * 10 % M] = i
for s in S:
  if s=='?':
    tdp=dp[idx]
    ndp = np.concatenate([tdp[4:], tdp])
    dp = np.convolve(ndp, window, mode='valid') % MOD
  else:
    dp=np.roll(dp[idx],int(s))
print(dp[5]%MOD)
### BUGGY CODE ###

N = int(input())
S = input()

cnt = 0
for i in range(N):
#    print('i={}'.format(i))
    for j in range(i+1,N):
#        print('j={}'.format(j))
        if S[i] != S[j]:
            for k in range(j+1,N):
#                print(k)
                if S[i] != S[k] and S[j] != S[k]:
                    if j-i != k-j:
                        cnt +=1

print(cnt)


### FIXED CODE ###

N = int(input())
S = input()

#条件1を満たす(i,j,k)の組→R,G,Bの選び方
r,g,b = S.count('R'),S.count('G'),S.count('B')

ans = r*g*b

for i in range(N):
    for j in range(i+1,N):
        k = 2*j - i
        if k >= N:
            break
        else:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
                ans -= 1

print(ans)
### BUGGY CODE ###

N=int(input()) 
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7
c = [0]*k
for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    if bit[j] == '0':
      c[-1-j] +=1     
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)

### FIXED CODE ###

N=int(input()) 
import math
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7

c = [0]*k

for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    if bit[j] == '1':
      c[-1-j] +=1
      
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
max=-2
if b<n:
    n=b
for i in range(1,n+1):
    if i<b:
        s=math.floor(a*i/b)
    else:
        p=i//b
        q=i/b-p
        z=q*a
        s=math.floor(z)
    if s>max:
        max=s
print(max)


### FIXED CODE ###

import math
a,b,n=map(int,input().split())
max=-2
if n<b:
    max=math.floor(a*n/b)
else:
    #b<=n
    max=math.floor(a*(b-1)/b)
    

print(max)
### BUGGY CODE ###

N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]

for _ in range(Q):
    x, y = map(int, input().split())
    while len(queue) > 0 and (shortest_path[x] == 0 or shortest_path[y] == 0):
        v = queue.pop(0)
        shortest_path[v[0]] = v[1]
        queue += [[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]]
    print(shortest_path[x] + shortest_path[y])

### FIXED CODE ###

from collections import deque

N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x] + shortest_path[y])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 22 09:27:00 2020

@author: azikausy
"""


S = list(input())
Q = int(input())
Query = {}
#TFC = []
for i in range(0, Q):
    l = input().split()
    if len(l) == 1:
        #Query[i] = [l[0], 0, 0]
        S.reverse() 
    else:
        #Query[i] = l
        if l[1] == "2":
            S.append(l[2])
        else:
            S.insert(0, l[2])

ans = ""
for i in range(0, len(S)):
    ans = ans + S[i]
print(ans)

### FIXED CODE ###

from collections import deque
S = list(input())
Q = int(input())
perm = 0
d = deque(S)

for i in range(0, Q):
    l = input().split()
    if len(l) == 1:
        perm += 1
    else:
        if (int(l[1])+perm) % 2 == 0:
            d.append(l[2])
        else:
            d.appendleft(l[2])
 
S0 = list(d)
if perm % 2 != 0:
    S0.reverse()
ans = ""
for i in range(0, len(S0)):
    ans = ans + S0[i]
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
S = str(input())

def inversion_command(l, r, s):
    s_l = s[:l]
    s_c = s[l:r]
    s_r = s[r:]
    
    s_c = s_c.replace('0', 'X')
    s_c = s_c.replace('1', '0')
    s_c = s_c.replace('X', '1')
    return s_l + s_c + s_r
    
#print(inversion_command(0, 3, S))

s_list = set([S])

for _ in range(K):
    tmp_s_list = set()
    for l in range(N + 1):
        for r in range(l, N + 1):
            for s in s_list:
                tmp_s_list.add(inversion_command(l, r, s))
    s_list = tmp_s_list

ans = 0
for s in s_list:
    s_split = s.split('0')
    s_len = [len(s) for s in s_split]
    s_max = max(s_len)
    #print(s_len)
    #print(s_max)
    ans = max(ans, s_max)
print(ans)
    





### FIXED CODE ###

N, K = map(int, input().split())
S = str(input())

import re

def nchars(s, n):
    """文字列 s に、同じ文字が n 個以上連続している部分文字列を見つける
    """
    assert n > 0
    reg = re.compile("(.)\\1{%d,}" % (n - 1))  # カンマを取ると n 個ちょうどになる
    while True:
        m = reg.search(s)
        if not m:
            break
        yield m.group(0)
        s = s[m.end():]

s_list = list(nchars(S, 1))
s_list_num = [len(s) for s in s_list]
if '1' in s_list[0]:
    s_list_num.insert(0,0)
else:
    s_list_num.insert(0,0)
    s_list_num.insert(0,0)


s_list_sum = []
tmp_sum = 0
for x in s_list_num:
    tmp_sum += x
    s_list_sum.append(tmp_sum)

#print(s_list)
#print(s_list_num)
#print(s_list_sum)

ans = 0
for i in range(1, len(s_list_sum),2):

    l_sum = s_list_sum[i-1]
    r_sum = s_list_sum[min(len(s_list_sum)-1, i+K*2)]
    #print(l_sum, r_sum)
    ans = max(ans, r_sum - l_sum)

print(ans)
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
A.sort()
ans = [0]*N
from bisect import *
lis = []
cum_max = N
for x,y,i in A:
  insort(lis,(y,i))
  if lis[-1][0]==cum_max and len(lis)==lis[-1][0]-lis[0][0]+1:
    for y1,i1 in lis:
      ans[i1] = len(lis)
    cum_max = lis[0][0]-1
    lis = []
print(*ans, sep='\n')


### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
    self.min_y = [N]*n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
    return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.min_y[x] = min(self.min_y[x],self.min_y[y])
    self.parents[y] = x

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
uf = UnionFind(N)
uf.min_y = [y for x,y,i in A]
ans = [1]*N
A.sort()
Y = [(i,y) for x,y,i in A]
from heapq import *
heap = []
for u,y in Y:
  atode = []
  for _ in range(len(heap)):
    y1,v = heappop(heap)
    if y<y1:
      heappush(heap,(y1,v))
      break
    uf.union(u,v)
    if uf.parents[v]<0:
      atode.append((uf.min_y[v],v))
  if uf.parents[u]<0:
    heappush(heap,(uf.min_y[u],u))
  for y1,v in atode:
    heappush(heap,(y1,v))
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')