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

N, M = [int(nm) for nm in input().split()]
a1 = -1

import math
total_case = 1
for m in range(M+1):
  if m != M:
    a2 = int(input())
  else:
    a2 = N + 1
  safe_stairs = a2 - a1 - 1
  if safe_stairs == 0:
    print(0)
    break
  howmany_jump1 = safe_stairs - 1
  mx_jump2 = howmany_jump1 // 2
  #２のジャンプは０回～（mx_jump2）回
  case = 0
  for j2 in range(mx_jump2 + 1):
    jump2 = j2
    jump1 = howmany_jump1 - (j2 * 2)
    c = math.factorial(jump1 + jump2) // (math.factorial(jump1) * math.factorial(jump2))
    case += c
  total_case *= case
  a1 = a2
else:
  ans = total_case % (10**9 + 7)
  print(ans)

### FIXED CODE ###

N, M = [int(nm) for nm in input().split()]
if M != 0:
  a = int(input())

C = [1, 0] # [-2段目, -1段目]
C += [0]*(N+10) # C = [-2段目, -1段目, 0段目, 1段目, 2段目, ...]
for n in range(0, N+1):
  if M == 0:
    C[n+2] = (C[n] + C[n+1]) % 1000000007
  else: # M > 0:
    if n != a:
      C[n+2] = (C[n] + C[n+1]) % 1000000007
    else: # n == a:
      C[n+2] = 0
      M -= 1
      if M > 0:
        a = int(input())

ans = C[N+2]  % 1000000007
print(ans)
### BUGGY CODE ###

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

cnt = N
for i in range(N):
    for j in range(N):
        if i != j and A[i] % A[j] == 0:
            cnt -= 1
            break

print(cnt)


### FIXED CODE ###

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

ans = [False] * (Amax + 1)
for x in A:
    for j in range(x, Amax + 1, x):
        ans[j] += 1

print(sum(ans[i] == 1 for i in A))
### BUGGY CODE ###

#B
T=input()
L=["" for i in range(len(T))]
for i in range(len(T)):   
    if T[i]=="?":
        L[i]="D"
    else:
        L[i]=T[i]

ans=""
for i in L:
    ans+=i
print(ans)

### FIXED CODE ###

#B
T=input()
ans=T.replace("?", "D")
 
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import math 

def is_loadable(load, num_truck, w_list):

    excess = load*num_truck - sum(w_list)
    #print('Minimum Load:', load, num_truck, 'excess:', excess)
    cur_load = 0
    #truck_load = list()
    for w in w_list:
        #print(cur_load, w)
        if cur_load + w < load:
            cur_load += w
        elif cur_load + w == load:
            #truck_load.append(cur_load + w)
            cur_load = 0
            num_truck -= 1
            if num_truck < 0:
                return False
        else:
            num_truck -= 1
            if num_truck < 0:
                return False
            excess += load - cur_load
            if excess < 0:
                return False
            #print(cur_load, 'is added')
            #truck_load.append(cur_load)
            cur_load = w

    #truck_load.append(cur_load)
    if (cur_load and num_truck == 0):
        return False
    #print(truck_load)
    return True

n, num_truck = map(int, sys.stdin.readline().split())

weight = list()
for i in range(n):
    weight.append(int(sys.stdin.readline()))

ave_w = sum(weight) / num_truck
max_w = max(weight)
load = max(max_w, math.ceil(ave_w))

while True:
    if is_loadable(load, num_truck, weight):
        break
    load += 1

print(load)



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import math 

def is_loadable(load, num_truck, w_list):

    excess = load*num_truck - sum(w_list)
    # print('Minimum Load:', load, num_truck, 'excess:', excess)
    cur_load = 0
    #truck_load = list()
    for w in w_list:
        #print(cur_load, w)
        if cur_load + w < load:
            cur_load += w
        elif cur_load + w == load:
            #truck_load.append(cur_load + w)
            cur_load = 0
            num_truck -= 1
            if num_truck < 0:
                return False
        else:
            num_truck -= 1
            if num_truck < 0:
                return False
            excess += load - cur_load
            if excess < 0:
                return False
            #print(cur_load, 'is added')
            #truck_load.append(cur_load)
            cur_load = w

    #truck_load.append(cur_load)
    if (cur_load and num_truck == 0):
        return False
    #print(truck_load)
    return True

