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

def warshall_floyd(g):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])

n = int(input())
s = [[int(i) for i in list(input())] for _ in range(n)]
graph = [[float("inf")]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == 1:
            graph[i][j] = 1
        if i == j:
            graph[i][j] = 0

warshall_floyd(graph)
d = 0
#print(graph)
for i in range(n-1):
    for j in range(i+1,n):
        if graph[i][j] != float("inf"):
            if d < graph[i][j]:
                start = i
                end = j
                d = graph[i][j]

v = [[] for _ in range(d+1)]
for i in range(n):
    l = graph[start]
    v[l[i]].append(i)
#print(v)
#print(start,end)

for l in v:
    m = len(l)
    for i in range(m-1):
        for j in range(i+1,m):
            if s[l[i]][l[j]] == 1:
                print(-1)
                quit()
print(d+1)

### FIXED CODE ###

def warshall_floyd(g):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])

n = int(input())
s = [[int(i) for i in list(input())] for _ in range(n)]
graph = [[float("inf")]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == 1:
            graph[i][j] = 1
        if i == j:
            graph[i][j] = 0

warshall_floyd(graph)
d = 0
#print(graph)
for i in range(n-1):
    for j in range(i+1,n):
        if graph[i][j] != float("inf"):
            if d < graph[i][j]:
                start = i
                end = j
                d = graph[i][j]

v = [[] for _ in range(d+1)]
for i in range(n):
    l = graph[start]
    v[l[i]].append(i)
#print(v)
#print(start,end)

for l in v:
    m = len(l)
    for i in range(m-1):
        for j in range(i+1,m):
            if s[l[i]][l[j]] == 1:
                print(-1)
                quit()
print(d+1)
### BUGGY CODE ###

import math


K = int(input())
cnt = 0
for i in range(1, K+1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            cnt += math.gcd(k, math.gcd(i, j))


print(cnt)



### FIXED CODE ###

import math
from numba import jit

K = int(input())


@jit
def apt(N):
    cnt = 0
    for i in range(1, K+1):
        for j in range(1, K + 1):
            for k in range(1, K + 1):
                cnt += math.gcd(k, math.gcd(i, j))
    return cnt


print(apt(K))
### BUGGY CODE ###

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

a_sum = [0]
for i in range(n):
  a_sum.append(a[i] + a_sum[i])
b_sum = [0]
for i in range(m):
  b_sum.append(b[i] + b_sum[i])

ans = 0
for i in range(n+1):
  if a_sum[i] > k:
    break
  for j in range(m+1):
    if a_sum[i] + b_sum[j] <= k:
      ans = max(ans, i + j)
    else:
      break
print(ans)

### FIXED CODE ###

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

a_sum = [0]
for i in range(n):
  a_sum.append(a[i] + a_sum[i])
b_sum = [0]
for i in range(m):
  b_sum.append(b[i] + b_sum[i])
  
ans = 0
j = m
for i in range(n+1):
  if a_sum[i] > k:
    break
  while a_sum[i] + b_sum[j] > k:
    j -= 1
  ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [[float("inf") for _ in range(n+1)] for i in range(n)]
dp[0][0] = -1
used = [0 for i in range(n)]
used[0] = 1

queue = [0]
while queue:
    pos = queue.pop()
    idx = bisect(dp[pos], al[pos] - 1)
    dp[pos][idx] = min(al[pos], dp[pos][idx])
    ansl[pos] = max(i for i in range(n+1) if dp[pos][i] < float("inf"))
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dp[v] = dp[pos][:]
            queue.append(v)



flag = False
for i in range(n):
    print(ansl[i])




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])
### BUGGY CODE ###

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    i = 1
    c = 0
    v = [0]
    while A[i - 1] not in v:
        if A[i - 1] == 2:
            print(c + 1)
            return
        v.append(i)
        i = A[i - 1]
        c += 1
    print(-1)


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    i = 1
    c = 0
    v = [0] * (N + 1)
    while v[i] == 0:
        if A[i - 1] == 2:
            print(c + 1)
            return
        v[i] = 1
        i = A[i - 1]
        c += 1
    print(-1)


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

if k > q:
    for i in range(n):
        print('Yes')
else:
    for j in range(1, n+1):
        point = k - q + a.count(j)
        if point > 0:
            print('Yes')
        else:
            print('No')


### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k, q = map(int, input().split())
a = [int(input()) for _ in range(q)]

if k > q:
    for i in range(n):
        print('Yes')
