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

import bisect

n,m = map(int, input().split())
A = sorted(map(int, input().split()))

for _ in range(m):
  b,c = map(int, input().split())
  ind = bisect.bisect_left(A, c)
  A = A[:ind]+[c]*b+A[ind:]

print(sum(A[-n:]))

### FIXED CODE ###

n,m = map(int, input().split())
A = list(map(int, input().split()))
BC = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: -x[1])

add = []

for b,c in BC:
  add += [c]*b
  if len(add)>n:
    break
    
ans = sorted(A+add)    
print(sum(ans[-n:]))
### BUGGY CODE ###

n, m = map(int, input().split())
jobs = []
ans = 0
for i in range(n):
    a, b = map(int, input().split())
    jobs.append([a, b])
for i in range(1, m+1):
    today_income = [job[1] for job in jobs if job[0] <= i]
    if today_income:
        today_max_income = max(today_income)
        max_income_payment_day = [job[0] for job in jobs if job[1] == today_max_income]
        jobs.remove([max(max_income_payment_day), today_max_income])
        ans += today_max_income
print(ans)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
ab_list = [list(map(int, input().split())) for i in range(n)]
ab_list.sort()
idx = 0
q = []
ans = 0
for j in range(1, m+1):
    while idx < n:
        a, b = ab_list[idx]
        if a <= j:
            heapq.heappush(q, -b)
            idx += 1
        else:
            break
    if len(q) > 0:
        b = heapq.heappop(q)
        ans -= b
print(ans)
### BUGGY CODE ###

s = input()
K = int(input())
ans = []
for i in range(len(s)):
    for k in range(i+1, len(s)+1):
        ans.append(s[i:k])
ans = set(ans)
ans = list(ans)
ans.sort()
print(ans[K-1])

### FIXED CODE ###

s = input()
K = int(input())
head = [h for h in s]

head = set(head)
head = list(head)
head.sort()

cnt = 0
ans = []
idx = 0
while cnt < K:
    for i in range(len(s)):
        if s[i] == head[idx]:
            for k in range(i+1, min(len(s)+1, i+6)):
                ans.append(s[i:k])
        ans = set(ans)
        ans = list(ans)
        cnt = len(ans)
    idx += 1
ans = set(ans)
ans = list(ans)
ans.sort()
print(ans[K-1])
### BUGGY CODE ###

# coding: utf-8
def modpow(x, n, mod):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return modpow((x**2) % mod, n // 2, mod)
    else:
        return x * modpow(x, n - 1, mod) % mod
def modcomb(n, r, mod):
    "nCr = X/Yとおく"
    r = min(r, n - r)
    ue, sita = 1, 1
    for i in range(1, r + 1):
        ue *= (n + 1 - i) % mod
        sita *= i % mod
    # return ue * modpow(sita, mod-2, mod)
    return ue * pow(sita, mod-2, mod)

N, A, B = map(int, input().split())
mod = 10 ** 9 + 7

ans = pow(2, N, mod) - 1
ans -= modcomb(N, A, mod)
# ans -= cmb(N, A, mod) % mod
ans %= mod
ans -= modcomb(N, B, mod)
# ans -= cmb(N, B, mod) % mod
ans %= mod
print(ans % mod)

### FIXED CODE ###

# coding: utf-8
def modcomb(n, r, mod):
    "nCr = X/Yとおく"
    r = min(r, n - r)
    X, Y = 1, 1
    for i in range(1, r + 1):
        X = X * (n + 1 - i) % mod
        Y = Y * i % mod
    # return ue * modpow(sita, mod-2, mod)
    return X * pow(Y, mod-2, mod) % mod

N, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = pow(2, N, mod) - 1
a = modcomb(N, A, mod)
# ans %= mod
b = modcomb(N, B, mod)
ans -= a + b
print(ans % mod)
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 998244353
s = list()
for _ in range(k):
    l, r = map(int, input().split())
    s += range(l, r + 1)
s.sort()
dp = [0 for _ in range(n)]
dp[0] = 1
for i in range(n):
    for x in s:
        if x + i > n - 1:
            break
        dp[i + x] = (dp[i + x] + dp[i]) % mod

print(dp[-1])


### FIXED CODE ###

n, k = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(k)]
dp = [0 for _ in range(n + 1)]
dp[1] = 1
s = 0
mod = 998244353

for i in range(1, n + 1):
    s += dp[i]
    for l, r in LR:
        if i + l <= n:
            dp[i + l] = (dp[i + l] + s) % mod
            if i + r + 1 <= n:
                dp[i + r + 1] = (dp[i + r + 1] - s) % mod

print(dp[n])
### BUGGY CODE ###

N,K = map(int,input().split())
num = N
if N <= abs(N - K):
  print(N)