n, num_truck = map(int, sys.stdin.readline().split())

weight = list()
for i in range(n):
    weight.append(int(sys.stdin.readline()))

ave_w = sum(weight) / num_truck
max_w = max(weight)
load = max(max_w, math.ceil(ave_w))
max_ng = load - 1

while True:
    if is_loadable(load, num_truck, weight):
        break
    min_ng = load
    load += 1024

min_ok = load
while True:
    if min_ok == max_ng + 1:
        break
    load = (max_ng + min_ok) // 2
    if is_loadable(load, num_truck, weight):
        min_ok = load
    else:
        max_ng = load

print(min_ok)
### BUGGY CODE ###

n,k=map(int,input().split())
A=[]
for i in range(n):
  A.append(int(input())-k)
AA,BB=[0]*(n+1),[0]*(n+1)
AA[-2]=A[-1]
BB[-2]=A[-1]
for i in reversed(range(n-1)):
  AA[i]=AA[i+1]+A[i]
  BB[i]=BB[i+1]+A[i]
BB.sort()
cur=1
D=dict()
D[BB[0]]=cur
for i in range(1,n+1):
  if BB[i]==BB[i-1]:
    continue
  else:
    cur+=1
    D[BB[i]]=cur
AAA=[0]*(n+1)
for i in range(n+1):
  AAA[i]=D[AA[i]]

import math
n_max=2*10**5
nn=int(math.log2(n_max))+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

ans=0
for i in range(n+1):
  ans+=i-bitsum(BIT,AAA[i]-1)
  bitadd(BIT,AAA[i],1)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
A=[]
for i in range(n):
  A.append(int(input())-k)
AA,BB=[0]*(n+1),[0]*(n+1)
AA[-2]=A[-1]
BB[-2]=A[-1]
for i in reversed(range(n-1)):
  AA[i]=AA[i+1]+A[i]
  BB[i]=BB[i+1]+A[i]
BB.sort()
cur=1
D=dict()
D[BB[0]]=cur
for i in range(1,n+1):
  if BB[i]==BB[i-1]:
    continue
  else:
    cur+=1
    D[BB[i]]=cur
AAA=[0]*(n+1)
for i in range(n+1):
  AAA[i]=D[AA[i]]

nn=18
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

ans=0
for i in range(n+1):
  ans+=i-bitsum(BIT,AAA[i]-1)
  bitadd(BIT,AAA[i],1)
print(ans)
### BUGGY CODE ###

import collections
from sys import stdin


def counter(num_arr):
    uniq_dict = {}
    for val in num_arr:
        uniq_dict[val] = uniq_dict.get(val, 0) + 1
    return uniq_dict


def get_result(data):
    N = data[0][0]
    A = data[1]
    uniq_cnt = counter(A)
    ans = {}
    for key in uniq_cnt.keys():
        tmp = uniq_cnt.copy()
        tmp[key] -= 1
        ans[key] = int(sum([val * (val-1) / 2 for val in tmp.values()]))

    for i in range(N):
        print(ans[A[i]])


if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    get_result(data)


### FIXED CODE ###

import collections
from sys import stdin

# # not AC
# def counter(num_arr):
#     uniq_dict = {}
#     for val in num_arr:
#         uniq_dict[val] = uniq_dict.get(val, 0) + 1
#     return uniq_dict


# def get_result(data):
#     N = data[0][0]
#     A = data[1]
#     uniq_cnt = counter(A)
#     ans = {}
#     for key in uniq_cnt.keys():
#         tmp = uniq_cnt.copy()
#         tmp[key] -= 1
#         ans[key] = int(sum([val * (val-1) / 2 for val in tmp.values()]))

