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

import sys,math,copy
import numpy as np
input = sys.stdin.readline
S = [int(x) if x != '?' else -1 for x in input().strip()]
N = len(S)

dp_ = np.zeros((13), dtype=int)
dp_[0] = 1
mod = 1
for i, s in enumerate(S[::-1], start=1):
    dp = np.zeros((13), dtype=int)
    if s == -1:
        for d in range(10):
            m = (d * mod) % 13
            for pm in range(13):
                dp[(pm+m)%13] = (dp[(pm+m)%13] + dp_[pm]) % (10 ** 9 + 7)

    else:
        m = (s * mod) % 13
        for pm in range(13):
            dp[(pm+m)%13] = (dp[(pm+m)%13] + dp_[pm]) % (10 ** 9 + 7)
    dp_ = dp
    mod = (mod * 10) % 13
print(dp_[5] % (10 ** 9 + 7))

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = list(map(int, input().split()))
total = sum(A)
ans = []

from functools import lru_cache
@lru_cache(maxsize=None)
def rec(ind):
    if ind >= N:
        ind -= N
    return A[ind]*2

for i in range(N):
    t = 0
    for j in range(N//2):
        ind = i+1+j*2
        t += rec(ind)
    ans.append(total-t)
print(*ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
# 山1に降った量の半分をxと置くと、山2はA1-x、山3はA2-(A1-x)となり、翻って山1はA3-(A2-(A1-x))
# x = A3-A2+A1+x
# x = (A1+A3-A2) // 2
x = (sum(A[::2]) - sum(A[1::2])) // 2
ans = [x*2]
for i in range(N-1):
    a = A[i] - x
    ans.append(a*2)
    x = a
print(*ans)
### BUGGY CODE ###

import re
s = input()

count = 0
while 'ABC' in s:
    s = s.replace('ABC', 'BCA', 1)
    count += 1
print(count)

### FIXED CODE ###

s = input()

s = s.replace('BC', 'D')
a_count = 0
count = 0
for c in s:
    if c == 'A':
        a_count += 1
    elif c == 'D':
        count += a_count
    else:
        a_count = 0

print(count)
### BUGGY CODE ###

n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = []
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      pool.append(ab[here][1])
      here += 1
    else:
      break
  pool.sort()
  try:
    ans += pool[-1]
    del pool[-1]
  except:
    pass
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
ab = []
for i in range(n):
  a,b = map(int,input().split())
  ab.append([-a,b])
ab.sort()
ab.reverse()
#print(ab)
here = 0
ans = 0
pool = []
import heapq
for i in range(m+1):
  while True:
    if here == n:
      break
    elif ab[here][0] == -i:
      heapq.heappush(pool,-ab[here][1])
      here += 1
    else:
      break
  try:
    #print(pool)
    ans -= heapq.heappop(pool)
    #print(pool)
  except:
    pass
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1):
            for i in range(N+1):
                if i > 0:
                    dp[i][j][k] += (dp[i-1][j][k] + (N / (i+j+k))) * (i / (i+j+k))
                if j > 0 and i < N:
                    dp[i][j][k] += (dp[i+1][j-1][k] + (N / (i+j+k))) * (j / (i+j+k))
                if k > 0 and j < N:
                    dp[i][j][k] += (dp[i][j+1][k-1] + (N / (i+j+k))) * (k / (i+j+k))
    print(dp[cnt[0]][cnt[1]][cnt[2]])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0.] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1-k):
            for i in range(N+1-j-k):
                ijk = float(i + j + k)
                if ijk == 0:
                    continue
                x = N / ijk
                tmp = 0
                if i > 0:
                    tmp += (dp[i-1][j][k] + x) * (i / ijk)
                if j > 0 and i < N:
                    tmp += (dp[i+1][j-1][k] + x) * (j / ijk)
                if k > 0 and j < N:
                    tmp += (dp[i][j+1][k-1] + x) * (k / ijk)
                dp[i][j][k] = tmp
    print(dp[cnt[0]][cnt[1]][cnt[2]])


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

n,m=map(int,input().split())
l=[[] for _ in range(n)]
d=list()

for i in range(m):
  p,q=map(int,input().split())
  l[p-1].append(q)
  d.append([p,q])
 
for i in range(n):
  if len(l[i])>0:
    l[i].sort()

for i in range(m):
  print(str(d[i][0]).zfill(6)+str(l[d[i][0]-1].index(d[i][1])+1).zfill(6))


### FIXED CODE ###

import bisect

n,m=map(int,input().split())
l=[[] for _ in range(n)]
d=list()