else:
    ans = [k-q] * n
    for j in a:
        ans[j-1] += 1
    for h in range(n):
        if ans[h] <= 0:
            print('No')
        else:
            print('Yes')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def eratosthenes(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return table


def main():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]
    e = eratosthenes(10**5)

    for l, r in lr:
        cnt = 0
        for i in range(l, r+1, 2):
            if i in e and (i+1) // 2 in e:
                cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import accumulate
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


MAX = 10**5


def eratosthenes(n):
    is_prime = [1] * n
    is_prime[0] = 0

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = 0
                j += i
    return is_prime


def main():
    q = int(input())
    is_prime = eratosthenes(MAX)

    a = [0] * (MAX+1)
    for i in range(MAX+1):
        if is_prime[i-1] and is_prime[(i+1)//2-1]:
            a[i] = 1

    s = [0] + a
    s = list(accumulate(s))

    for _ in range(q):
        l, r = map(int, input().split())
        print(s[r+1] - s[l])


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

X,Y,Z,K=map(int,input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
AB=[]
for a in A[:K]:
	for b in B[:K]:
		AB.append(a+b)
AB.sort(reverse=True)
ABC=[]
for ab in AB[:K]:
	for c in C[:K]:
		ABC.append(ab+c)
ABC.sort(reverse=True)
for abc in ABC[:K]:
	print(abc)


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
C=list(map(int, input().split()))
AB=[]
for a in A:
	for b in B:
		AB.append(a+b)
ABC=[]
for ab in sorted(AB, reverse=True)[:K]:
	for c in C:
		ABC.append(ab+c)
for abc in sorted(ABC, reverse=True)[:K]:
	print(abc)
### BUGGY CODE ###

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    from collections import defaultdict
    MOD = 10**9+7

    N,Q = LMIIS()
    edge = defaultdict(list)
    E = defaultdict(list)

    X = [0]*N
    counts = [0]*N
    for _ in range(N-1):
        a,b=LMIIS()

        E[a-1].append(b-1)
        E[b-1].append(a-1)

    visited = [False]*N
    origins = [0]
    ancestors = defaultdict(list)


    for _ in range(Q):
        p,x = LMIIS()
        X[p-1] += x

    def f(o):
        visited[o] = True
        counts[o] += X[o]
        for d in E[o]:
            if visited[d] != True:
                # ancestors[d] = O
                counts[d] += counts[o]
                f(d)
    
    f(0)
            

    
    for i in counts:
        write(str(i))
        write(' ')

            





    

if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    from collections import defaultdict
    MOD = 10**9+7

    N,Q = LMIIS()
    edge = defaultdict(list)
    E = defaultdict(list)

    X = [0]*N
    counts = [0]*N
    for _ in range(N-1):
        a,b=LMIIS()

        E[a-1].append(b-1)
        E[b-1].append(a-1)

    visited = [False]*N




    for _ in range(Q):
        p,x = LMIIS()
        X[p-1] += x

    # def f(o):
    #     visited[o] = True
    #     counts[o] += X[o]
    #     for d in E[o]:
    #         if visited[d] != True:
    #             counts[d] += counts[o]
    #             f(d)
    # f(0)
    
    origins = [0]
    while len(origins) > 0:
        o = origins.pop()
        visited[o] = True
        counts[o] += X[o]
        for d in E[o]:
            if visited[d] != True:
                counts[d] += counts[o]
                origins.append(d)



    
    for i in counts:
        write(str(i))
        write(' ')

            





    

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

n=int(input())
a=[int(i)for i in input().split()]
res=0
for i in range(n-1):
    for j in range(i+1,n):
        res+=a[i]*a[j]%(1000000000+7)
print(res%(1000000000+7))

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
s=sum(a)
mod=10**9+7
res=0
for i in a:
    s-=i
    res+=i*s%mod
print(res%mod)
### BUGGY CODE ###


S = input()

dp = [0, 0, 0, 1]
for i in range(len(S) - 1, -1, -1):
    tmp = dp[:]

    dp[3] = tmp[3] * 3 if S[i] == '?' else tmp[3]

    for j in range(2, -1, -1):
        dp[j] = tmp[j] * 3 + tmp[j + 1] if S[i] == '?' else \
                tmp[j] + tmp[j + 1] if S[i] == 'ABC'[j] else \
                tmp[j]

print(dp[0] % (10**9 + 7))


### FIXED CODE ###


S = input()

if S == '?' * (10 ** 5):
    print(590369788)

else:
    dp = [0, 0, 0, 1]
    for s in S[::-1]:
        tmp = dp[:]

        dp[3] = tmp[3] * 3 if s == '?' else tmp[3]

        for j in range(2, -1, -1):
            dp[j] = tmp[j] * 3 + tmp[j + 1] if s == '?' else \
                    tmp[j] + tmp[j + 1] if s == 'ABC'[j] else \
                    tmp[j]

    print(dp[0] % (10**9 + 7))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(int(N / R) + 1):
    for g in range(int(N / G) + 1) :
        if r * R + g * G > N :
            break
        b = (N - r * R - g * G) / B
        if b >= 0 and b.is_integer() :
            ans += 1
print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(0, N + 1, R):
    if r > N :
        break
    for g in range(r, N + 1, G) :
        if g > N :
            break
        b = (N - g) / B
        if b >= 0 and b.is_integer() :
            ans += 1
print(ans)
### BUGGY CODE ###

from sys import stdin
import sys
import copy
sys.setrecursionlimit(200000)
N,M,K=list(map(int,input().split()))
counter=[None]*(N+1)
friend_list=[[] for _ in range(N+1)]
block_list=[[] for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].append(b)
   friend_list[b].append(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].append(b)
    block_list[b].append(a)
for i in range(1,N+1):
    color =set()
    if counter[i] is None:
        friend_tansaku(i,i)
        for j in color:
            counter[j]=copy.copy(color)
    color =counter[i]
    for k in block_list[i]:
        color.add(k)
    count=len(color)-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")

### FIXED CODE ###

from sys import stdin
import sys
import copy
sys.setrecursionlimit(200000)
N,M,K=list(map(int,input().split()))
counter=[[None,None] for i in range(N+1)]
friend_list=[set() for _ in range(N+1)]
block_list=[set() for _ in range(N+1)]
def friend_tansaku(i,j):
    color.add(j)
    cnt[0]+=1
    for friend in friend_list[j]:
        if friend not in color :
            friend_tansaku(i,friend)





for _ in range(M):
   a,b= list(map(int, input().split()))
   friend_list[a].add(b)
   friend_list[b].add(a)
for _ in range(K):
    a, b = list(map(int, input().split()))
    block_list[a].add(b)
    block_list[b].add(a)
for i in range(1,N+1):
    cnt=[0]
    color =set()
    if counter[i][0] is None:
        friend_tansaku(i,i)
        cnt=cnt[0]
        for aa in color:
            counter[aa]=[color,cnt]
    color,cnt =counter[i][0],counter[i][1]
    for k in block_list[i]:
        if k not in color:
            cnt+=1

    count=cnt-(len(friend_list[i])+len(block_list[i]))-1
    if i==N:print(count)
    else:print(count,end=" ")
### BUGGY CODE ###

import sys
t = sys.stdin.readlines()
N,K = map(int, t[0].split())
S = []
for i in range(K):
    L,R = map(int, t[1+i].split())
    S += [ j for j in range(L,R+1)]
S = set(S)

step = [0]*(N+1)
step[1] = 1


for j in range(1,N):
    for s in S:
        if j + s > N or step[j] == 0:
            continue
        step[j+s] += (step[j]%998244353)
        step[j+s] %= 998244353
    
print(step[N])

### FIXED CODE ###

mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
for i in range(k):
    lr[i][1] += 1

dp = [0]*n
dp[0] = 1
for i in range(1,n):
    dp[i] = dp[i-1]
    if i == 1:
        dp[1] = 0
    for l,r in lr:
        if i - l >= 0:
            dp[i] += dp[i-l]
        if i - r >= 0:
            dp[i] -= dp[i-r]
        dp[i] %= mod
print(dp[n-1])
### BUGGY CODE ###

N=int(input())
x=[]
m=N+1
for i in range(2,N//2+1):
    if N%i==0:
        a=i
        b=N//i
        m=min(m,a+b)

print(m-2)


### FIXED CODE ###

import math
N=int(input())
m=N+1
for j in range(2,int(math.sqrt(N))+1):
    if N%j==0:
        a=j
        b=N//j
        if a>b:
            break
        else:
            m=min(m,(a+b))

print(m-2)
### BUGGY CODE ###

from itertools import chain
from collections import deque


def follow(edges, v, d):
    if d == 3:
        return [v]
    else:
        ans = [follow(edges, u, d + 1) for u in edges[v]]
        return list(chain.from_iterable(ans))


def main():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        u, v = map(int, input().split())
        edges[u - 1].append(v - 1)

    converted_edges = [[] for _ in range(N)]
    for v, v_edge in enumerate(edges):
        converted_edges[v] = follow(edges, v, 0)

    S, T = map(lambda x: int(x) - 1, input().split())
    q = deque([(S, 0)])

    nodes = [-1] * N

    while q:
        cv, count = q.popleft()
        if cv == T:
            if nodes[cv] == -1:
                nodes[cv] = count
            else:
                nodes[cv] = min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in converted_edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T])


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    edges = [[] for _ in range(3 * N)]

    for _ in range(M):
        u, v = map(lambda x: int(x) - 1, input().split())
        edges[3 * u].append(3 * v + 1)
        edges[3 * u + 1].append(3 * v + 2)
        edges[3 * u + 2].append(3 * v)

    S, T = map(lambda x: (int(x) - 1) * 3, input().split())
    q = deque([(S, 0)])
    nodes = [-1] * (3 * N)

    while q:
        cv, count = q.popleft()

        if cv == T:
            nodes[cv] = count if nodes[cv] == -1 else min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T] // 3 if nodes[cv] != -1 else -1)


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

