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

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
key = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bt = 0
    for e in c:
        bt |= 1 << (e - 1)
    key.append((bt, a))

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        state = i | key[j][0]
        cost = dp[i] + key[j][1]
        dp[state] = min(dp[state], cost)

if dp[-1] == float("inf"):
    ans = -1
else:
    ans = dp[-1]

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():

    INF = 10 ** 7
    n, m = map(int, input().split())
    state_num = 1 << n
    key = []
    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        bt = 0
        for e in c:
            bt |= 1 << (e - 1)
        key.append((bt, a))

    dp = [INF for _ in range(state_num)]
    dp[0] = 0

    for i in range(state_num):
        for j in range(m):
            ks, kc = key[j]
            state = i | ks
            cost = dp[i] + kc
            dp[state] = min(dp[state], cost)

    ans = dp[-1]
    if ans == INF:
        ans = -1
    print(ans)


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

N, K = [int(v) for v in input().split()]

link = []
for k in range(K):
    L, R = [int(v) for v in input().split()]

    for i in range(L, R+1):
        link.append(i)

link.sort()
count = [1]

for i in range(1, N):
    v = 0
    for l in link:
        if i < l:
            break
        v += count[i - l]
    count.append(v % 998244353)

print(count[-1])


### FIXED CODE ###

N, K = [int(v) for v in input().split()]

links = []
for k in range(K):
    L, R = [int(v) for v in input().split()]
    links.append((L, R))

links = sorted(links, key=lambda x: x[1])

count = [1]
sub = [0, 1]
subtotal = 1

for i in range(1, N):
    v = 0
    for l, r in links:
        r2 = i - l + 1
        l2 = i - r
        if l2 < 0:
            l2 = 0
        if r2 >= 0:
            v += sub[r2] - sub[l2]

    count.append(v % 998244353)
    subtotal = (subtotal + v) % 998244353
    sub.append(subtotal )

print(count[-1])
### BUGGY CODE ###

#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import fractions
N = int(input())
sum = 0
for i in range(N):
    sum += i
print(sum)

### FIXED CODE ###

#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import fractions
N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
dp = [0] * (N+2)
dp[1] = 1
e = 1e9 + 7
for i in range(2, N+2):
    if i-1 not in A:
        dp[i] = (dp[i-1] + dp[i-2]) % e
print(int(dp[-1]))

### FIXED CODE ###

n, m = map(int, input().split())
mod = 1e+9+7
dp = [0]*(n+1)
dp[0] = 1
isPass = [1]*(n+1)
for _ in range(m):
    a = int(input())
    isPass[a] = 0
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if isPass[j]:
            dp[j] += dp[i]
            dp[j] %= mod
print(int(dp[n]))
### BUGGY CODE ###

n,m = map(int,input().split())
a_ls = list(map(int, input().split()))
b_ls = []
for i in range(m):
    num, c = map(int,input().split())
    for _ in range(num):
        b_ls.append(c)
a_ls = a_ls + b_ls
a_ls.sort(reverse= True)
print(sum(a_ls[:n]))



### FIXED CODE ###

from collections import Counter
n,m = map(int,input().split())
a_ls = list(map(int, input().split()))
counter = Counter(a_ls)
for i in range(m):
    b,c = map(int,input().split())
    counter[c] += b

cards = sorted(counter.items(), key = lambda x:x[0], reverse=True)
rest = n
Sum = 0
for num, count in cards:
    if count < rest:
        Sum += num * count
        rest -= count
    else:
        Sum += rest * num
        break
print(Sum)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""

from collections import defaultdict

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

