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

from operator import mul
from functools import reduce

def comb(n, r):
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer // denom

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

if K >= 2:
  A.sort(reverse = True)
  ans = 0
  for i in range(N - K + 1):
    for j in range(i + K - 1, N):
      ans += (A[i] - A[j]) * comb(j - i - 1, max(0, K - 2))
      ans %= MOD
  print(ans)
else:
  print(0)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

kai1 = [1, 1]
kai2 = [1, 1]
inverse = [0, 1]
for i in range(2, N + 1):
  kai1.append((kai1[-1] * i) % MOD)
  inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
  kai2.append((kai2[-1] * inverse[-1]) % MOD)


def comb(n, r):
  if r < 0 or r > n:
    return 0
  r = min(r, n - r)
  return (kai1[n] * kai2[r] * kai2[n - r]) % MOD

if K >= 2:
  A.sort(reverse = True)
  maxS = 0
  minS = 0
  for i in range(N - K + 1):
    maxS += A[i] * comb(N - i - 1, K - 1)
    maxS %= MOD
  A.sort()
  for i in range(N - K + 1):
    minS += A[i] * comb(N - i - 1, K - 1)
    minS %= MOD
  print((maxS - minS) % MOD)
else:
  print(0)
### BUGGY CODE ###

from functools import lru_cache


@lru_cache()
def mod_power(a, f_power):
    """
    a の p 乗を求めるアルゴリズム
    計算量はO(log(f_power))
    """
    if f_power == 0:
        return 1
    if f_power % 2 == 0:
        half = mod_power(a, f_power / 2)
        # half : a ** (power /2) の 2乗で a ** power を求める
        return half * half % MOD
    else:
        return a * mod_power(a, f_power - 1) % MOD


@lru_cache()
def comb(a, b):
    if b > a - b:
        return comb(a, a - b)
    # res = 1
    mul = 1
    div = 1
    for i in range(b):
        # res *= (a - i)
        # res /= (i + 1)
        mul *= (a - i)
        mul %= MOD

        div *= (i + 1)
        div %= MOD
    res = mul * mod_power(div, MOD - 2) % MOD
    return res


def prime_factorization(x):
    res = []
    i = 2
    left = x + 0
    while True:
        if (i * i > x) and (left == 1):
            break
        cnt = 0
        while left % i == 0:
            left /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        # print(i, res)
        i += 1
    return res


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

MOD = 10 ** 9 + 7

ans = 1
for power in prime_factorization(m):
    ans *= comb(n - 1 + power, power)
ans %= MOD

print(ans)
# print(prime_factorization(6))

### FIXED CODE ###

MOD = 10 ** 9 + 7


def prime_factorization(n):
    i = 2
    res = []
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        i += 1
    if n > 1:
        res.append(1)
    return res


def comb(a, b):
    b = min(b, a - b)
    if b < 0:
        return 0
    elif b == 0:
        return 1
    elif b == 1:
        return a
    else:
        return (a % MOD) * pow(b, MOD - 2, MOD) % MOD * comb(a - 1, b - 1) % MOD


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

ans = 1
for power in prime_factorization(M):
    ans *= comb(N - 1 + power, power)
    ans %= MOD

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

x, y, z, K = map(int, input().split())
K = min(x * y * z, K)
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)


def check(p, return_array=False):
    cnt = 0
    results = []
    for i in a:
        for j in b:
            for k in c:
                ijk = i + j + k
                if ijk < p:
                    break
                results.append(ijk)
                cnt += 1
                if cnt >= K:
                    return True, results
    return False, results


left = 10**10 * 3
right = 0

while left - right > 1:
    center = (left + right) // 2
    flg, results = check(center)
    if flg:
        tmp = results
        right = center
    else:
        left = center

print("\n".join(map(str, sorted(tmp, reverse=True))))


### FIXED CODE ###

import numpy as np
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))

ab = np.ravel(a + b[:, None])
ab.sort()
abc = np.ravel(c + ab[-k:, None])
abc.sort()
print(np.sum(abc[-k:][::-1].astype(str).astype(object) + "\n"), end="")
### BUGGY CODE ###