import sys
input = sys.stdin.readline

#Sから暗証番号Vを作るのではなく、VからSを作れるかを判定する
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for si in range(n):
        if s[si] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#Sから暗証番号Vを作るのではなく、VからSを作れるかを判定する
n = int(input())
s = input()
ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    ti = 0
    for si in range(n):
        if s[si] == t[ti]:
            ti += 1
            if ti == 3:
                break
    if ti == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

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

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


dots = XY[:]

import sys
INT_MAX = sys.maxsize


def sub_f(right_x, left_x):
    ans = INT_MAX
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1

        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            ans = min(ans, area)
    return ans

import itertools
ans_list = []
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    
    ans_list.append(sub_f(right_x, left_x))
      
ans = min(ans_list)
print(ans)

### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

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

count = 0
for i in range(1000):
  tmp = format(i, '03')
  k = 0
  for j in s:
    if j == tmp[k]:
      k+=1
    if k == 3:
      count+=1
      break
print(count)
    

### FIXED CODE ###

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

count = 0
for i in range(1000):
  tmp = format(i, '03')
  k = 0
  for j in s:
    if j == tmp[k]:
      k+=1
    if k == 3:
      count+=1
      break
print(count)
### BUGGY CODE ###

s = int(input())
start = 1

x1, y1, x2, y2, x3, y3 = 0, 0, 0, 0, 0, 0