for i in range(m):
  p,q=map(int,input().split())
  l[p-1].append(q)
  d.append([p-1,q])
 
for i in range(n):
  if len(l[i])>0:
    l[i].sort()

for i in range(m):
  o = bisect.bisect_left(l[d[i][0]], d[i][1])+1
  print(str(d[i][0]+1).zfill(6)+str(o).zfill(6))
### BUGGY CODE ###

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

cnt=0

for i in range(n):
    if i == 0:
        cnt += 1
    else:
      if min(p[:i+1]) == p[i]:
          cnt += 1
      else:
        continue

print(cnt)


### FIXED CODE ###

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

min=p[0]
cnt=0

for i in range(n):
    if min >= p[i]:
        cnt+=1
        min=p[i]
    else:
        continue
print(cnt)
### BUGGY CODE ###

def myAnswer(N:int,A:list) -> int:
   ans = []
   for a in A:
      if(a in ans):
         ans.remove(a)
      else:
         ans.append(a)
   return len(ans)

def modelAnswer():
   return
def main():
   N = int(input())
   A = [int(input()) for _ in range(N)]
   print(myAnswer(N,A[:]))
if __name__ == '__main__':
   main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
ans=dict()
cnt=0

for _ in range(N):
    A=int(input())
    if((A in ans)==False):
        ans[A]=1
    else:
        ans[A]+=1

for value in ans.values():
    if(value%2==1):
        cnt+=1

print(cnt)
### BUGGY CODE ###


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

G1 = []
G2 = []
G3 = []
a = int(0)

for i in range(N):
    for j in range(N):
        if (i + j) % 3 ==2:
            G1.append(c[i][j])
        elif (i + j) % 3 == 0:
            G2.append(c[i][j])
        else:
            G3.append(c[i][j])
ans_candi = []

for i1 in range(C):
    for i2 in range(C):
        for i3 in range(C):
            t = int(0)
            if i1!=i2 and i2!=i3 and i3!=i1:
                for j in G1:
                    t += D[j-1][i1]
                for j in G2:
                    t += D[j-1][i2]
                for j in G3:
                    t += D[j-1][i3]
                ans_candi.append(t)


print(min(ans_candi))


### FIXED CODE ###


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

G1 = [0]*C
G2 = [0]*C
G3 = [0]*C
a = int(0)

for i in range(N):
    for j in range(N):
        if (i + j) % 3 ==2:
            G1[c[i][j]-1] += 1
        elif (i + j) % 3 == 0:
            G2[c[i][j]-1] += 1
        else:
            G3[c[i][j]-1] += 1
ans_candi = []


for i1 in range(C):
    for i2 in range(C):
        for i3 in range(C):
            t = int(0)
            if i1!=i2 and i2!=i3 and i3!=i1:
                for j in range(C):
                    t += D[j][i1]*G1[j]
                for j in range(C):
                    t += D[j][i2]*G2[j]
                for j in range(C):
                    t += D[j][i3]*G3[j]
                ans_candi.append(t)


print(min(ans_candi))
### BUGGY CODE ###

MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

dp=[[0]*13]
for i in range(len(s)):
    dp.append([0]*13)

dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]
    for k in range(13):
        dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5])

### FIXED CODE ###

MOD = 10**9+7
s = input()
ind = list(range(len(s)))
sl = list(s)
#print(sl)
dsl = dict(zip(ind, sl))
#print(dsl)

ind2 = list(range(13))
dp={}
#dp.setdefault(0, dict(zip(ind2,[0]*13)))
for i in range(len(s)+1):
    #dp.append(dict(zip(ind2,[0]*13)))
    dp.setdefault(i, dict(zip(ind2,[0]*13)))


#print(dp)
dp[0][0]=1

for i in range(len(s)):
    for k in range(10):
        if dsl[i] != "?" and dsl[i] != str(k):
            continue
        for j in range(13):
            dp[i+1][(j*10+k)%13] += dp[i][j]%MOD
    #for k in range(13):
    #    dp[i+1][k] %= MOD

#print(dp)
print(dp[len(s)][5]%MOD)
### BUGGY CODE ###

from scipy.sparse import*
i=lambda:tuple(map(int,input().split()))
f=csgraph.dijkstra
n,m,l=i()
d=eval('[0]*-~n,'*-~n)
exec('a,b,c=i();d[a][b]=c;'*m)
d=f(f(d,0)<=l)
d[d>n]=0
for _ in'_'*i()[0]:print(int(d[i()])-1)

### FIXED CODE ###