def z_algorithm(s):  # O(|S|)
    """
    SとS[i:]のLCP(longest common prefix: 最長共通接頭辞の長さ) Z[i]を計算し、Zを返す
    """
    n = len(s)
    z = [0] * n
    z[0] = n
    i = 1
    j = 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k < j and k + z[k] < j:
            z[i + k] = z[k]
            k += 1
        i += k
        j -= k
    return z

# ---------------------- #

n = int(input())
s = input()

ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j in range(len(Z)):
        if Z[j] > j:
            ans = max(ans, j)
        else:
            ans = max(ans, Z[j])

print(ans)


### FIXED CODE ###

def z_algorithm(s):  # O(|S|)
    """
    SとS[i:]のLCP(longest common prefix: 最長共通接頭辞の長さ) Z[i]を計算し、Zを返す
    """
    n = len(s)
    z = [0] * n
    z[0] = n
    i = 1
    j = 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while k < j and k + z[k] < j:
            z[i + k] = z[k]
            k += 1
        i += k
        j -= k
    return z

# ---------------------- #

n = int(input())
s = input()

ans = 0
for i in range(n):
    Z = z_algorithm(s[i:])
    for j in range(len(Z)):
        if Z[j] > j:
            ans = max(ans, j)
        else:
            ans = max(ans, Z[j])

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

n,m=map(int,input().split())
li=[]
for i in range(m):
    li.append(int(input()))

def convi(li):
    m=max(li)
    a=[1,1]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
            
    ans=1    
    for j in li:
        ans=ans*a[j-1]%1000000007
    return ans

def count(li,n):
    t=1
    ans=1
    li2=[]
    for i in range(1,n+1):
        if i in li:
            if i+1 in li:
                return(0)
            else:
                li2.append(t)
                t=0
        else:
            t+=1
    if t>0:        
        li2.append(t)   
    if 0 in li2:
    	li2.remove(0)
        

        
    return convi(li2)

                

print(count(li,n)%1000000007)   


### FIXED CODE ###

n,m=map(int,input().split())
li=[]
for i in range(m):
    li.append(int(input()))

def convi(li):
    m=max(li)
    a=[1,1]
    if m>2:
        for i in range(2,m+1):
            a.append(a[i-2]+a[i-1])
            
    ans=1    
    for j in li:
        ans=ans*a[j-1]%1000000007
    return ans

def count(li,n):
    t=1
    ans=1
    li2=[]
    li.append(n+1)
    if len(li)>0:
        for i in range(len(li)):
            
            if i>0:
                li2.append(li[i]-li[i-1]-1)
                if li[i]-li[i-1]==1 and i<len(li):
                    return 0
            else:
                li2.append(li[i])
                
    #print(li2)      
    return convi(li2)
                

print(count(li,n)%1000000007)
### BUGGY CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    H, W = read_values()
    S = [input() for _ in range(H)]
    X = [[0 for _ in range(W)] for __ in range(H)]
    Y = [[0 for _ in range(W)] for __ in range(H)]

    for h in range(H):
        for w in range(W):
            if S[h][w] == ".":
                X[h][w] = 1 if w == 0 else X[h][w - 1] + 1
                Y[h][w] = 1 if h == 0 else Y[h - 1][w] + 1

    res = 0
    for h in range(H - 1, -1, -1):
        for w in range(W - 1, -1, -1):
            if S[h][w] == "#":
                continue
            if w != W - 1:
                X[h][w] = max(X[h][w + 1], X[h][w]) 
            if h != H - 1:
                Y[h][w] = max(Y[h + 1][w], Y[h][w])
            res = max(res, X[h][w] + Y[h][w] - 1)
    print(res)

        
if __name__ == "__main__":
    main()



### FIXED CODE ###

