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

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

    for _ in range(k):
        imos = [0 for _ in range(n)]

        for i, ai in enumerate(a):
            imos[max(0, i - ai)] += 1
            if i + ai + 1 < n:
                imos[i + ai + 1] -= 1

        val = 0
        for i, im in enumerate(imos):
            val += im
            a[i] = min(val, n)

        if min(a) == n:
            break

    print(*a, sep=" ")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue
# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, k = ns()
    a = na()

    for _ in range(min(k,42)):
        imos = [0 for _ in range(n)]

        for i, ai in enumerate(a):
            imos[max(0, i - ai)] += 1
            if i + ai + 1 < n:
                imos[i + ai + 1] -= 1

        val = 0
        for i, im in enumerate(imos):
            val += im
            a[i] = min(val, n)

        # if min(a) == n:
        #     break

    print(*a, sep=" ")


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

#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()
            if not group[node]:
                group[node] = count
    

            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
                else:
                    if abs(group[next_node]-group[node]) == 1:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))

    print(answer)

    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
    S = [next(tokens) for _ in range(N)]  # type: "List[int]"
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**5]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


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

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

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

N = int(input())
s = []
count=0

for i in range(N):
  a = list(input())
  a.sort()
  s.append(''.join(a))
  
duplicate_list =sorted(set(s), key=s.index)

for i in range (len(duplicate_list)):
  for j in range (s.count(duplicate_list[i])):
    count += j

print(count)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
s = defaultdict(lambda:0)
count=0

for i in range(N):
  a = "".join(sorted(input()))
  s[a] +=1
  
  if s[a] >1:
    count += s[a]-1
print(count)
### BUGGY CODE ###

"""1, 2, 3, 4, 5, 6, 7, 8, 9, 
10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99, 
100, 101, 110, 111, 112, 121, 122, 123, 210, 211, 212, 221, 222, 223, 232, 233, 234, 321, 322, 323, 33

1 -> 10,11,12 -> 100,101 ,110,111,112, 121,122,123

2 -> 21,22,23 -> 210,211,212, 221,222,223, 232,233,234"""
def main():
    n = int(input())
    queue = [i for i in range(1,10)]
    while True:
        if n <= 1:
            print(queue[0])
            return
        tmp = queue.pop(0)
        n -= 1
        if tmp%10 != 0:
            queue.append(tmp*10 + tmp%10 - 1)
        queue.append(tmp*10 + tmp%10)
        if tmp%10 != 9:
            queue.append(tmp*10 + tmp%10 + 1)
            
main()

### FIXED CODE ###

"""1, 2, 3, 4, 5, 6, 7, 8, 9, 
10, 11, 12, 21, 22, 23, 32, 33, 34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99, 
100, 101, 110, 111, 112, 121, 122, 123, 210, 211, 212, 221, 222, 223, 232, 233, 234, 321, 322, 323, 33

1 -> 10,11,12 -> 100,101 ,110,111,112, 121,122,123

2 -> 21,22,23 -> 210,211,212, 221,222,223, 232,233,234"""
def main():
    n = int(input())
    
    queue = [i for i in range(1,10)]
    if n < 10:
        print(queue[n-1])
        return
    n -= 9
    while True:
        if n <= 0:
            print(queue[n-1])
            return
        tmp = queue.pop(0)
        if tmp%10 == 0:
            queue += [tmp*10 + tmp%10, tmp*10 + tmp%10 + 1]
            n -= 2
        elif tmp%10 == 9:
            queue += [tmp*10 + tmp%10 - 1, tmp*10 + tmp%10]
            n -= 2
        else:
            queue += [tmp*10 + tmp%10 - 1, tmp*10 + tmp%10, tmp*10 + tmp%10 + 1]
            n -= 3

main()
### BUGGY CODE ###

from heapq import heappush,heappop,heapify
INF=10**18

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]
def same(a,b):
    return find(a)==find(b)