from scipy.sparse import*
s=csgraph.floyd_warshall
n,m,l,*t=map(int,open(0).read().split())
d=eval('[9e9]*-~n,'*-~n)
for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=d[b][a]=c
d=s(d)
d[d>l]=9e9
d[d<=l]=1
d=s(d)
d[d>9e9]=9e9
for s,t in zip(*[iter(t[m*3+1:])]*2):print(int(d[s,t]%9e9-1))
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())
A = [[] for _ in range(H)]
inf = 1000000007
for i in range(H):
    A[i] = list(input())
    for j in range(W):
        if A[i][j] == '.':
            A[i][j] = inf
        elif A[i][j] == '#':
            A[i][j] = 0

#print(A)

for i in range(H):
    for j in range(1, W):
        A[i][j] = min(A[i][j-1]+1, A[i][j])

#print(A)


for i in range(H):
    for j in range(W-2, -1, -1):
        A[i][j] = min(A[i][j+1]+1, A[i][j])

#print(A)

for i in range(1, H):
    for j in range(0, W):
        A[i][j] = min(A[i-1][j]+1, A[i][j])

#print(A)

for i in range(H-2, -1, -1):
    for j in range(W):
        A[i][j] = min(A[i+1][j]+1, A[i][j])

#print(A)

ans_list = []

for i in range(H):
    ans_list.append(max(A[i]))

print(max(ans_list))

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
A = [[] for _ in range(H)]
inf = 10 ** 7
for i in range(H):
    A[i] = list(input())
    for j in range(W):
        if A[i][j] == '.':
            A[i][j] = inf
        elif A[i][j] == '#':
            A[i][j] = 0

A = np.array(A)

#print(A)

for j in range(1, W):
    A[:,j] = np.minimum(A[:,j-1]+1, A[:,j])

#print(A)
for j in range(W-2, -1, -1):
    A[:,j] = np.minimum(A[:,j+1]+1, A[:,j])

#print(A)

for i in range(1, H):
    A[i,:] = np.minimum(A[i-1,:]+1, A[i,:])

#print(A)

for i in range(H-2, -1, -1):
     A[i,:] = np.minimum(A[i+1,:]+1, A[i,:])

#print(A)


ans = np.max(A)

#for i in range(H):
#    ans_list.append(max(A[i]))

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

import sys
X = list(sys.stdin.readline().strip())
N = len(X)

def solve():
    cnt = 0
    i = 0
    while True:
        while i < N and X[i] != 'S':
            i += 1
        j = i
        while j < N and X[j] != 'T':
            j += 1
        if j == N:
            return N - 2*cnt
        cnt += 1
        X[i] = ' '
        X[j] = ' '

print(solve())

### FIXED CODE ###

X = list(input())
N = len(X)
NHALF = N // 2

def solve():
    nt, ns = 0, 0
    for i in range(N):
        if X[i] == 'S':
            ns += 1
        elif ns > 0:
            ns -= 1
        else:
            nt += 1
    return nt + ns


print(solve())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N = int(input())
A = [int(a) for a in input().split()]

dpmax = [[0]*N for _ in range(N)]
dpmin = [[0]*N for _ in range(N)]
        
def f(i, j, t):
    if i > j or i < 0 or i >= N or j < 0 or j >= N:
        return 0
    
    if i == j:
        if t == 0:
            dpmin[i][j] = -A[i]
            return -A[i]
        if t == 1:
            dpmax[i][j] = A[i]
            return A[i]
        
    if t == 0 and dpmin[i][j] > 0:
        return dpmin[i][j]
    elif t == 1 and dpmax[i][j] > 0:
        return dpmax[i][j]
    
    if t == 0:
        dpmin[i][j] = min(-A[i]+f(i+1, j, 1), -A[j]+f(i, j-1, 1))
        return dpmin[i][j]
    else:
        dpmax[i][j] = max(A[i]+f(i+1, j, 0), A[j]+f(i, j-1, 0))
        return dpmax[i][j]

ans = f(0, N-1, 1)
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

dp = [[0]*N for _ in range(N)]
        
for k in range(N):
    for i in range(N-k):
        if k == 0:
            dp[i][i] = A[i]
            continue
    
        dp[i][i+k] = max(A[i]-dp[i+1][i+k], A[i+k]-dp[i][i+k-1])

print(dp[0][N-1])
### BUGGY CODE ###

n = input()
A=[]
for i in range(0,int(n)):
  a=input()
  A.append(int(a))

for i in range(0,int(n)):
  if ( sorted(A)[-1] == A[i]):
  	print (sorted(A)[-2])
  else:
    print(sorted(A)[-1])

### FIXED CODE ###