def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    H, W = read_values()
    S = [input() for _ in range(H)]
    X = [[0 for _ in range(W)] for __ in range(H)]
    Y = [[0 for _ in range(W)] for __ in range(H)]

    for h in range(H):
        for w in range(W):
            if S[h][w] == ".":
                X[h][w] = 1 if w == 0 else X[h][w - 1] + 1
                Y[h][w] = 1 if h == 0 else Y[h - 1][w] + 1

    res = 0
    for h in range(H - 1, -1, -1):
        for w in range(W - 1, -1, -1):
            if S[h][w] == "#":
                continue
            if w != W - 1:
                X[h][w] = max(X[h][w + 1], X[h][w]) 
            if h != H - 1:
                Y[h][w] = max(Y[h + 1][w], Y[h][w])
            res = max(res, X[h][w] + Y[h][w] - 1)
    print(res)

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

n,k = map(int,input().split())
alis = list(map(int,input().split()))

value = 1
for i in range(k):
    value = value * alis[i]

for i in range(k,n):
    if(value < value*alis[i]/alis[i-k]):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n,k = map(int,input().split())
alis = list(map(int,input().split()))

for i in range(n-k):
    if(alis[i]<alis[i+k]):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
sum = 0
for i in range(1, n):
    sum += i
print(sum)

### FIXED CODE ###