#     for i in range(N):
#         print(ans[A[i]])

def get_result(data):
    N = data[0][0]
    A = data[1]
    uniq_cnt = collections.Counter(A)
    all_selection = 0
    for val in uniq_cnt.values():
        all_selection += int(val * (val-1) / 2)

    for i in range(N):
        print(all_selection - uniq_cnt[A[i]] + 1)


if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    get_result(data)
### BUGGY CODE ###

s=input()
dp=[[0]*13 for _ in range(len(s)+5)]
dp[0][0]=1
for i in range(len(s)):
    if s[i]=='?':
        c=-1
    else:
        c=int(s[i])
    
    for j in range(10):
        if c!=-1 and c!=j:
            continue
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
    for j in range(13):
        dp[i+1][j]%=(10**9+7)

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

### FIXED CODE ###

s=input()
dp=[[0]*13 for _ in range(len(s)+5)]
dp[0][0]=1
for i in range(len(s)):
    
    if s[i]!='?':  
        j=int(s[i])
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
            dp[i+1][(k*10+j)%13]%=(10**9+7)
    else:
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
                dp[i+1][(k*10+j)%13]%=(10**9+7)

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

a,n,m=list(map(int,input().split()))
count=0
for x in range(1,m+1):
    xl=[int(i) for i in list(str(x))]
    y=sum(xl)
    if x==(y+a)**n:count+=1
print(count)


### FIXED CODE ###

a,n,m=list(map(int,input().split()))
count=0
check_list=[]
i=0
if a==0:i=1
while (i+a)**n<m:
    check_list.append((i+a)**n)
    i+=1
for x in check_list:
    xl=[int(i) for i in list(str(x))]
    y=sum(xl)
    if x==(y+a)**n:count+=1
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

xcal = [[0]*n for i in range(1<<n)]
ycal = [[0]*n for i in range(1<<n)]

for i in range(1<<n):
    for j in range(n):
        xcal[i][j] = abs(l[j][0])
        ycal[i][j] = abs(l[j][1])
        for k in range(n):
            if (i>>k) & 1:
                xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
        
ans = [float("INF")]*(n+1)

for i in range(1<<n):
    count = 0
    for j in range(n):
        if i >> j & 1:
            count += 1
    j = i
    while j >= 0:
        j &= i
        cost = 0
        for k in range(n):
            if not (i>>k & 1):
                cost += min(xcal[j][k],ycal[i-j][k])*l[k][2]
        ans[count] = min(ans[count],cost)

for i in ans:
    print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]

    xcal = [[0]*n for i in range(1<<n)]
    ycal = [[0]*n for i in range(1<<n)]

    for i in range(1<<n):
        for j in range(n):
            xcal[i][j] = abs(l[j][0])
            ycal[i][j] = abs(l[j][1])
            for k in range(n):
                if (i>>k) & 1:
                    xcal[i][j] = min(xcal[i][j],abs(l[j][0]-l[k][0]))
                    ycal[i][j] = min(ycal[i][j],abs(l[j][1]-l[k][1]))
            xcal[i][j] *= l[j][2]
            ycal[i][j] *= l[j][2]
    ans = [float("INF")]*(n+1)

    for i in range(1<<n):
        count = 0
        for j in range(n):
            if i >> j & 1:
                count += 1
        j = i
        while j >= 0:
            j &= i
            cost = 0
            for k in range(n):
                if not (i>>k & 1):
                    cost += min(xcal[j][k],ycal[i-j][k])
                if cost > ans[count]:
                    break
            ans[count] = min(ans[count],cost)
            j -= 1

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    #w={s}
    w=deque([0,s])
    tmp=[0]*(n+1)
    n*=3
    ans=1
    while n:
        x=w.pop()
        if x==0:
            n-=1
            ans+=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if tmp[j]==0 or tmp[j]%3!=ans%3:
                    w.appendleft(j)
                    tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)

if __name__=="__main__":
    sol()


### FIXED CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    #tmp=[0]*(n+1)
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

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