else:
  while N <= num:
    num = N
    N = abs(N - K)
  print(num)

### FIXED CODE ###

N,K = map(int,input().split())
ans1 = N % K
ans2 = abs(ans1 - K)
if ans1 <= ans2:
  print(ans1)
else:
  print(ans2)
### BUGGY CODE ###

import math
a,b=map(int,input().split())
c=list(map(int,input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
d=make_divisors(sum(c))


m=1
for i in d:
  d=[0 for i in range(a)]
  for j in range(a):
    d[j]=c[j]%i
  d.sort()
  for j in range(a):
    k=sum(d[:j]) 
    l=(a-j)*i-sum(d[j:])
    if k==l and k+l<=b*2:
      m=i
      break
print(m)


### FIXED CODE ###

import math
from itertools import accumulate
a,b=map(int,input().split())
c=list(map(int,input().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse = True)
    return divisors
d=make_divisors(sum(c))


m=1
for i in d:
  e=[]
  for j in range(a):
    e.append(c[j]%i)
  e.sort()
  acc_m = list(accumulate(e))
  e=[i-e[j] for j in range(a)]
  acc_p = list(accumulate(e))
  for j in range(a):
    k=acc_m[j]
    l=acc_p[-1]-acc_p[j]
    if k==l and k+l<=b*2:
      print(i)
      exit()
### BUGGY CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

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

ans = 1
for i in range(1, n):
    flag = True
    for j in range(i):
        if p[i] > p[j]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)


### FIXED CODE ###

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

ans = 1
min = p[0]
for i in range(1, n):
    if min > p[i]:
        min = p[i]
    if p[i] <= min:
        ans += 1

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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
import functools
INF = float("inf")

MOD = 1000000007  # type: int


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def LCM(a, b):
    return a*b//GCD(a, b)


def solve(N: int, A: "List[int]"):

    ans = 0
    # 最小公倍数
    lcm = 1
    for a in A:
        d, m = divmod(lcm, a)
        if m == 0:
            ans += d
            ans %= MOD
        else:
            ss = LCM(lcm, a)
            ans *= ss//lcm
            ans %= MOD
            lcm = ss
            ans += lcm//a
            ans %= MOD
    print(ans % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
import math
MOD = 1000000007  # type: int


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def div(a, b):
    return (a * power(b, MOD-2)) % MOD


def solve(N: int, A: "List[int]"):

    lcm = Counter()
    for a in A:
        c = factorial(a)
        for k in c:
            lcm[k] = max(c[k], lcm[k])
    # print(lcm)

    LCM = 1
    for k, v in lcm.items():
        LCM *= power(k, v)
        LCM %= MOD
    # print(LCM)

    tot = 0
    for a in A:
        tot += div(LCM, a)
    print(tot % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


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

H, N = map(int, input().split())
D = list(map(int, input().split()))

f = [1] + [0 for i in range(1, H+1)]
flag = 0
for i in range(N):
  for j in range(H-D[i], -1, -1):
    if f[j] == 1:
      f[j+D[i]] = 1
  if f[-1] == 1:
    print("Yes")
    flag = 1
    break
if flag == 0:
  print("No")

### FIXED CODE ###

H, N = map(int, input().split())
A = list(map(int, input().split()))
if sum(A) >= H:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())
h = list(map(int, input().split()))
ans = 0
for i in range(n):
    tmp = 0
    for j in range(i, n - 1):
        if h[j] < h[j + 1]:
            break
        tmp += 1
    ans = max(ans, tmp)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
h = list(map(int, input().split()))
ans = 0
tmp = 0
for i in range(n - 1):
    if h[i] < h[i + 1]:
        tmp = 0
    else:
        tmp += 1
    ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

import fractions
c=0
N=int(input())
L=list(map(int,input().split()))
a=L[0]
for i in range(N):
  a=(L[i]*a)//fractions.gcd(L[i], a)
for i in range(N):
  c=(c+(a//L[i]))%(10**9+7)
print(c)

### FIXED CODE ###

import fractions
c=0
N=int(input())
L=list(map(int,input().split()))
a=L[0]
for i in range(1,N):
  a=(L[i]*a)//fractions.gcd(L[i], a)
for i in range(N):
  c+=(a//L[i])
print(c%(10**9+7))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
a = []
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    inp = input()
    a.append(inp)
    for j in range(W):
        if inp[j] == "#":
            queue.append([i,j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
ans = 0
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] +1
            ans = max(dist[nh][nw], ans)
            queue.append([nh, nw])
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
a = []
for _ in range(H):
    a.append(input())
queue = deque([])
dist = [[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            queue.append([i,j])
            dist[i][j] = 0
dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]
while len(queue) != 0:
    now = queue.popleft()
    h = now[0]
    w = now[1]
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]
        if nh < 0 or nw < 0 or nh >= H or nw >= W:
            continue
        elif dist[nh][nw] == -1:
            dist[nh][nw] = dist[h][w] +1
            queue.append([nh, nw])
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dist[i][j])
print(ans)
### BUGGY CODE ###

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

A =[] 

for i in range(N):
  A.append([i+1,a[i]])


A.sort(key=lambda x: x[1], reverse=True)


dp = [[0] * (N+1) for i in [1] * (N+1)]


for i in range(N+1):
  for x in range(i+1):
    y = i - x
    if x == 0 and y == 0:
      dp[x][y] = 0
    
    elif x == 0:
      dp[x][y] = dp[x][y-1] + A[y-1][1]*((N-y+1) - (A[y-1][0]))


    elif y == 0:
      dp[x][y] = dp[x-1][y] + A[x-1][1]*((A[x-1][0]) - x )


    else:
      dp[x][y] = max(dp[x][y-1] + A[x+y-1][1]*((N-y+1) - (A[x+y-1][0])) , dp[x-1][y] + A[x+y-1][1]*((A[x+y-1][0]) - x ))

ans = 0
for x in range(N+1):
  y = N - x
  ans = max(ans,dp[x][y])
  
print(ans)

### FIXED CODE ###

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

A =[] 

for i in range(N):
  A.append([i+1,a[i]])


A.sort(key=lambda x: x[1], reverse=True)

dp = []
for i in range(N+1,-1,-1):
  dp.append([0] * (i+1))

for i in range(N+1):
  for x in range(i+1):
    y = i - x
    if x == 0 and y == 0:
      dp[x][y] = 0
    
    elif x == 0:
      dp[x][y] = dp[x][y-1] + A[y-1][1]*((N-y+1) - (A[y-1][0]))


    elif y == 0:
      dp[x][y] = dp[x-1][y] + A[x-1][1]*((A[x-1][0]) - x )


    else:
      dp[x][y] = max(dp[x][y-1] + A[x+y-1][1]*((N-y+1) - (A[x+y-1][0])) , dp[x-1][y] + A[x+y-1][1]*((A[x+y-1][0]) - x ))

ans = 0
for x in range(N+1):
  y = N - x
  ans = max(ans,dp[x][y])
  
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
count = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            count += gcd(a,b,c)
print(count)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

K = int(input())
count = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            d = gcd(a,b)
            count += gcd(c, d)
print(count)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))

    seen = [False] * (N+1)
    arr = [1]
    seen[1] = True
    while True:
        next = A[arr[-1]]
        if seen[next]:
            arr.append(next)
            break
        arr.append(next)
        seen[next] = True

    x = int(math.log2(K)) + 1
    dub = [[-1] * (N+1) for _ in range(x)]
    for idx, a in enumerate(arr[:-1]):
        dub[0][a] = arr[idx+1]
    for d in range(1,x):
        for k in range(1, N+1):
            tmp = dub[d - 1][k]
            if tmp == -1:continue
            dub[d][k] =  dub[d-1][tmp]

    ret = 1
    while K:
        d = int(math.log2(K))
        K -= 1 << d
        ret = dub[d][ret]
    print(ret)

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations, product
#import bisect# lower_bound etc
#import numpy as np
def run():
    N,K = map(int, sysread().split())
    A = [0] + list(map(int, sysread().split()))
    perm = [1]
    seen = [[-1, False] for _ in range(N+1)]
    seen[1] = [1,True]
    l = 1
    while True:
        v = perm[-1]
        idx, boo = seen[A[v]]
        if boo: break
        l += 1
        perm.append(A[v])
        seen[A[v]] = [l,True]

    if K <= idx -1:
        print(perm[K])
        return None
    K -= idx - 1
    perm = perm[idx-1:]
    print(perm[K % len(perm)])

if __name__ == "__main__":
    run()
### BUGGY CODE ###

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

Ls = [0] * M
Rs = [0] * M

for i in range(M):
    Ls[i], Rs[i] = list(map(int, input().split()))

count = 0
for i in range(N):
    judge = True
    for k in range(M):
        L = Ls[k]
        R = Rs[k]
        if not (L <= i + 1 <= R):
            judge = False
    if judge:
        count += 1
print(count)


### FIXED CODE ###

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

maxvL = 0
minvR = 1000000
for i in range(M):
    L, R = list(map(int, input().split()))
    if maxvL < L:
        maxvL = L
    if minvR > R:
        minvR = R

count = 0
for i in range(N):
    if maxvL <= i + 1 <= minvR:
        count += 1
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from itertools import product
from collections import deque
import numpy as np
class Grid():
    def __init__(self, grid, w=0, h=0, function=lambda x: x):
        self.w = w = w if w else len(grid[0])
        self.h = h = h if h else len(grid)
        dtype = type(function(grid[0][0]))
        self.grid = np.empty((h, w), dtype=dtype)
        for i, row in zip(range(h), grid):
            for j, val in zip(range(w), row):
                self.grid[i][j] = function(val)
    
    def is_valid_x(self, x):
        return 0 <= x < self.w
    def is_valid_y(self, y):
        return 0 <= y < self.h
    def is_valid_xy(self, x, y):
        return self.is_valid_x(x) and self.is_valid_y(y) 
    
    def __iter__(self):
        return iter(self.grid)
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.grid])
    def __getitem__(self, x):
        return self.grid[x]
    def __setitem__(self, x, val):
        self.grid[x] = val

X = iter(open(0).readlines())
h, w = map(int, next(X).split())
ch, cw = map(int, next(X).split())
dh, dw = map(int, next(X).split())
dp = Grid([x.strip() for x in X], function=lambda x: 10**6 if x == '.' else -1)

def dfs(stack):
    if not stack:
        return
    x, y, d = stack[0]
    dp[y, x] = d
    stack2 = []
    while stack:
        x, y, d = stack.pop()
        if dp[y, x] < d:
            continue
        for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+dx, y+dy
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d:
                dp[ny, nx] = d
                stack.append((nx, ny, d))
        for dx, dy in product(range(-2, 3), repeat=2):
            if abs(dx) + abs(dy) < 2:
                continue
            nx, ny = x+dx, y+dy                
            if dp.is_valid_xy(nx, ny) and dp[ny, nx] > d+1:
                dp[ny, nx] = d+1
                stack2.append((nx, ny, d+1))
    dfs(stack2)

dfs([(cw-1, ch-1, 0)])
if dp[dh-1, dw-1] == 10**6:
    print(-1)
else:
    print(dp[dh-1, dw-1])

### FIXED CODE ###

from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])
### BUGGY CODE ###