n = input()
A=[]
for i in range(0,int(n)):
  a=input()
  A.append(int(a))
B=[]
B =sorted(A)
  
for i in range(0,int(n)):
  if ( B[-1] == A[i]):
  	print (B[-2])
  else:
    print(B[-1])
### BUGGY CODE ###

#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())

#output
import numpy as np
import bisect as bi

X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]

answer = 0

for i in range(N):
    damage = np.zeros(N, int)
    if H[i] <= 0:
        continue
    else:
        damage[i] = ((H[i]-1+A)//A)*A
        a = bi.bisect_right(X, X[i]+2*D)
        if a <= N-1:
            damage[a] = -((H[i]-1+A)//A)*A
    damage = np.cumsum(damage)
    answer += (H[i]-1+A)//A
    H -= damage

print(answer)

### FIXED CODE ###

from sys import stdin
input = stdin.readline

#input
N, D, A = map(int, input().split())
X = [0]*N
H = [0]*N
for i in range(N):
    X[i], H[i] = map(int, input().split())
 
#output
import numpy as np
import bisect as bi
 
X = np.array(X)
H = np.array(H)
idx = np.argsort(X)
X = X[idx]
H = H[idx]
 
damage = np.zeros(N+1, int)
answer = 0
power = 0
for i in range(N):
    power -= damage[i]
    J = (H[i]-1+A)//A
    if J <= power:
        continue
    else:
        a = bi.bisect_right(X, X[i]+2*D)
        damage[a] += J - power
        answer += J-power
        power = J
 
print(answer)
### BUGGY CODE ###

from math import sqrt
N = int(input())

for n in range(1, N+1):
    count = 0
    for z in range(1, int(sqrt(n))):
        for y in range(1,z+1):
            for x in range(1, y+1):
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == n:
                    if len(set([x, y, z])) == 3:
                        count += 6
                    elif len(set([x, y, z])) == 2:
                        count += 3
                    elif len(set([x, y, z])) == 1:
                        count += 1
    print(count)


### FIXED CODE ###

from math import sqrt
N = int(input())
ans = [0] * (N+1)

for x in range(1, int(sqrt(N)) + 2):
    for y in range(1,int(sqrt(N)) + 2):
        for z in range(1, int(sqrt(N)) + 2):
            n = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n <= N:
                ans[n] += 1

for i in range(1, len(ans)):
    print(ans[i])
### BUGGY CODE ###

s = input()
t = input()
n = len(s)
p = n*(n-1)/2
i = 0
j = 1
k = 0
for _ in range(int(p)):
  if s[i] == s[j] and t[i] == t[j]:
    k = k + 1
  elif s[i] != s[j] and t[i] != t[j]:
    k = k + 1
  else:
    print('No')
    break
  j = j + 1
  if j == n:
    i = i + 1
    j = i + 1
if k == p:
  print('Yes')

### FIXED CODE ###

S=input()
T=input()
a=[None]*26
b=[None]*26
k=1
for i in range(26):
    for j in range(len(S)):
        if S[j]==chr(97+i):
            if a[i]==None:
                a[i]=T[j]
            else:
                if T[j]!=a[i]:
                    k=0
                    break
for i in range(26):
    for j in range(len(S)):
        if T[j]==chr(97+i):
            if b[i]==None:
                b[i]=S[j]
            else:
                if S[j]!=b[i]:
                    k=0
                    break
if k==1:print("Yes")
else:print("No")
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    for j in range(b):
        tmp = heapq.heappop(A_LIST)
        heapq.heappush(A_LIST, max(tmp, c))
print(sum(A_LIST))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print(sum(A_LIST))
### BUGGY CODE ###

from heapq import heappush, heappop, heapify
import math
def solve():
	n , k= map(int, input().strip().split())
	a= [(-int(x),1,int(x)) for x in input().strip().split()]
	heapify(a)
	for i in range(k):
		x,cnt,orig = heappop(a)
		if x == 1:
			return 1
		heappush(a,(-((orig+cnt)//(cnt+1)),cnt+1,orig))
	return -(heappop(a)[0])


print(solve())

### FIXED CODE ###

from heapq import heappush, heappop, heapify
import math
def check(a,mid,k):
	cnt = 0
	for x in a:
		cur_cnt = (x+mid-1)//mid - 1
		cnt+=cur_cnt
		if cnt > k:
			return False
	return True

def solve():
	n , k= map(int, input().strip().split())
	a= [int(x) for x in input().strip().split()]
	l = 0
	r = 10**9+20
	while r-l > 1:
		mid = (r+l)//2
		if check(a,mid,k):
			r = mid
		else:
			l = mid
	return l+1
 
print(solve())
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
d = [[0] * (H*W+1) for i in range(H*W+1)]

# 全ての数字に対応する座標を格納
matrix = [[] for i in range(H*W+1)]
for i in range(H):
    for j in range(W):
        matrix[A[i][j]] = (i, j)

#print(matrix)
for i in range(1, H*W+1):
    for j in range(i, H*W+1):
        if (j-i) % D != 0: continue
        if i == j:
            d[i][j] = 0
        else:
            f = matrix[j-D]
            to = matrix[j]
            d[i][j] = d[i][j-D] + abs(f[0]-to[0]) + abs(f[1]-to[1])
    for j in range(i-1,0,-1):
        if (j-i) % D != 0: continue
        f = matrix[j+D]
        to = matrix[j]
        d[i][j] = d[i][j-D] + abs(f[0]-to[0]) + abs(f[1]-to[1])

for i in range(Q):
    l, r = map(int, input().split())
    print(d[l][r])



### FIXED CODE ###

H, W, D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int,input().split())) for _ in range(Q)]

number_list = [[0] * 2 for _ in range(H*W+1)]
for h in range(H):
    for w in range(W):
        number_list[A[h][w]] = [h, w]

d = [0] * (H*W+1)
for idx in range(H*W+1):
    pre_idx = idx - D
    if pre_idx <= 0:
        continue
    diff = abs(number_list[idx][0] - number_list[pre_idx][0])
    diff += abs(number_list[idx][1] - number_list[pre_idx][1])
    d[idx] = d[pre_idx] + diff

for l, r in LR:
    cnt = 0
    print(d[r] - d[l])
### BUGGY CODE ###

import sys
import itertools

N, M, K = map(int, input().split())
A = list(map(int, sys.stdin.readline().rsplit()))
B = list(map(int, sys.stdin.readline().rsplit()))

sA = [0] + list(itertools.accumulate(A))
sB = [0] + list(itertools.accumulate(B))

res = 0
for i in range(N + 1):
    for j in range(M + 1):
        if sA[i] + sB[j] <= K:
            res = max(res, i + j)
        else:
            break

print(res)


### FIXED CODE ###

import sys
import itertools
import bisect

N, M, K = map(int, input().split())
A = list(map(int, sys.stdin.readline().rsplit()))
B = list(map(int, sys.stdin.readline().rsplit()))

sA = [0] + list(itertools.accumulate(A))
sB = [0] + list(itertools.accumulate(B))

res = 0
for i, a in enumerate(sA):
    if K < a:
        break
    j = bisect.bisect_right(sB, K - a) - 1
    res = max(res, i + j)

print(res)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[11]:


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


# In[12]:


x0 = 1
for i in range(K):
    x0 *= A[i]
x = x0
for j in range(K,N):
    score = x*A[j]//A[j-K]
    if score > x:
        print("Yes")
    else:
        print("No")
    x = score


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[2]:


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


# In[9]:


def main():
    for j in range(K,N):
        if A[j] > A[j-K]:
            print("Yes")
        else:
            print("No")


# In[10]:


if __name__ == '__main__':
    main()


# In[ ]:
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
ans1 = 0
for i in range(N -K +1):
  ans2 = sum(A[i:i+K])
  if ans2 > ans1:
    ans1 = ans2
    ans_list = A[i:i+K]
#print(ans_list)

ans = sum(map(lambda i:i/2+0.5,ans_list))


print(ans)
  

### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,k=MI()
	p=LI()

	for i in range(n):
		p[i]=p[i]/2+0.5
	#print(p)

	ans=sum(p[:k])
	now=sum(p[:k])

	for i in range(n-k):
		now=now-p[i]+p[i+k]
		ans=max(ans,now)
	print(ans)















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

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 n*len(divisors)
n=int(input())
s=0
for i in range(1,n+1):
    s+=make_divisors(i)
print(s)

### FIXED CODE ###

import math
n=int(input())
s=0
for i in range(1,n+1):
    s+=i*((math.floor(n/i)*math.floor(n/i+1))/2)
print (int(s))
### BUGGY CODE ###

import itertools
X=int(input())
l=[100,101,102,103,104,105]
for i in range(1,X//100+1):
  for v in itertools.combinations_with_replacement(l,i):
    if sum(v)==X:
      print(1)
      exit()
print(0)

### FIXED CODE ###

N=int(input())
n=N//100
if n>0:
  m=N%100
  if m/n<=5:
    print(1)
  else:
    print(0)
else:
    print(0)