n = int(input())
ans = int((n*(n-1))//2)
print(ans)
### BUGGY CODE ###

import numpy as np
import copy

N = int(input())  
a = np.array(input().split(), dtype=np.int32)
M = np.arange(N) + 1
    
for i in np.arange(N // 2)[::-1]:
    A = a[np.where(M % (i+1) == 0)]
    if np.sum(A) % 2  == 0:
        a[i] = 0
    else:
        a[i] = 1
        
ans = np.where(a == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))

### FIXED CODE ###

import numpy as np
import copy

N = int(input())  
a = np.array(input().split(), dtype=np.int32)
M = np.arange(N) + 1
    
for i in np.arange(N // 2)[::-1]:
    A = a[i::i+1]
    if np.sum(A) % 2  == 0:
        a[i] = 0
    else:
        a[i] = 1
        
ans = np.where(a == 1)[0] + 1

print(np.size(ans))

if np.size(ans) > 0:
    print(*ans.astype(np.int32))
### BUGGY CODE ###

import pprint
N=int(input())
l2=[]
bit2=50
bit5=22
#table=[[0 for _ in range(20)] for _ in range(15)]
#table=[[0 for _ in range(45)] for _ in range(20)]
table=[[0 for _ in range(bit2)] for _ in range(bit5)]
from decimal import *
getcontext().prec=20
for i in range(N):
    pf={}
    n=float(input())
    #print(n)
    n=n*pow(10,9)
    count2=0
    count5=0
    n=Decimal(n)
    #print(n,kake)
    while n/2==n//2:
        n=n//2
        count2=count2+1
    while n/5==n//5:
        n=n//5
        count5=count5+1
    table[count5][count2]=table[count5][count2]+1
    l2.append([count2,count5])
#pprint.pprint(table)
#print(l2)
ans=0
for i in range(bit5):
    for j in range(bit2):
        num=table[i][j]
        min2=max(0,18-j)
        min5=max(0,18-i)
        cnt=0
        if num>0:
            #print(min2,min5,i,j,num)
            for k in range(min5,bit5):
                for l in range(min2,bit2):
                    cnt=cnt+table[k][l]
            if (min2<=j)and(min5<=i):
                cnt=cnt-1
            ans=ans+num*cnt
            #print(ans)
print(ans//2)



### FIXED CODE ###

import pprint
from collections import deque
N=int(input())
l2=[]
bit2=50
bit5=22
#table=[[0 for _ in range(20)] for _ in range(15)]
#table=[[0 for _ in range(45)] for _ in range(20)]
table=[[0 for _ in range(bit2)] for _ in range(bit5)]
for i in range(N):
    n=list(input())
    #print(n)
    cnt=9
    d=deque()
    flag=1
    for i in range(len(n)):
        if n[i]==".":
            flag=0
        else:
            d.append(n[i])
            if flag==0:
                cnt=cnt-1
    for i in range(cnt):
        d.append("0")
    n=int("".join(d))
    #print(n)
    count2=0
    count5=0
    #print(n,kake)
    while n%2==0:
        n=n//2
        count2=count2+1
    while n%5==0:
        n=n//5
        count5=count5+1
    table[count5][count2]=table[count5][count2]+1
    l2.append([count2,count5])
#pprint.pprint(table)
#print(l2)
ans=0
for i in range(bit5):
    for j in range(bit2):
        num=table[i][j]
        min2=max(0,18-j)
        min5=max(0,18-i)
        cnt=0
        if num>0:
            #print(min2,min5,i,j,num)
            for k in range(min5,bit5):
                for l in range(min2,bit2):
                    cnt=cnt+table[k][l]
            if (min2<=j)and(min5<=i):
                cnt=cnt-1
            ans=ans+num*cnt
            #print(ans)
print(ans//2)
### BUGGY CODE ###

n, k, s = map(int, input().split())
ans = ""
for i in range(k):
    ans += str(s) + " "
if s != 10**9:
    for i in range(n - k):
        ans += str(s + 1) + " "
else:
    for i in range(n - k):
        ans += str(s - 1) + " "
print(ans)

### FIXED CODE ###

n, k, s = map(int, input().split())
ans = []
for i in range(k):
    ans.append(str(s))
if s != 10**9:
    for i in range(n - k):
        ans.append(str(s + 1))
else:
    for i in range(n - k):
        ans.append(str(s - 1))
print(" ".join(ans))
### BUGGY CODE ###

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
abcd = sorted(abcd, key=lambda x:x[3], reverse=True)
A = [0]*N
a = 0
for i in range(2**Q):
  bag = []
  A = [-1]*(N+1)
  A[1] = 1
  ans = 0
  for j in range(Q):
    if (i>>j)&1:
      bag += [j]

  for j in bag:
    if A[abcd[j][1]] == -1:
      if A[abcd[j][0]] + abcd[j][2] <= M:
        A[abcd[j][1]] = A[abcd[j][0]] + abcd[j][2]
        ans += abcd[j][3]
      else:
        ans = 0
        break
    elif A[abcd[j][1]] == A[abcd[j][0]] + abcd[j][2]:
      ans += abcd[j][3]
    else:
      ans = 0
      break

  a = max(ans, a)

print(a)


### FIXED CODE ###

import itertools
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
A = [0]*N
ans = 0
bag = [i for i in range(1, M+1)]
for v in itertools.combinations_with_replacement(bag, N):
  an = 0
  for a, b, c, d in abcd:
    a -= 1
    b -= 1
    if v[b] - v[a] == c:
      an += d

  ans = max(ans, an)
print(ans)
### BUGGY CODE ###

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

def main():
    S = input()
    ini_len = len(S)

    ind0 = 1
    ind1 = 1
    while ind0 >= 0 or ind1 >= 0:
        ind0 = S.find('01')
        if ind0 >= 0:
            S = S.replace('01', '')
        ind1 = S.find('10')
        if ind1 >= 0:
            S = S.replace('10', '')
    print(ini_len - len(S))

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    S = input()
    print(len(S) - abs(S.count('1') - S.count('0')))

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

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N
tmp = A[0]
for i in range(N):
    if i == 0: 
        A[i] = 0
    else:
        tmp = A[i]
        A[i] = A[i-1]
    ans[i] += abs(A[0])
    for j in range(N-1):
        ans[i] += abs(A[j]-A[j+1])
    ans[i] += abs(A[N-1])
    A[i] = tmp
for i in range(N):
    print(ans[i])

### FIXED CODE ###

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

all = abs(A[0]) + abs(A[N-1])
for i in range(N-1):
    all += abs(A[i+1] - A[i])

print(all - (abs(A[0]) + abs(A[1]-A[0])) + abs(A[1]))

for i in range(1, N-1):
    print(all- (abs(A[i+1]-A[i]) + abs(A[i-1] - A[i])) + abs(A[i+1]-A[i-1]))
    
print(all - (abs(A[N-1])+abs(A[N-1]-A[N-2])) + abs(A[N-2]))
### BUGGY CODE ###

N = int(input())
if N !=1:
    result = sum(range(1,N))
else:
    result = 0
print(result)

### FIXED CODE ###

N = int(input())
result = N * (N-1)//2
print(result)
### BUGGY CODE ###

import math

n = int(input())
ans = 0
x = int(math.ceil(math.sqrt(n)))

for i in range(1, x+1):
    j=i
    while i*j<=n:
        if i*j == n and (i+j-2 < ans or ans == 0):
            ans = i+j-2
            break
        j+=1

print(ans)



### FIXED CODE ###

import math

n = int(input())
ans = n-1
x = int(math.ceil(math.sqrt(n)))

for i in range(1, x+1):
    if n%i == 0:
        ans = int(min(ans, i+n/i-2))

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

from collections import deque
h,w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
m = ['#' for _ in range(h+2)]
m[0] += '#'*(w+1)
m[h+1] += '#'*(w+1)
que = deque()
que.append(c)
warp = [[10**9 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1,h+1):  m[i] += input()+'#'
up = lambda x,y: 1 if 0<x-1 and m[x-1][y]=='.' else 0
down = lambda x,y: 1 if x+1<=h and m[x+1][y]=='.' else 0
right = lambda x,y: 1 if y+1<=w and m[x][y+1]=='.' else 0
left = lambda x,y: 1 if 0<y-1 and m[x][y-1]=='.' else 0

def jump(x,y,cost):
  deq = deque()
  for i in range(x-2,x+3):
    if i<=0 or h<i:  continue
    for j in range(y-2,y+3):
      if j<=0 or w<j:  continue
      if m[i][j] == '.' and warp[i][j]>cost+1:
        warp[i][j] = cost+1
        if (i,j) not in que:
          deq.append((i,j))
  return deq
  
warp[c[0]][c[1]] = 0
while que:
  q = que.popleft()
  row,col = q[0],q[1]
  cost = warp[row][col]
  if up(row,col) and warp[row-1][col]>cost:
    que.appendleft((row-1,col))
    warp[row-1][col] = cost
  if down(row,col) and warp[row+1][col]>cost:
    que.appendleft((row+1,col))
    warp[row+1][col] = cost
  if right(row,col) and warp[row][col+1]>cost:
    que.appendleft((row,col+1))
    warp[row][col+1] = cost
  if left(row,col) and warp[row][col-1]>cost:
    que.appendleft((row,col-1))
    warp[row][col-1] = cost
  que.extend(jump(row,col,cost))
if warp[d[0]][d[1]] != 10**9: print(warp[d[0]][d[1]])
else: print(-1)

### FIXED CODE ###

from collections import deque
h,w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
m = ['#' for _ in range(h+2)]
m[0] += '#'*w
m[h+1] += '#'*w
que = deque()
que.append(c)
warp = [[10**6 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1,h+1):  m[i] += input()+'#'
up = lambda x,y: 1 if 0<x-1 and m[x-1][y]=='.' else 0
down = lambda x,y: 1 if x+1<=h and m[x+1][y]=='.' else 0
right = lambda x,y: 1 if y+1<=w and m[x][y+1]=='.' else 0
left = lambda x,y: 1 if 0<y-1 and m[x][y-1]=='.' else 0

def jump(x,y,cost):
  deq = deque()
  for i in range(x-2,x+3):
    if i<=0 or h<i:  continue
    for j in range(y-2,y+3):
      if j<=0 or w<j:  continue
      if m[i][j] == '.' and warp[i][j]>cost+1:
        warp[i][j] = cost+1
        deq.append((i,j))
  return deq
  
warp[c[0]][c[1]] = 0
while que:
  q = que.popleft()
  row = q[0]
  col = q[1]
  cost = warp[row][col]
  if up(row,col) and warp[row-1][col]>cost:
    que.appendleft((row-1,col))
    warp[row-1][col] = cost
  if down(row,col) and warp[row+1][col]>cost:
    que.appendleft((row+1,col))
    warp[row+1][col] = cost
  if right(row,col) and warp[row][col+1]>cost:
    que.appendleft((row,col+1))
    warp[row][col+1] = cost
  if left(row,col) and warp[row][col-1]>cost:
    que.appendleft((row,col-1))
    warp[row][col-1] = cost
  que.extend(jump(row,col,cost))

if warp[d[0]][d[1]] != 10**6:  print(warp[d[0]][d[1]])
else:  print(-1)
### BUGGY CODE ###

S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
kake = 1
ret = 0
len_s = len(S)
for i in range(len_s) :
	p_amari = ( int(S[len_s-1-i]) * kake + p_amari ) % 2019
	ret += ls[p_amari]
	ls[p_amari] += 1
	kake *= 10
print(int(ret))

### FIXED CODE ###

S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
ret = 0
len_s = len(S)
for i in range(len_s) :
	p_amari = ( int(S[len_s-1-i]) * pow(10, i, 2019) + p_amari ) % 2019
	ret += ls[p_amari]
	ls[p_amari] += 1
print(int(ret))
### BUGGY CODE ###

A,B,K=map(int,input().split())
l=[x for x in range(A,B+1) if x-A<=K-1 or B-x<=K-1]
for x in l:
    print(x)

### FIXED CODE ###

A,B,K=map(int,input().split())
if B-A+1<=2*K:
    for i in range(A,B+1):
        print(i)
else:
    for i in range(A,A+K):
        print(i)
    for i in range(B-K+1,B+1):
        print(i)
### BUGGY CODE ###

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

f = 1

if n%2 == 0:
    for i in range(n//2):
        if a.count((2*i)+1) != 2:
            f = 0
            break

else:
    if a.count(0) != 1:
        f == 0
    for i in range(n//2):
        if a.count((2*i)+2) != 2:
            f = 0
            break
if f == 0:
    print(f)
else:
    print(2**(n//2))

### FIXED CODE ###

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

f = 1

if n%2 == 0:
    ans = [2]*(n//2)
    #print(ans)
    for i in range(n):
        if a[i]%2 == 0:
            f = 0
            break
        x = a[i]//2
        ans[x] -= 1

else:
    ans = [2]*((n+1)//2)
    ans[0] -= 1
    for i in range(n):
        if a[i]%2 != 0:
            f = 0
            break
        x = a[i]//2
        ans[x] -= 1

for i in range(len(ans)):
    if ans[i] != 0:
        f = 0
        break

if f == 0:
    print(f)
else:
    print((2**(n//2))%1000000007)
### BUGGY CODE ###

a = int(input())
b = list(map(int, input().split()))
c = [b.count(i+1) for i in range(a)]
[print(j) for j in c]

### FIXED CODE ###

a = int(input())
b = list(map(int, input().split()))
c = [0 for i in range(a)]
for i in b:
  c[i-1] += 1
for j in c:
  print(j)
### BUGGY CODE ###

import numpy as np

n,m,q = map(int, input().split())

a = np.zeros((n+1,n+1))

for i in range(m):
    l,r = map(int,input().split())
    a[r:,:l+1] += 1

for i in range(q):
    p,q = map(int, input().split())
    print(int(a[q][p]))


### FIXED CODE ###

n,m,q = map(int, input().split())

a = [[0]*(n+1) for i in range(n+1)]

for i in range(m):
    l,r = map(int, input().split())
    a[l][r]+=1

b = [[0]*(n+1) for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]

for i in range(q):
    p,q = map(int, input() .split())
    ans = b[q][q]-b[p-1][q]-b[q][p-1]+b[p-1][p-1]
    print(ans)
### BUGGY CODE ###

def main():
    n,m,k = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    ma = 0
    a2 = [0]
    b2 = [0]
    for i in range(len(a)):
        a2.append(a[i]+a2[i])
    for i in range(len(b)):
        b2.append(b[i]+b2[i])
    jj = len(b2)-1
    for i in range(len(a2)):
        if(a2[i]>k):
            break
        j = jj
        while((a2[i]+b2[j])>k):
            j -= 1
        ma = max(ma,i+j)

    print(ma)
            
main()

### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)