from itertools import*
n,k=map(int,input().split())
s=input()
t=[0]*(s[0]=="0")+[len(list(g)) for _,g in groupby(s)]+[0]*(s[-1]=="0"or(1-("1"in s)))
a,b=t[::2],t[1::2]
l=len(t)//2;k=min(k,l)
print(max(sum(a[i:i+k+1]+b[i:i+k])for i in range(l+1-k)))

### FIXED CODE ###

from itertools import*
n,k=map(int,input().split())
s=input()
t=[0]*(s[0]=="0")+[len(list(g)) for _,g in groupby(s)]+[0]*(s[-1]=="0"or(1-("1"in s)))
a,b=t[::2],t[1::2]
l=len(t)//2;k=min(k,l)
t=r=sum(a[:k+1]+b[:k]) 
for w,x,y,z in zip(a,b,a[k+1:],b[k:]):
	t+=-w-x+y+z
	r=max(r,t)
print(r)
### BUGGY CODE ###

import sys 
try:
    sys.stdin = open('input.txt', 'r') 
    sys.stdout = open('output.txt', 'w')
except:
    pass

input = sys.stdin.readline
ht,st,ha,sa = map(int,input().split())
while True:
	ha -= st
	ht -= sa
	if ha==0 or ht==0:
		break
print("Yes") if ha==0 else print("No")
	