n = int(input())
l = list(map(int,input().split()))
ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans += l[i]*l[j]
print(ans%1000000007)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
sum_n = [0]*n
sum_n[0] = l[0]
sumall = sum(l)
for i in range(1,n):
    sum_n[i] = sum_n[i-1] + l[i]
for i in range(n):
    ans += ((l[i]*(sumall-sum_n[i]))%1000000007)
print(ans%1000000007)
### BUGGY CODE ###

N, M = map(int,input().split())
A = []
B = []
for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        B.append(b)
    if b == N:
        A.append(a)
for a in A:
    if a in B:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')


### FIXED CODE ###

N, M = map(int, input().split())
A = set()
B = set()

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if A & B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

from functools import reduce
import math

num = int(input())
a = 1
sum = 0

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

def loopC(a, b, num):
  sum = 0
  for c in range(1, num + 1):
      ans = gcd(a, b, c)
      sum += ans
  return sum

def loopB(a, num):
  sum = 0
  for b in range(1, num + 1):
    ans = loopC(a, b, num)
    sum += ans
  return sum

for a in range(1, num + 1):
  ans = loopB(a, num)
  sum += ans

print(sum)

### FIXED CODE ###

import math

num = int(input())
sum = 0

for a in range(1, num + 1):
  for b in range(1, num + 1):
    gcd_ab = math.gcd(a, b)
    for c in range(1, num + 1):
      sum += math.gcd(gcd_ab, c)

print(sum)
### BUGGY CODE ###

s = input()
for _ in range(int(input())):
  t = input()
  if t == "1":
    s = s[::-1]
  else:
    t = t.split()
    if t[1] == "1":
      s = t[2] + s
    else:
      s += t[2]
print(s)

### FIXED CODE ###

S = input()
len_s = len(S)
rev = False
max_ = 2*10**5
index = max_ + len_s
rev_index = max_ - 1
s = ["." for _ in range(max_*2 + len_s)]
for i in range(len_s):
    s[max_+i] = S[i]
for _ in range(int(input())):
  t = input()
  if t == "1":
    rev = not rev
  else:
    t = t.split()
    if (t[1] == "1" and not rev) or (t[1] == "2" and rev):
      s[rev_index] = t[2]
      rev_index -= 1
    else:
      s[index] = t[2]
      index += 1
if rev:
  for i in range((max_ + max_ + len_s - 1), 0, -1):
    if s[i] != ".":
      print(s[i], end="")
else:
  for i in range((max_ + max_ + len_s)):
    if s[i] != ".":
      print(s[i], end="")
### BUGGY CODE ###

N=int(input())
S=input()
X=int(S,2)

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1

def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
ls2=[0 for i in range(bitcount+2)]
for i in range(1,bitcount+2):
  ls[i]=f(i)
  ls2[i]=ls2[ls[i]]+1

for i in range(N):
  if S[i]=='0':
    print(ls2[(X^(2**(N-1-i)))%(bitcount+1)]+1)
  else:
    if (X^(2**(N-1-i)))==0:
      print(0)
    else:
      print(ls2[(X^(2**(N-1-i)))%(bitcount-1)]+1)
  


### FIXED CODE ###

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

#Sのビット数
bitcount=0
for i in range(N):
  if S[i]=='1':
    bitcount+=1
bp=bitcount+1
bm=bitcount-1

lsp=[1 for i in range(N)]
for i in range(1,N):
  lsp[i]=(lsp[i-1]*2)%bp
lsp.reverse()
fXp=0
for i in range(N):
  if S[i]=='1':
    fXp=(fXp+lsp[i])%bp
    
if bm!=0:
  lsm=[1 for i in range(N)]
  for i in range(1,N):
    lsm[i]=(lsm[i-1]*2)%bm
  lsm.reverse()
  fXm=0
  for i in range(N):
    if S[i]=='1':
      fXm=(fXm+lsm[i])%bm


def f(n):
  c=0
  x=1
  while x<=n:
    if n&x>0:
      c+=1
    x*=2
  return n%c