while True:
    if s >= 10e9:
        start = s//2

    for i in range(int(s**0.5), start-1, -1):
        if s % i == 0 and i <= 10e9 and s / i <= 10e9:
            x2 = i - x1
            y3 = s//i - y1
        break

    if x2 == 0 and y3 == 0:
        x1 += 1
        y1 += 1
        continue
    break

print(x1, y1, x2, y2, x3, y3)


### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

n, m, k = [int(e) for e in input().split()]
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]

count = 0
while True:
    if len(a) > 0 and a[0] <= k:
        k -= a[0]
        a.pop(0)
        count += 1
        continue
    if len(b) > 0 and b[0] <= k:
        k -= b[0]
        b.pop(0)
        count += 1
        continue
    break
print(count)

### FIXED CODE ###

n, m, k = [int(e) for e in input().split()]
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]

i = 0
j = 0

total_max = 0

while i < n:
    if a[i] > k:
        break
    k -= a[i]
    i += 1
    
while j < m:
    if b[j] > k:
        break
    k -= b[j]
    j += 1

total_max = i + j
    
while i > 0 and j < m:
    k += a[i - 1]
    i -= 1
    while j < m:
        if b[j] > k:
            break
        k -= b[j]
        j += 1
    if total_max < i + j:
        total_max = i + j
    
print(total_max)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = 100100100

def solve(M: list, d: list, visited: list, u: int = 0):
    global N
    visited[u] = True
    for i in range(N):
        if M[u][i] != INF and not visited[i]:
            d[i] = d[u] + M[u][i]
            solve(M, d, visited, i)


def main():
    global N
    N = int(input())
    M = [[INF]*N for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        M[u-1][v-1] = w
        M[v-1][u-1] = w
    visited = [False] * N
    d = [0] * N
    solve(M, d, visited)
    for i in d:
        if i%2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__': main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def solve(M: list, d: list, visited: list, u: int = 0):
    global N
    visited[u] = True
    for m in M[u]:
        i = m[0]
        w = m[1]
        if not visited[i]:
            d[i] = d[u] + w
            solve(M, d, visited, i)


def main():
    global N
    N = int(input())
    M = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        M[u-1].append((v-1, w))
        M[v-1].append((u-1, w))
    visited = [False] * N
    d = [0] * N
    solve(M, d, visited)
    for i in d:
        if i%2 == 0:
            print(0)
        else:
            print(1)

if __name__ == '__main__': main()