graph = defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = int(input())
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        dp[v][d] = t
        if d > 0:
            updatedp(v, t, d-1)
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print(col[dp[i][0]+1])


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
agc012 C
"""

from collections import defaultdict

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

graph = defaultdict(list)
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

q = int(input())
qlist = [tuple(map(int, input().split())) for i in range(q)]
qlist.reverse()

dp = [[-1]*11 for i in range(n+1)]
col = [0]


def updatedp(v, t, d):
    if dp[v][d] == -1:
        dp[v][d] = t
        if d > 0:
            updatedp(v, t, d-1)
            for u in graph[v]:
                updatedp(u, t, d-1)


t = 0
for v, d, c in qlist:
    col.append(c)
    updatedp(v, t, d)
    t += 1

for i in range(1, n+1):
    print(col[dp[i][0]+1])
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse = True)
q.sort(reverse = True)
r.sort(reverse = True)
pp = p[:x]
qq = q[:y]
if x+y <= c:
  rr = r[:(x+y)]
else:
  rr = r
ppqq = pp + qq
ppqq.sort()
for i in range(len(ppqq)):
  if ppqq[i] < rr[0]:
    ppqq[i] = rr[0]
    del rr[0]
    rr.append(0)
print(sum(ppqq))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse = True)
q.sort(reverse = True)
r.sort(reverse = True)
pp = p[:x]
qq = q[:y]
if x+y <= c:
  rr = r[:(x+y)]
else:
  rr = r
ppqqrr = pp + qq + rr
ppqqrr.sort(reverse = True)
print(sum(ppqqrr[:x+y]))
### BUGGY CODE ###

import fractions
N, K = map(int,input().split())
N = fractions.gcd(N,K)
min = N
for i in range(10**8):
    N = abs(N-K)
    if min > N:
        min = N
    if N == 0:
        min = 0
        break
print(min)

### FIXED CODE ###

#
N, K = map(int,input().split())
N  %= K
min = N
for i in range(10**6):
    N = abs(N-K)
    if min > N:
        min = N
    if N == 0:
        min = 0
        break
print(min)
### BUGGY CODE ###

N = list(input()) #e.g. 1432
buf_1 = 0 #入力の3桁目以上 - 2桁目以下 ,1400
buf_2 = 0 #X_1+...+X_6はこれ以下 , 入力の3桁目以上,14
counter = 0 #カウンタ

if len(N) <= 2 : #2桁以下なら終了
    print(0)
    exit()

#3桁以上なら続行
M = 10*int(N[-2]) + int(N[-1]) #入力の2桁目以下,32
for i in range(len(N) - 2) :
    buf_1 += (100*(10**i)) * int(N[-(i+3)]) 
buf_2 = int(buf_1/100) #入力の3桁目以上

##test##
#print('M is')
#print(M)
#print('buf_2 is')
#print(buf_2)
##test##

for j in range(int(M)+1) :
    for k in range(int(M/2)+1) :
        for l in range(int(M/3)+1) :
            for m in range(int(M/4)+1) :
                for n in range(int(M/5)+1) :
                    if M == (1*j+2*k+3*l+4*m+5*n) and (buf_2 -(j+k+l+m+n)) >= 0 :
                        ##test##
                        #print('set is')
                        #print(buf_2 -(j+k+l+m+n),j,k,l,m,n)
                        ##test##
                        print(1)
                        exit()
print(0)

### FIXED CODE ###

X = int(input())
for i in range(1,X+1) :
    for j in range(100*i,105*i+1) :
        if X % j == 0 :
            print(1)
            exit()
print(0)
### BUGGY CODE ###

S = str(input())
N = len(S)

ans = 0
for i in range(N-3):
    for j in range(i+4,N):
        if j == i+4:
            temp = int(S[i:j+1])
        else:
            temp = temp*10 + int(S[j])
        #rint(temp)
        if temp%2019 == 0:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter
S = str(input())
N = len(S)

#smod = [int(S[i:])%2019 for i in range(N)]
smod = [0]
tmod = 0
keta = 1
for i in range(N):
    temp = tmod + int(S[(N-1)-i])*keta
    #print(temp)
    tmod = temp%2019
    smod.append(tmod)
    keta = keta*10%2019


cmod = Counter(smod)
#print(cmod)

ans = 0
for i in cmod.values():
    ans += i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

class RollingHash():
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = (1 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)
        
        for i, char in enumerate(string):
            self.hash[i+1] = (self.hash[i] + ord(char)) * self.BASE % self.MOD
            self.pow[i+1] = (self.pow[i] * self.BASE) % self.MOD
            
    def get_hash(self, l, r):
        res = (self.hash[r] - self.hash[l] * self.pow[r-l] % self.MOD) % self.MOD
        return res

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

rh = RollingHash(s)

ans = 0
for length in range(n + 1):
    set_ = set()
    for l in range(n):
        # [l, l + length), [l + length, l + 2*length)
        if l + 2*length > n:
            break
        set_.add(rh.get_hash(l, l + length))
        tmp = rh.get_hash(l + length, l + 2*length)
        if tmp in set_:
            ans = length
            break

print(ans)

### FIXED CODE ###

def LRS(str): 
  
    n = len(str) 
    LCSRe = [[0 for x in range(n + 1)]  
                for y in range(n + 1)] 
  
    res = ""
    res_length = 0
  
    index = 0
    for i in range(1, n + 1): 
        for j in range(i + 1, n + 1): 
              
            if (str[i - 1] == str[j - 1] and
                LCSRe[i - 1][j - 1] < (j - i)): 
                LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
  
                if (LCSRe[i][j] > res_length): 
                    res_length = LCSRe[i][j] 
                    index = max(i, index) 
                  
            else: 
                LCSRe[i][j] = 0
  
    if (res_length > 0): 
        for i in range(index - res_length + 1, 
                                    index + 1): 
            res = res + str[i - 1] 
  
    return res 
  
n = int(input())
s = input()

print(len(LRS(s)))
### BUGGY CODE ###

import numpy as np

n,m=map(int,input().split())
x=list(map(int,input().split()))
n = min(n,len(x))

xs=sorted(x)
# xs

# def sabun(x,i):
#     return x[i+1]-x[i]

def sabun(x):
    a=np.array(x)
    return list(a[1:]-a[:-1])

# sabunx=[sabun(xs,i) for i in range(m-1)]

sabunx=sabun(xs)
# sabunx

for _ in range(n-1):
    sabunx.remove(sabunx[sabunx.index(sorted(sabunx,reverse=True)[0])])
#     print(sabunx)
    
print(sum(sabunx))

### FIXED CODE ###

import numpy as np

n,m=map(int,input().split())
x=list(map(int,input().split()))
n = min(n,len(x))

xs=sorted(x)
# xs

# def sabun(x,i):
#     return x[i+1]-x[i]

def sabun(x):
    a=np.array(x)
    return list(a[1:]-a[:-1])

# sabunx=[sabun(xs,i) for i in range(m-1)]

sabunx=sabun(xs)
# sabunx

print(sum(sorted(sabunx,reverse=True)[n-1:]))
### BUGGY CODE ###

s=input().split()
t=[int(i) for i in s]
while True:
    if t[0]==0:
        break
    else:
        print("#"*t[1])
        for i in range(t[0]-2):
            print("#"+"."*(t[1]-2)+"#")
        print("#"*t[1])
        print()


### FIXED CODE ###

while True:
    s=input().split()
    t=[int(i) for i in s]
    H=t[0]
    W=t[1]
    if H==0:
        break
    else:
        print("#"*W)
        for i in range(H-2):
            print("#"+"."*(W-2)+"#")
        print("#"*W)
        print()
### BUGGY CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n-1)
for i in range(n):
    tbl = [0]*n
    for j in range(i,n):
        tbl[j] = min(abs(j+1-i-1),abs(i+1-x)+1+abs(j+1-y))
    for i in range(1,n):
        ans[i-1] += tbl.count(i)
[print(i) for i in ans]


### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n)
for i in range(n):
    tbl = [0]*n
    for j in range(i,n):
        tbl[j] = min(abs(j+1-i-1),abs(i+1-x)+1+abs(j+1-y))
        ans[tbl[j]] += 1
[print(i) for i in ans[1:]]
### BUGGY CODE ###

from itertools import accumulate
n, m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(m):
    b, c = map(int,input().split())
    a += [c]*b
a.sort(reverse=True)
ac = list(accumulate(a))
print(ac[n-1])

### FIXED CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
bc = [list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x:x[1], reverse=True)

ad = 0
idx = 0
for b, c in bc:
    for i in range(min(b, n-idx)):
        if a[idx+i] < c:
            continue
        else:
            ad += c*i
            idx += i
            print(ad + sum(a[idx:]))
            exit()
    ad += c*min(b, n-idx)
    idx += min(b, n-idx)
print(ad + sum(a[idx:]))
### BUGGY CODE ###

#ABC125_C
import fractions
from functools import reduce
 
def gcd(nums):
    return reduce(fractions.gcd,nums)
 
N=int(input())
A=list(map(int,input().split()))
ans=1
       
for i in range(N):
    temp=A.copy()
    temp.remove(temp[i])
    if gcd(temp) > ans:
        ans=gcd(temp)
print(ans)

### FIXED CODE ###

#ABC125_C

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

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(x%y,y)

LCD=[A[0]]
RCD=[A[-1]]
for i in range(1,N):
    LCD.append(gcd(LCD[-1],A[i]))
    RCD.append(gcd(RCD[-1],A[-i-1]))

ans=1

if RCD[N-2]>ans:
    ans=RCD[N-2]

for i in range(1,N-1):
    if gcd(LCD[i-1],RCD[N-i-2])>ans:
        ans=gcd(LCD[i-1],RCD[N-i-2])

if LCD[N-2]>ans:
    ans=LCD[N-2]
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
ct = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if (S == (i + j + k)):
                ct += 1

print(ct)


### FIXED CODE ###

K, S = map(int, input().split())
ct = 0
for i in range(K + 1):
    for j in range(K + 1):
        a = S - i - j
        if 0 <= a <= K:
            ct += 1

print(ct)
### BUGGY CODE ###

from operator import mul
from functools import reduce

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

if ANS>10**18:
    print(-1)
else:
    print(ANS)

### FIXED CODE ###

import collections
import sys

N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1
if 0 in A_dict.keys():
    print("0")
    sys.exit()
    
for key, value in A_dict.items():
    ANS=ANS*(key**value)
    if ANS>10**18:
        print(-1)
        sys.exit()

print(ANS)
### BUGGY CODE ###

def acNumberInString(word):
  count = 0
  while len(word) > 0:
    index = word.find('AC')
    if index == -1:
      return count

    count += 1
    word = word[index+2:]
  return count

N, Q = map(int, input().split())
S = input()
for q in range(Q):
  start, end = map(int, input().split())
  tmp_word = S[start-1:end]
  print(acNumberInString(tmp_word))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
AC_numbers = [0]

# そうか、まず累積和で全体のACのかずを数えるのか
for i in range(1, N):
  if S[i-1] == 'A' and S[i] == 'C':
    AC_numbers.append(AC_numbers[i - 1] + 1)
  else:
    AC_numbers.append(AC_numbers[i-1])

# そこから引いて数を求める
for q in range(Q):
  start, end = map(int, input().split())
  count = AC_numbers[end-1] - AC_numbers[start-1]
  print(count)
### BUGGY CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools

s = stdin.readline().rstrip()
n = int(stdin.readline().rstrip())

flag = 0
prefix = []
suffix = []

for i in range(n):
    q = [x for x in stdin.readline().rstrip().split()]

    if len(q) == 1:
        flag = (flag + 1) % 2
    else:
        if (q[1] == "1" and flag == 0) or (q[1] == "2" and flag == 1):
            prefix.insert(0,q[2])
        else:
            suffix.append(q[2])

s = ''.join(prefix) + s + ''.join(suffix)

if flag == 1: s = ''.join(list(reversed(s)))
print (s)


### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

s = deque(stdin.readline().rstrip())
n = int(stdin.readline().rstrip())

flag = 0

for i in range(n):
    q = [x for x in stdin.readline().rstrip().split()]

    if len(q) == 1:
        flag = 1 - flag
    else:
        if (q[1] == "1" and flag == 0) or (q[1] == "2" and flag == 1):
            s.appendleft(q[2])
        else:
            s.append(q[2])

if flag == 1:
    s = ''.join(s)[::-1]
else:
    s = ''.join(s)
print (s)
### BUGGY CODE ###

import bisect
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
	if s[i] == "R":
		r.append(i+1)
	elif s[i] == "G":
		g.append(i+1)
	else:
		b.append(i+1)
ans = 0
for i in r:
	for j in g:
		ans += len(b)
		if i > j:
			k = j-abs(i-j)
			m = i+abs(i-j)
		else:
			k = j+abs(i-j)
			m = i-abs(i-j)
		if k in b:
			ans -= 1
		if m in b:
			ans -= 1
		if i > j:
			k = i-abs(i-j)
		else:
			k = i+abs(i-j)
		if k in b:
			ans -= 1
		l = (i+j)//2
		if abs(i-l) == abs(j-l):
			if l in b:
				ans -= 1
print (ans)

### FIXED CODE ###

import bisect
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
	if s[i] == "R":
		r.append(i+1)
	elif s[i] == "G":
		g.append(i+1)
	else:
		b.append(i+1)
ans = 0
if len(r) == 0 or len(g) == 0 or len(b) == 0:
	print (0)
	exit()
for i in r:
	for j in g:
		ans += len(b)
		if i > j:
			k = j-abs(i-j)
			m = i+abs(i-j)
		else:
			k = j+abs(i-j)
			m = i-abs(i-j)
		if k <= b[-1] and k >= b[0]:
			x = bisect.bisect_left(b,k)
			if x >= 0 and x < len(b):
				if b[x] == k:
					ans -= 1
		if m <= b[-1] and m >= b[0]:
			x = bisect.bisect_left(b,m)
			if x >= 0 and x < len(b):
				if b[x] == m:
					ans -= 1
		l = (i+j)//2
		if abs(i-l) == abs(j-l):
			x = bisect.bisect_left(b,l)
			if x >= 0 and x < len(b):
				if b[x] == l:
					ans -= 1
print (ans)
### BUGGY CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

#dp[i][j][direction] = (count, rem)
inf = 10**18
dp = [[[(inf, inf) for i in range(4)] for j in range(w)] for k in range(h)]

q = deque([((0, 0), x1-1, y1-1, i) for i in range(4)])
used = [[[False for l in range(4)] for i in range(w)] for j in range(h)]

for i in range(4):
    dp[x1-1][y1-1][i] = (0, 0)

while q:
    count, x, y, d = q.popleft()
    for dx, dy, dd in [(-1, 0, 2), (1, 0, 0), (0, -1, 1), (0, 1, 3)]:
        if 0 <= x+dx <= h-1 and 0 <= y+dy <= w-1:
            if g[x+dx][y+dy] == "@":
                continue

            if dd == d:
                if count[1] == k-1:
                    nextcount = (count[0]+1, 0)
                else:
                    nextcount = (count[0], count[1]+1)

            else:
                nextcount = (count[0]+1, 0)

            if dp[x+dx][y+dy][dd] < nextcount:
                continue
            dp[x+dx][y+dy][dd] = nextcount
            q.append((nextcount, x+dx, y+dy, dd))


ans = inf
for i in range(4):
    temp = dp[x2-1][y2-1][i][0]
    if dp[x2-1][y2-1][i][1] > 0:
        temp += 1
    ans = min(ans, temp)

if ans >= inf:
    ans = -1
print(ans)


### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())

g = []
for i in range(h):
    g.append(input())

inf = 10**9
dp = [[inf for j in range(w)] for k in range(h)]
dp[x1-1][y1-1] = 0
q = deque([(x1-1, y1-1)])

while q:
    x, y = q.popleft()
    if (x, y) == (x2-1, y2-1):
        break
    c = dp[x][y]
    for i in range(x+1, min(x+k+1, h)):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break


    for i in range(x-1, max(x-k-1, -1), -1):
        if g[i][y] == "@":
            break

        if dp[i][y] == inf:
           q.append((i, y))

        if dp[i][y] >= c + 1:
            dp[i][y] = c + 1
        else:
            break

    for j in range(y+1, min(y+k+1, w)):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break


    for j in range(y-1, max(y-k-1, -1), -1):
        if g[x][j] == "@":
            break

        if dp[x][j] == inf:
            q.append((x, j))

        if dp[x][j] >= c + 1:
            dp[x][j] = c + 1
        else:
            break

if dp[x2-1][y2-1] == inf:
    print(-1)
else:
    print(dp[x2-1][y2-1])
### BUGGY CODE ###

import pprint
H,W=map(int,input().split())
import copy
lastraw=["#"]*(W+2)
field=[["#"]*(W+2)]
for i in range(H):
  field.append(["#"]+list(input())+["#"])

field.append(lastraw)
maxmoves=0
#print(field)
saved_field=copy.deepcopy(field)

for i in range(H):
  for j in range(W):
    field=copy.deepcopy(saved_field)
    goal_point=(0,0)
    [sy,sx]=[j+1,i+1]
    [gy,gx]=[0,0]

    queue=[[sy,sx]]
    tests = ((-1,0),(0, 1),(1, 0),(0, -1))
    moves=0

    if field[sx][sy]=='#':
      queue=[]
    else:
      field[sx][sy]=0

    while True:
      if len(queue)==0:
        maxmoves=max(maxmoves,moves-1)
        break
      queue_next = []
      moves += 1
      #pprint.pprint(field)
      for y, x in queue:
        for ny, nx in tests:
          ty, tx = y + ny, x + nx
          if field[tx][ty] == '.' or field[tx][ty] ==moves:
            field[tx][ty] = moves
            queue_next.append((ty, tx))
      queue = queue_next
      if goal_point in queue:
        break
        #pprint.pprint(field)
        maxmoves=max(maxmoves,moves)
print(maxmoves)


### FIXED CODE ###

import pprint
H,W=map(int,input().split())
import copy
lastraw=["#"]*(W+2)
field=[["#"]*(W+2)]
for i in range(H):
  field.append(["#"]+list(input())+["#"])
 
field.append(lastraw)
maxmoves=0
#print(field)
saved_field=copy.deepcopy(field)
 
for i in range(H):
  for j in range(W):
    field=copy.deepcopy(saved_field)
    goal_point=(0,0)
    [sy,sx]=[j+1,i+1]
    [gy,gx]=[0,0]
 
    queue=[[sy,sx]]
    tests = ((-1,0),(0, 1),(1, 0),(0, -1))
    moves=0
 
    if field[sx][sy]=='#':
      queue=[]
    else:
      field[sx][sy]=0
 
    while True:
      if len(queue)==0:
        maxmoves=max(maxmoves,moves-1)
        break
      queue_next = []
      moves += 1
      #pprint.pprint(field)
      for y, x in queue:
        for ny, nx in tests:
          ty, tx = y + ny, x + nx
          if field[tx][ty] == '.':
            field[tx][ty] = moves
            queue_next.append((ty, tx))
      queue = queue_next
      if goal_point in queue:
        break
        #pprint.pprint(field)
        maxmoves=max(maxmoves,moves)
print(maxmoves)
### BUGGY CODE ###

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

ruiA, ruiB = [0], [0]

for i in range(N):
    ruiA.append(ruiA[i] + A[i])

for j in range(M):
    ruiB.append(ruiB[j] + B[j])

tmp = 0
for i in range(N + 1):
    for j in range(M + 1):
        if ruiA[i] + ruiB[j] <= K:
            tmp = max(tmp, i + j)

print(tmp)

### FIXED CODE ###

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

ruiA, ruiB = [0], [0]

for i in range(N):
    ruiA.append(ruiA[i] + A[i])

for j in range(M):
    ruiB.append(ruiB[j] + B[j])

t = False
for i in range(N + M + 1):
    if i <= N and ruiA[i] <= K:
        continue
    if i <= M and ruiB[i] <= K:
        continue
    if i > N and ruiA[N] + ruiB[i - N] <= K:
        continue
    if i > M and ruiA[i - M] + ruiB[M] <= K:
        continue

    t = False
    for j in range(0, i + 1):
        if j > M or i - j > N:
            continue
        if ruiA[i - j] + ruiB[j] <= K:
            t = True
            break

    if not t:
        print(i - 1)
        exit()

print(N + M)