ls=[0 for i in range(bitcount+2)]  
for i in range(1,bitcount+2):
  ls[i]=ls[f(i)]+1

for i in range(N):
  if S[i]=='0':
    print(ls[(fXp+lsp[i])%bp]+1)
  else:
    if bm==0:
      print(0)
    else:
      print(ls[(fXm-lsm[i])%bm]+1)
### BUGGY CODE ###

from numpy import*
a,b=loadtxt(open(0),skiprows=1)
c=0
l=1<<29
while l:u=l;l>>=1;c+=sum(diff(searchsorted(sort(hstack((b%u-u,b%u))),([u],[l])-a%u).T))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)
### BUGGY CODE ###

n,k = map(int,input().split())
lis = list(map(int,input().split()))
li = list(map(int,input().split()))
lis.sort(reverse=True)
li.sort()
hi = 10 ** 12
low = 0
while hi > low+1:
    mid = (hi + low)//2
    cnt = 0
    for i in range(n):
        cnt += max(0,lis[i]-mid//li[i])
    if cnt <= k:
        hi = mid
    else:
        low = mid
    ans1 = low
    ans2 = hi
cnt = 0
for i in range(n):
    cnt += max(0,lis[i]-ans1//li[i])
if cnt <= k:
    print(ans1)
else:
    print(ans2)

### FIXED CODE ###

n,k = map(int,input().split())
lis = list(map(int,input().split()))
li = list(map(int,input().split()))
lis.sort(reverse=True)
li.sort()
hi = 10 ** 12
low = 0
while hi > low+1:
    mid = (hi + low)//2
    cnt = 0
    for i in range(n):
        cnt += max(0,lis[i]-mid//li[i])
    if cnt <= k:
        hi = mid
    else:
        low = mid
    ans1 = low
    ans2 = hi
cnt = 0
for i in range(n):
    cnt += max(0,lis[i]-ans1//li[i])
if cnt <= k:
    print(ans1)
else:
    print(ans2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] != 1:
  a[0] = 1
  ans += 1
b = [[]for i in range(n)]
for i in range(n):
  b[a[i]-1].append(i)
b[0].remove(0)
huka = 0
kyo = [float("inf")] * n
def dfs(x,y):
  kyo[x] = y
  for i in b[x]:
    dfs(i,y+1)
dfs(0,0)
def dfs2(x,y):
  if kyo[x] <=k-y:
    return
  if y == k-1 and x != 0:
    kyo[x] = 0
    global ans
    ans += 1
    return
  kyo[x] = 0
  dfs2(a[x]-1,y+1)
hukai = []
for i in range(n):
  hukai.append([kyo[i],i])
hukai.sort(key = lambda x:-x[0])
for j,i in hukai:
  if j <= k:
    continue
  dfs2(i,0)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
if a[0] != 1:
  a[0] = 1
  ans += 1
b = [[]for i in range(n)]
for i in range(1,n):
  b[a[i]-1].append(i)
huka = 0
kyo = [float("inf")] * n
z =[[]for i in range(n)]
def dfs(x,y):
  kyo[x] = y
  z[y].append(x)
  for i in b[x]:
    dfs(i,y+1)
dfs(0,0)
def dfs2(x,y):
  if kyo[x] <=k-y:
    return
  if y == k-1 and x != 0:
    kyo[x] = 0
    global ans
    ans += 1
    return
  kyo[x] = 0
  dfs2(a[x]-1,y+1)
for i in range(n-1,k,-1):
  for j in z[i]:
    dfs2(j,0)
print(ans)
### BUGGY CODE ###

N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  for i in range(N):
    if b[i]==i+1:
      cnt+=0
    elif i==b[b[i]-1]-1:
      c[i]+=1
  #print('c='+str(c))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()
  for i in range(N):
    b[i]=a[i][c[i]]
  #print('b='+str(b))

print('-1')

### FIXED CODE ###

import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
#print(matches)
q = deque(range(n))
#print(q)
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    b = matches[a].pop()
    #print(a, b)
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        if matches[a]:
            q.append(a)
        if matches[b]:
            q.append(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4017206
# N,M = map(int, input().split())
N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))


#1,2,3
A,B,C = (a[i] for i in range(1,4))

# dpA,B,C

dp = [ [ [0] * (C+1) 
           for _ in range(B+C+1)
       ]
           for _ in range(A+B+C+1) 
     ]


for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            # if a == b == c == 0:
            #     continue

            try: 
                dp[a][b][c] = (
                        ( a * ( dp[a-1][b][c]   if a else 0)  ) + 
                        ( b * ( dp[a+1][b-1][c] if b else 0)  ) +
                        ( c * ( dp[a][b+1][c-1] if c else 0)  ) + N 
                       ) / ( a+b+c ) 
            except:
                continue

print(dp[A][B][C])


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4017206
# N,M = map(int, input().split())
N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))


#1,2,3
A,B,C = (a[i] for i in range(1,4))

# dpA,B,C

# dp = [ [ [0] * (C+1) 
#            for _ in range(B+C+1)
#        ]
#            for _ in range(A+B+C+1) 
#      ]

dp = [ [ [0]*(A+B+C+1) for _ in range(B+C+1)]
        for _ in range(C+1) ] 

for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            # if a == b == c == 0:
            #     continue

            try: 
                dp[c][b][a] = (
                        ( a * ( dp[c][b][a-1]   if a else 0)  ) + 
                        ( b * ( dp[c][b-1][a+1] if b else 0)  ) +
                        ( c * ( dp[c-1][b+1][a] if c else 0)  ) + N 
                       ) / ( a+b+c ) 
                # dp[a][b][c] = (
                #         ( a * ( dp[a-1][b][c]   if a else 0)  ) + 
                #         ( b * ( dp[a+1][b-1][c] if b else 0)  ) +
                #         ( c * ( dp[a][b+1][c-1] if c else 0)  ) + N 
                #        ) / ( a+b+c ) 
            except:
                continue

print(dp[C][B][A])
# print(dp[A][B][C])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from functools import lru_cache

INF = 10**9 + 1

@lru_cache(None)
def get_max(A,B,rest,cur):
    if len(A) > 0:
        a = A[0]
    else:
        a = INF
    if len(B) > 0:
        b = B[0]
    else:
        b = INF
    if rest < a and rest < b:
        return cur

    if rest >= a:
        tmp_a = get_max(tuple(list(A)[1:]),B,rest-a,cur+1)
    else:
        tmp_a = 0
    if rest >= b:
        tmp_b = get_max(A,tuple(list(B)[1:]),rest-b,cur+1)
    else:
        tmp_b = 0

    return max(tmp_a,tmp_b)



def main():
    N,M,K = [int(i) for i in input().strip().split()]
    A = tuple([int(i) for i in input().strip().split()])
    B = tuple([int(i) for i in input().strip().split()])


    ans = get_max(A,B,K,0)

    return ans

if __name__ == "__main__":
    print(main())

### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)

def main():
    N,M,K = [int(i) for i in input().strip().split()]
    A = [int(i) for i in input().strip().split()]
    B = [int(i) for i in input().strip().split()]

    pre_A = [0] * (N + 1)
    pre_B = [0] * (M + 1)


    for i in range(1,N+1):
        pre_A[i] = pre_A[i-1] + A[i-1]
        if pre_A[i] > K:
            idx_a = i-1
            break
    else:
        idx_a = N

    for i in range(1,M+1):
        pre_B[i]= pre_B[i-1] + B[i-1]
        if pre_B[i] > K:
            idx_b = i-1
            break
    else:
        idx_b = M

    ans = max(idx_a,idx_b)

    j = idx_b
    for i in range(idx_a + 1):
        while pre_B[j] > K - pre_A[i]:
            j -= 1
        ans = max(ans,i+j)

    return ans

if __name__ == "__main__":
    print(main())