### FIXED CODE ###

import sys 
import math
try:
    sys.stdin = open('input.txt', 'r') 
    sys.stdout = open('output.txt', 'w')
except:
    pass

input = sys.stdin.readline
ht,st,ha,sa = map(int,input().split())
t = math.ceil(ht/sa)
a = math.ceil(ha/st)
if t>=a:
	print("Yes")
else:
	print("No")
### BUGGY CODE ###

#X = int(input())
#S = str(input())
N, K= map(int, input().split())
A = list(map(int, input().split()))

start = 1
for i in range(K):
  start *= A[i]
  
now = start    
for i in range(N - K):
  now *= A[K + i]
  now /= A[i]
  #print(start, now)
  if now > start:
    print("Yes")
  else:
    print("No")
  start = now
  
  

### FIXED CODE ###

#X = int(input())
#S = str(input())
N, K= map(int, input().split())
A = list(map(int, input().split()))
  
for i in range(N - K):
  #print(start, now)
  if A[K + i] > A[i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

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

p = [(n+1)/2 for n in p]
#import numpy as np
#s = np.cumsum(p)

max_e=0
for i in range(N-(K-1)):
  v=p[i:K+i]
  smax=sum(v)
  #e=(K+smax)/2

  max_e = max(max_e, smax)
    
print(max_e)

### FIXED CODE ###

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

p = [(n+1)/2 for n in p]
import numpy as np
s = np.cumsum(p)

e=s[K-1]
max_e=e
for i in range(1,N-K):
  e=s[i+K]-s[i]
  max_e = max(max_e, e)
    
print(max_e)