def dijkstra(G,s,g,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        if(u==g):
            return dist
        if(G[u]):
            for c,v in G[u]:
                if(dist[u]+c<dist[v]):
                    dist[v]=dist[u]+c
                    heappush(que,(dist[v],v))
    return dist

N=int(input())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

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

G=[[] for i in range(N)]
Edges=[]
for i in range(N):
    for j in range(N):
        if(i==j):
            continue
        Edges.append([A[i][j],i,j])
heapify(Edges)

res=0
while Edges:
    cost,fr,to=heappop(Edges)
    if not same(fr,to):
        union(fr,to)
        G[fr].append((cost,to))
        G[to].append((cost,fr))
        res+=cost
    else:
        di=dijkstra(G,fr,to,N)
        if di[to]<A[fr][to]:
            print(-1)
            exit()
        if di[to]>cost:
            G[fr].append((cost,to))
            G[to].append((cost,fr))
            res+=cost
print(res)

### FIXED CODE ###

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
res=0
flag=[[False]*N for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
            elif k!=i and k!=j and A[i][j]==A[i][k]+A[k][j] and not flag[i][j] and not flag[j][i]:
                flag[i][j]=True
                flag[j][i]=True
                res-=A[i][j]
ans=sum(sum(A[i]) for i in range(N))//2+res

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

N, P = map(int, input().split())
S = list(input())

if P != 2 and P != 5:
    count = [0] * P
    ans = 0
    tmp = 0
    for i in range(N - 1, -1, -1):
        tmp += int(S[i]) * 10 ** (N - 1 - i)
        tmp %= P
        ans += count[tmp]
        count[tmp] += 1
    ans += count[0]

    # print (count)
    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)

### FIXED CODE ###

N, P = map(int, input().split())
S = list(input())

if P != 2 and P != 5:
    count = [0] * P
    ans = 0
    tmp = 0
    for i in range(N - 1, -1, -1):
        tmp += int(S[i]) * pow(10, (N - 1 - i), P)
        tmp %= P
        ans += count[tmp]
        count[tmp] += 1
    ans += count[0]

    # print (count)
    print (ans)

if P == 2:
    count = 0
    for index, s in enumerate(S):
        if int(s) % 2 == 0:
            count += (index + 1)
    print (count)

if P == 5: 
    count = 0
    for index, s in enumerate(S):
        if int(s) % 5 == 0:
            count += (index + 1)
    print (count)
### BUGGY CODE ###

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

check = True
for i in range(N):
  if A.count(A[i]) > 1:
    check = False
    
print("YES" if check else "NO")

### FIXED CODE ###

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

check = True
for i in range(N-1):
  if A[i] == A[i+1]:
    check = False
    
print("YES" if check else "NO")
### BUGGY CODE ###

# coding: utf-8
# Your code here!


H, W = map(int, input().rstrip().split(' '))

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        if s == '.':
            temp_field.append(0)
        else:
            temp_field.append(1)
    field.append(temp_field)

dp = [[H + W] * W for _ in range(H)]
dp2 = [[False] * W for _ in range(H)]
lists = []
for i in range(H):
    for j in range(W):
        if field[i][j] == 1:
            dp[i][j] = 0
            dp2[i][j] = True
            if i > 0:
                lists.append([i-1, j])
            if i < H - 1:
                lists.append([i+1, j])
            if j > 0:
                lists.append([i, j-1])
            if j < W - 1:
                lists.append([i, j+1])
           
count = 0
while True:
    if len(lists) == 0:
        break
    
    i, j = lists.pop(0)
    if dp2[i][j] == True:
        continue
    else:
        dp2[i][j] = True
        
        min_dist = H + W
        if i > 0:
            min_dist = min(min_dist, dp[i-1][j] + 1)
            if dp2[i-1][j] == False:
                lists.append([i-1, j])
        if i < H - 1:
            min_dist = min(min_dist, dp[i+1][j] + 1)
            if dp2[i+1][j] == False:
                lists.append([i+1, j])
        if j > 0:
            min_dist = min(min_dist, dp[i][j-1] + 1)
            if dp2[i][j-1] == False:
                lists.append([i, j-1])
        if j < W - 1:
            min_dist = min(min_dist, dp[i][j+1] + 1)
            if dp2[i][j+1] == False:
                lists.append([i, j+1])
            
        dp[i][j] = min_dist
        
print(max([max(temp_dp) for temp_dp in dp]))

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import deque

H, W = map(int, input().rstrip().split(' '))

field = [[0] * W for _ in range(H)]
d = deque()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            field[i][j] = 1
            d.append([i, j, 0])

max_dist = 0
while len(d) > 0:
    cur_h, cur_w, dist = d.popleft()
    for i, (dh, dw) in enumerate([[0, 1], [0, -1], [1, 0], [-1, 0]]):
        if (cur_h + dh) >= 0 and (cur_h + dh) < H and (cur_w + dw) >= 0 and (cur_w + dw) < W:
            if field[cur_h+dh][cur_w+dw] == 0:
                field[cur_h+dh][cur_w+dw] = 1
                d.append([cur_h+dh, cur_w+dw, dist+1])
                max_dist = max(max_dist, dist+1)

print(max_dist)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def is_prime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

def make(n):
    ans=[]
    for i in range(2,n+1):
        if is_prime(i):
            ans.append(i)
    return ans

if __name__ == '__main__':
    Q=int(input())
    Queries=[list(map(int,input().split())) for i in range(Q)]
    upper=max(Queries,key=lambda x:x[1])
    p_list=make(upper[1])

    for l,r in Queries:
        temp=[i for i in p_list if l<=i<=r and is_prime((i+1)//2)]
        if l!=1:
            print(len(temp))
        if l==1:
            print(len(temp)-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline

def Eratosthenes():
    num=[True for i in range(100001)]
    num[0]=False
    num[1]=False
    for i in range(2,100001):
        if num[i]:
            for j in range(2*i,100001,i):
                num[j]=False
    return num

if __name__ == '__main__':
    Q=int(input())
    Queries=[list(map(int,input().split())) for i in range(Q)]
    p_list=Eratosthenes()
    dp=[0 for _ in range(100001)]
    for i in range(3,100000):
        if p_list[i] and p_list[(i+1)//2]:
            dp[i+1]=dp[i]+1
        else:
            dp[i+1] = dp[i]
    for l,r in Queries:
        print(dp[r+1]-dp[l])
### BUGGY CODE ###

def search(x, num):
    search_set = set()
    for y in edge[x]:
        if y in nodes:
            nodes.remove(y)
            search_set.add(y)
    for y in search_set:
        num = search(y, num+1)
    return num
        


(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = list(range(1,n+1))
ans = 1
for x in range(1,n+1):
    if x not in nodes:
        continue
    tmp = search(x, 0)
    ans = max(tmp, ans)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e6))

def search(x, num):
    nodes.remove(x)
#     for y in edge[x]:
#         edge[y].discard(x)
#     for y in list(edge[x]):
    for y in edge[x]:
        if y in nodes:
            num = search(y, num)
    return num + 1

(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x in nodes:
        ans = max(ans, search(x, 0))
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
Edge = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    Edge[l-1].append((r-1, d))
    Edge[r-1].append((l-1, -d))
Left = [int(i) for i in range(N)]
Visit = [False for i in range(N)]
Node = [0 for i in range(N)]
Possible = True

while Left and Possible:
    start = Left.pop(0)
    Visit[start] = True
    Q = [start]
    while Q:
        now = Q.pop(0)
        for e in Edge[now]:
            if Visit[e[0]] == False:
                Visit[e[0]] = True
                Left.remove(e[0])
                Node[e[0]] = Node[now] + e[1]
                Q.append(e[0])
            elif e[0] != now:
                dest = Node[now] + e[1]
                if dest != Node[e[0]]:
                    Possible = False
                    break
print("Yes" if Possible else "No")


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
Inf = 10000000000
Edge = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, input().split())
    Edge[l-1].append((r-1, d))
    Edge[r-1].append((l-1, -d))
 
Node = [Inf for i in range(N)]
Possible = True
for i in range(N):
    if not Possible:
        break
    elif Node[i] == Inf:
        Node[i] = 0
        Q = deque([i])
        while Q:
            now = Q.popleft()
            for e in Edge[now]:
                if Node[e[0]] == Inf:
                    Node[e[0]] = Node[now] + e[1]
                    Q.append(e[0])
                elif Node[now] + e[1] != Node[e[0]]:
                    Possible = False
                    break
print("Yes" if Possible else "No")
### BUGGY CODE ###

a, b = map(int, input().split())

if a <= 0 <= b:
    print("Zero")
    exit()

minus = 0
for i in range(a, b+1):
    if i < 0:
        minus += 1

print("Positive" if minus % 2 == 0 else "Negative")

### FIXED CODE ###

a, b = map(int, input().split())

if a <= 0 <= b:
    print("Zero")
    exit()

if a < 0 and b < 0:
    print("Positive" if (b - a + 1) % 2 == 0 else "Negative")
    exit()

print("Positive")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import groupby
    s=input()
    G=groupby(s)
    A=[]
    for i,g in enumerate(G):
        key,iter=g
        if(i%2==0): a=len(list(iter))
        else: A.append((a,len(list(iter))))
    ans=[]
    for x,y in A:
        ans=ans+[0]*(x-1)
        ans.append((x-x//2)+(y//2))
        ans.append((x//2)+(y-y//2))
        ans=ans+[0]*(y-1)
    print(*ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import groupby
    s=input()
    n=len(s)
    G=groupby(s)
    A=[]
    for i,g in enumerate(G):
        key,iter=g
        if(i%2==0): a=len(list(iter))
        else: A.append((a,len(list(iter))))
    ans=[0]*n
    idx=-1
    for x,y in A:
        idx+=x
        ans[idx]=x-x//2+y//2
        ans[idx+1]=x//2+y-y//2
        idx+=y
    print(*ans)
resolve()
### BUGGY CODE ###

K = int(input())
S = input()

s = len(S)
mod = int(1e9+7)

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, K + s + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

n = 0

for i in range(s, K + s + 1):
    n += (pow(26,(K+s-i),mod)*pow(25,(i-s),mod)*(fact[i-1]*factinv[s-1]*factinv[i-s]))%mod


print(n%mod)

### FIXED CODE ###

K = int(input())
S = input()

s = len(S)
mod = int(1e9+7)


n = pow(26, K, mod)
ans = n

for i in range(K):
    n = n*25*(s+i)*pow(26*(i+1),-1,mod)%mod
    ans = (ans +n) % mod


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

N = int(input())
A = list(map(int, input().split()))
A.sort()
B = list(set(A))
ans = 0
n = len(B)
for i in range(n):
  b = B[i]
  c = A.count(b)
  if c < b:
    ans += c
  elif c > b:
    ans += c-b
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
old = A[0]
ans = 0
a = 1
for i in range(1, N):
  if A[i] == old: 
    a += 1
  else:
    if old > a:
      ans += a
    elif old < a:
      ans += a - old
    old = A[i]
    a = 1
if old > a:
  ans += a
elif old < a:
  ans += a - old
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
while N > 0:
    N -= K

if abs(N + K) > abs(N):
    print(abs(N))
elif abs(N + K) < abs (N):
    print(abs(N + K))
else:
    print(abs(N))

### FIXED CODE ###

N, K = map(int, input().split())
C = N // K

N -= K * (C)

if abs(N - K) > abs(N):
    print(abs(N))
elif abs(N - K) < abs (N):
    print(abs(N - K))
else:
    print(abs(N))
### BUGGY CODE ###

#%%
def search(x, y, z):
    return [[x-1, y, z+1], [x, y-1, z+1], [x, y+1, z+1], [x+1, y, z+1]]
    
h, w = map(int, input().split())
s = [[] for _ in range(h)]
for i in range(h):
    s[i] = list(input())

sharp = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            sharp += 1

check = [[0] * w for _ in range(h)]
que = [[0,0,1]]
check[0][0] == 1
flag = False

while len(que) > 0:
    tmp = que.pop(-1)
   #print(tmp)
    for i in search(tmp[0], tmp[1], tmp[2]):
        if 0 <= i[0] <= h-1 and 0 <= i[1] <= w-1 and s[i[0]][i[1]] == '.':
            if check[i[0]][i[1]] == 0:
                que.append(i)
                check[i[0]][i[1]] == 1
    if tmp[0] == h-1 and tmp[1] == w-1:
        key = tmp[2]
        flag = True
        break
#print(key)

if flag:
    print(h*w - sharp - key)
else:
    print(-1)
                



### FIXED CODE ###

#%%
def search(x, y, z):
    return [[x-1, y, z+1], [x, y-1, z+1], [x, y+1, z+1], [x+1, y, z+1]]
    
h, w = map(int, input().split())
s = [[] for _ in range(h)]
for i in range(h):
    s[i] = list(input())

sharp = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            sharp += 1

check = [[0] * w for _ in range(h)]
que = [[0,0,1]]
check[0][0] == 1
flag = False

while len(que) > 0:
    tmp = que.pop(0)
    #print(tmp)
    for i in search(tmp[0], tmp[1], tmp[2]):
        if 0 <= i[0] <= h-1 and 0 <= i[1] <= w-1 and s[i[0]][i[1]] == '.':
            if check[i[0]][i[1]] == 0:
                que.append(i)
                check[i[0]][i[1]] = 1
    if tmp[0] == h-1 and tmp[1] == w-1:
        key = tmp[2]
        flag = True
        break
#print(key)

if check[0][0] =='#':
    flag = False

if flag:
    print(h*w - sharp - key)
else:
    print(-1)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    def prime_factorize1(N):
        """
        Nをくって、Nの素因数を格納したリストresを返す。
        リストの要素をすべて掛ければNになる"""
        res = []
        x = N
        y = 2
        while y*y <= x:
            while x % y == 0:
                res.append(y)
                x //= y
            y += 1
        if x > 1:
            res.append(x)
        return res
    if n%2==1:
        print(0)
    elif n<10:
        print(0)
    else:
        ans=0
        for i in range(1,n//10+1):
            x=i*10
            from collections import Counter
            c=Counter(prime_factorize1(x))# ()にカウンターの対象のリストの変数名
            ans+=c[5]
        print(ans)
resolve()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    if n%2==1:
        print(0)
    elif n<10:
        print(0)
    else:
        ans=0
        for i in range(1,1000000):
            y=5**i
            num=(n//y)//2
            if num==0:
                break
            else:
                ans+=num
        print(ans)
resolve()
### BUGGY CODE ###

#n = int(input())
n,m,k = [int(z) for z in input().split()]
a = [int(z) for z in input().split()]
b = [int(z) for z in input().split()]
time = 0
x=[0]
y=[0]
#maX = -100000
num = 0
for i in range(n):
      x.append(x[i]+a[i])
for j in range(m):
      y.append(y[j]+b[j])

for i in range(n+1):
      if (x[i]>k):
            break
      for j in range(m+1):
            if (y[j]>k):
                  break
            z = x[i]+y[j]
            if (z<=k):
                  num = max(num,i+j)
                  
print(num)


### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N, M, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))


    nowtime = 0

    Asum = [0]
    Bsum = [0]
    tmp = 0
    for a in A:
        tmp += a
        Asum.append(tmp)
    tmp = 0
    for b in B:
        tmp += b
        Bsum.append(tmp)

    maxbooks = 0
    before = M
    bcount = M
    for acount in range(N+1):
        if Asum[acount] > K:
            continue
        while K < Asum[acount] + Bsum[bcount]:
            bcount -= 1
        maxbooks = max(maxbooks, acount+bcount)

    print(maxbooks)

if __name__ == '__main__':
    solve()