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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m,k = map(int,input().split())
uf = UnionFind(n)
block = [[0 for i in range(n)] for i in range(n)]
count = [-1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
    block[a-1][b-1] = 1
    block[b-1][a-1] = 1
for i in range(k):
    c,d = map(int,input().split())
    block[c-1][d-1] = 1
    block[d-1][c-1] = 1
for i in range(n):
    for j in range(n):
        if uf.same(i,j) and block[i][j] == 0:
            count[i] += 1
print(" ".join(map(str,count)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
class UnionFind():
    def __init__(self, n):
        self.parents = [-1]*n
        self.count = [1]*n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.count[x] +=  self.count[y]
n,m,k = map(int,input().split())
uf = UnionFind(n)
block = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1) 
    block[a-1].append(b-1)
    block[b-1].append(a-1)
for i in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)
ans = []
for i in range(n):
    ans.append(uf.count[uf.find(i)]-len(block[i])-1)
print(" ".join(map(str,ans)))
### BUGGY CODE ###

import collections

def main():
    n = int(input())
    c = [[] for i in range(n)]
    count = 0
    lists =[]

    for num in range(n):
        c[num] = input()
        c[num] = ''.join(sorted(c[num]))

    for i in c:
        if i in lists:
            count = count + lists.count(i)
            lists.append(i)
        else:
            lists.append(i)

    print(count)


if __name__ == '__main__' :
    main()

### FIXED CODE ###

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in count_dict:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1

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

n = int(input())
list_n_ans = []
k = 0
ans = 0

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

while n >= 2:
    list_n_ans.append(n)
    n -= 2


if n % 2 == 0:
    while len(list_n_ans) + k > 4:
        k -= 5
        x = prime_factorize(list_n_ans[k])
        y = [s for s in  x if s == 5]
        ans += len(y)

print(ans)




### FIXED CODE ###

n = int(input())

if n % 2 == 1:
    print(0)
elif n % 2 == 0:
    ans = 0
    k = 10
    while n >= k:
        ans += n//k
        k *= 5
        
    print(ans)
### BUGGY CODE ###

n =int(input())

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

ls = []

ls.append(str(a[0]))
if n%2==0:
    for i in range(1,n):
        if i%2==0:
            ls.append(str(a[i]))
        else:
            ls.insert(0,str(a[i]))
else:
    for i in range(1,n):
        if i%2==1:
            ls.append(str(a[i]))
        else:
            ls.insert(0,str(a[i]))

print(" ".join(ls))

### FIXED CODE ###

n =int(input())
a = list(map(str,input().split()))
lss = []
lse = []
if n%2==0:
    for i in range(n//2):
        lss.append(a[2*i])
    for i in range(n//2):
        lse.append(a[n-(2*i+1)])

else:
    for i in range(n//2):
        lss.append(a[2*i+1])
    for i in range(n//2+1):
        lse.append(a[n-2*i-1])


ls = lse+lss

print(" ".join(ls))
### BUGGY CODE ###

Q = int(input())
n = 10 ** 5
L = [0] * 2 + [1] * (n-1)

for i in range(int(n ** 0.5)+1):
    if L[i] == 1:
        j = 2
        while i * j <= n:
            L[i*j] = 0
            j += 1
            
T = [0] * (n+1)
for i in range(3,n):
    if L[i] == 1 and L[(i+1) // 2] == 1:
        T[i] = 1    
    
for i in range(Q):
    l, r = map(int, input().split())
    print(sum(T[l:r+1]))

### FIXED CODE ###

from itertools import accumulate

Q = int(input())
n = 10 ** 5
L = [0] * 2 + [1] * (n-1)

for i in range(int(n ** 0.5)+1):
    if L[i] == 1:
        j = 2
        while i * j <= n:
            L[i*j] = 0
            j += 1
            
T = [0] * (n+1)
for i in range(3,n):
    if L[i] == 1 and L[(i+1) // 2] == 1:
        T[i] = 1    
s = list(accumulate(T))
    
for i in range(Q):
    l, r = map(int, input().split())
    print(s[r]-s[l-1])
### BUGGY CODE ###

import sys
import fractions
import functools
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = LIST()

res = 0
for i in range(n):
    aa = a[:i] + a[i+1:]
    gcd = functools.reduce(fractions.gcd, aa)
    res = max(res,gcd)

print(res)


### FIXED CODE ###

import sys
import fractions
import functools
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
a = LIST()

L = [0]*n
R = [0]*n
L[0] = INF
L[1] = a[0] 
R[n-1] = INF
R[n-2] = a[n-1]

GCDs = [0]*n

for i in range(2, n):
    L[i] = fractions.gcd(L[i-1], a[i-1])

for i in range(n-3,-1,-1):
    R[i] = fractions.gcd(R[i+1], a[i+1])

GCDs[0] = R[0]
GCDs[n-1] = L[n-1]

for i in range(1,n-1):
    GCDs[i] = fractions.gcd(L[i], R[i])

res = max(GCDs)

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

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    class segTree:
        def __init__(self,n):
            if bin(n).count("1") == 1:
                self.leaves = 2**(n.bit_length()-1)
            else:
                self.leaves = 2**n.bit_length()
            self.identity = set()
            self.tree = [set()]*(self.leaves*2)

        def merge(self,x,y):
            #ここにマージ処理を書く
            return set(list(x)+list(y))

        def update(self,i,x):
            i = i+self.leaves
            self.tree[i] = set(x)
            i >>= 1
            while i > 0:
                self.tree[i] = self.merge(self.tree[i*2],self.tree[i*2+1])
                i >>= 1

        def query(self,l,r):
            #[l:r)のクエリ結果を返す
            l = l + self.leaves
            r = r + self.leaves
            res = self.identity
            while l < r:
                if l&1:
                    res = self.merge(res,self.tree[l])
                    l += 1
                if r&1:
                    r -= 1
                    res = self.merge(res,self.tree[r])
                l >>= 1
                r >>= 1
            return len(res)


    N = int(input())
    S = list(input())
    Q = int(input())
    seg = segTree(N)
    for i in range(N):
        seg.update(i,S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            a = int(a)
            seg.update(a-1,b)
        else:
            a = int(a)
            b = int(b)
            print(seg.query(a-1,b))
main()

### FIXED CODE ###

"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [Counter([]) for _ in range(n+1)]
        
        def change(self,i,x,y):
            while i <= self.size:
                if x in self.tree[i]:
                    self.tree[i][x] -= 1
                if y not in self.tree[i]:
                    self.tree[i][y] = 1
                else:
                    self.tree[i][y] += 1
                i += i&-i
    
        def sum(self,i):
            s = Counter([])
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            cnt = 0
            return s


    N = int(input())
    S = list(input())
    Q = int(input())
    bit = BIT(N)
    for i in range(N):
        bit.change(i+1," ",S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            x = S[int(a)-1]
            S[int(a)-1] = b
            bit.change(int(a),x,b)
        else:
            a = int(a)
            b = int(b)
            count = bit.sum(b) - bit.sum(a-1)
            ans = 0
            for v in count.values():
                if v > 0:
                    ans += 1
            print(ans)
main()
### BUGGY CODE ###

n = int(input())
L_W = []

for i in range(0,n):
    L_W.append(input())
L_nat = set(L_W)
L_nat = sorted(L_nat)
max = 0
ans = []
for i in range(0,len(L_nat)):
    tmp = L_W.count(L_nat[i])
    if max < tmp:
        max = tmp
        ans = []
        ans.append(L_nat[i])
    elif max == tmp:
        ans.append(L_nat[i])

for i in range(0,len(ans)):
    print(ans[i])

### FIXED CODE ###

import collections as col

n = int(input())
L_W = []
for i in range(0,n):
    L_W.append(input())
 
dic = col.Counter(L_W)

dic_values_max = max(list(dic.values()))
 
max_key = [i for i, j in dic.items() if j == dic_values_max]
 
max_key.sort()
 
for k in max_key:
    print(k)
### BUGGY CODE ###

n = int(input())
l = len(str(n))

s = 0
while n != 0:
  r = n % 10
  s = (s + r) % 9
  n = n // 10

if s % 9 == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = list(map(int,input()))

s = sum(n)

if s % 9 == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

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

#nupList = [list(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(W + 1)] for _ in range(N + 2)]

for i in range(N):
    w, v = map(int, input().split())

    for j in range(w, W + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i][j - w] + v)
        dp[i + 2][j]  = dp[i + 1][j] 
            

print(dp[N][W])

### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)
 
    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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


res = 0
for i in range(N):
    if A[i] >= N:
        continue
    for j in range(i,N):
        if abs(i-j) == A[i] + A[j]:
            res += 1

print(res)


### FIXED CODE ###

# https://atcoder.jp/contests/abc166/tasks/abc166_e

"""
変数分離すれば互いに独立なので、
連想配列でO(N)になる。
"""


import sys
input = sys.stdin.readline
from collections import Counter

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

P = (j+1-A[j] for j in range(N))
M = (i+1+A[i] for i in range(N))

dic = Counter(P)

res = 0
for m in M:
    res += dic.get(m,0)

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

S = list(input())
count = 0
flag = 1

while flag == 1:
    flag = 0
    for i in range(len(S)-1):
        if S[i] == 'B' and S[i+1] == 'W':
            S[i], S[i+1] = S[i+1], S[i]
            count += 1
            flag = 1
        
print(count)

### FIXED CODE ###

S = list(input())
posi = 0
count = 0

for i in range(len(S)):
    if S[i] == 'W':
        count += i - posi
        posi += 1

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

a, b = map(int, input().split())
g = []
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a%b)
g.append(gcd(a,b))
for i in range(1,g[0]):
    if not a%i and not b%i:
        g.append(i)
g.append(g[0])
l = len(g)
c = 0
for i in range(2,l-1):
    for j in range(i+1,l):
        if g[i] != 0 and not g[j]%g[i]:
            g[j]=0
for i in range(1,l):
    if g[i]!=0:
        c+=1
print(c)

### FIXED CODE ###

a, b = map(int, input().split())
def factor(n):
    a = []
    while not n%2:
       n//=2
       a.append(2)
    i = 3
    while i*i<=n:
        while not n%i:
            n//=i
            a.append(i)
        i+=2
    if n>1:
        a.append(n)
    return a
print(len(set(factor(a))&set(factor(b)))+1)
### BUGGY CODE ###

X = int(input())

CNT = 2000

for a in range(-CNT, CNT):
    for b in range(-CNT, CNT):
        if X == a ** 5 - b ** 5:
            print(a, b)
            exit()


### FIXED CODE ###

X = int(input())

CNT = 500

for a in range(-CNT, CNT):
    for b in range(-CNT, CNT):
        if X == a ** 5 - b ** 5:
            print(a, b)
            exit()
### BUGGY CODE ###

def main():
    n = int(input())
    # h, w, k = map(int, input().split())
    # a = list(map(int, input().split()))
    # s = input()
    while True:
        c = 360
        if c % n == 0:
            print(c // n)
            exit()
        c *= 2


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    # n = int(input())
    # h, w, k = map(int, input().split())
    # a = list(map(int, input().split()))
    # s = input()
    x = int(input())
    i = 1
    while (x*i) % 360 != 0:
        i += 1
    print(i)


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

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

All_list = list(map(int, input().split()))

for _ in range(M):
    Bi, Ci = map(int, input().split())
    All_list.extend([Ci for _ in range(Bi)])

All_list.sort(reverse=True)

print(sum(All_list[:N]))


### FIXED CODE ###

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

A_list = list(map(int, input().split()))

All_dict = {}

for Ai in A_list:
    if Ai not in All_dict.keys():
        All_dict[Ai] = 0
    All_dict[Ai] += 1
    
for _ in range(M):
    Bi, Ci = map(int, input().split())
    if Ci not in All_dict.keys():
        All_dict[Ci] = 0
    All_dict[Ci] += Bi
counter = 0
res = 0
all_card_val = list(All_dict.keys())
all_card_val.sort(reverse=True)
for card_val in all_card_val:
    possesion = All_dict[card_val]
    if counter + possesion <= N:
       res += card_val * possesion
       counter += possesion
    else:
        res += card_val * (N - counter)
        break

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

n=int(input())
a=list(map(int,input().split()))
 
a.sort()
b=list(set(a))
c=0
for i in range(len(b)):  
  if a.count( b[i] ) != b[i]:
    er = a.count( b[i] ) - b[i]
    if er<0:
      er = a.count( b[i] )
    if er>0:
      c+=er
print(c)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
counter=Counter(a)
b=list(set(a))
c=0
for i in b:
    k =  counter[i]
    c+= k-i if k-i>=0 else k
print(c)
### BUGGY CODE ###

n=int(input())
a="abcdefghijklmnopqrstuvwxyz"
b=""
i=1
while n/26>0:
  if n%26==0:
    b="z"+b
  else:
    b=a[n%26-1]+b
    n=n//26
print(b)

### FIXED CODE ###

n=int(input())
a="zabcdefghijklmnopqrstuvwxy"
b=""
while n/26>0:
  b=a[n%26]+b
  n=(n-1)//26
print(b)
### BUGGY CODE ###

import copy

def saiki(s,used,n):
  if int(s) > n:
    return 0

  count = 0
  arr = ['7','5','3']
  if len(used) == 3:
    count += 1
  
  for c in arr:
    cp_used = copy.deepcopy(used)
    cp_used.add(c)
    count += saiki(s+c,cp_used,n)
    
  return count
  

n = int(input())

ans = 0
array = []

used = set()
ans = saiki('7',set('7'),n) + saiki('5',set('5'),n) + saiki('3',set('3'),n)
print(ans)

### FIXED CODE ###

import copy
from collections import deque

n = int(input())

ans = 0
array = ['7','5','3']

count = 0
d = deque()
d.append(([],set()))

while len(d) != 0:
  s,used = d.pop()
  if len(s) != 0 and int(''.join(s)) > n:
    continue
  
  if len(used) == 3:
    count += 1  
    
  for c in array:
    cp_s = copy.deepcopy(s)
    cp_s.append(c)    
    if len(used) == 3:
      d.append((cp_s,used))
    
    else:
      cp_used = copy.deepcopy(used)
      cp_used.add(c)
      d.append((cp_s,cp_used))
  
print(count)
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
Y = sorted(list(set(X)))
Z = [X.count(y) for y in Y]
cnt = 0
for i in range(len(Y)):
    cnt += Z[i] 
    if cnt == N//2:
        cnt = Y[i+1] - Y[i]
        break
    elif cnt > N//2:
        cnt = 0
        break
print(cnt)

### FIXED CODE ###

N = int(input())
X = sorted(list(map(int,input().split())))
print(X[N//2]-X[N//2-1])
### BUGGY CODE ###

S=list(input())
i=0
count=0
while True:
    if S[i]=='B' and S[i+1]=='W':
        S[i]='W'
        S[i+1]='B'
        i-=1
        count+=1
        if i<0:
            i=0
        continue
    if i > len(S)-3:
        print(count)
        break
    i+=1
    


### FIXED CODE ###

s = input()
ans = 0
b = 0
for c in s:
    if c == 'W':
        ans += b
    elif c == 'B':
        b += 1
print(ans)
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
from copy import deepcopy
N=int(input())
l=list(map(int,input().split()))
dp=[]
for i in range(N):
	t=deepcopy(l)
	t.pop(i)
	dp.append(reduce(gcd,t))
print(max(dp))

### FIXED CODE ###

from fractions import gcd
N=int(input())
L=list(map(int,input().split()))
l=[0]*(N+1)
r=[0]*(N+1)
ans=0
for i in range(N):
  l[i+1]=gcd(L[i],l[i])
  r[N-i-1]=gcd(L[N-i-1],r[N-i])
for i in range(N):
  ans=max(ans,gcd(l[i],r[i+1]))
print(ans)
### BUGGY CODE ###

N=int(input())
c=1
for i in range(N):
  c *= i+1
c = c % (10**9+7)
print(c)

### FIXED CODE ###

N=int(input())
c=1
for i in range(N):
  c *= i+1
  c = c % (10**9+7) # ここで、掛け算のスケールを減らすのか！

print(c)
### BUGGY CODE ###

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

from itertools import permutations, combinations,combinations_with_replacement,product
L = list(combinations(range(N), 3))   #nCr
A=[]
for i in L:
  X = S[i[0]]+S[i[1]]+S[i[2]]
  if X not in A:
    A.append(X)
print(len(A))

### FIXED CODE ###

N = int(input())
S = input()
Pin = ['{0:03d}'.format(a) for a in range(0,1000)]
cnt = 0
for i in Pin:
  S1 = S
  A1 = S1.find(i[0])
  if A1!=-1:
    S2 = S1[(A1+1):]
    A2 = S2.find(i[1])
    if A2!=-1:
      S3 = S2[(A2+1):]
      A3 = S3.find(i[2])
      if A3!=-1:
        cnt +=1
print(cnt)
### BUGGY CODE ###

def verify_anagrams(w1, w2):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(" ", ""), y)))
    return f(w1) == f(w2)


N = int(input())
s = [input() for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if verify_anagrams(s[i], s[j]):
            ans += 1
print(ans)


### FIXED CODE ###

from operator import mul
from functools import reduce
import collections


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    elif r < 0:
        return 0
    numer = reduce(mul, range(n, n - r, -1))
    denom = reduce(mul, range(1, r + 1))
    return numer // denom


N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
ans = 0
for si in set(s):
    n = c[si]
    ans += cmb(n, 2)
print(ans)
### BUGGY CODE ###

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

dp = []
for i in range(m+1):
    dp.append([0 for j in range(n+1)])

def f(fn):
    global dp, a
    for i in range(1,m+1):
        for j in range(1,n+1):
            dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + fn(a[j-1]))

ans = []
f(lambda x: x[0]+x[1]+x[2])
ans.append(dp[m][n])
f(lambda x: x[0]+x[1]-x[2])
ans.append(dp[m][n])
f(lambda x: x[0]-x[1]+x[2])
ans.append(dp[m][n])
f(lambda x: x[0]-x[1]-x[2])
ans.append(dp[m][n])
f(lambda x: -x[0]+x[1]+x[2])
ans.append(dp[m][n])
f(lambda x: -x[0]+x[1]-x[2])
ans.append(dp[m][n])
f(lambda x: -x[0]-x[1]+x[2])
ans.append(dp[m][n])
f(lambda x: -x[0]-x[1]-x[2])
ans.append(dp[m][n])

print(max(ans))


### FIXED CODE ###

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

dp = []
for i in range(m+1):
    dp.append([0 for j in range(n+1)])

def f(fn):
    global dp, a
    for i in range(1,m+1):
        for j in range(i,n+1):
            if j == i:
                dp[i][j] = sum(map(fn, a[:j]))
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + fn(a[j-1]))

ans = []
f(lambda x: x[0]+x[1]+x[2])
ans.append(dp[m][n])
f(lambda x: x[0]+x[1]-x[2])
ans.append(dp[m][n])
f(lambda x: x[0]-x[1]+x[2])
ans.append(dp[m][n])
f(lambda x: x[0]-x[1]-x[2])
ans.append(dp[m][n])
f(lambda x: -x[0]+x[1]+x[2])
ans.append(dp[m][n])
f(lambda x: -x[0]+x[1]-x[2])
ans.append(dp[m][n])
f(lambda x: -x[0]-x[1]+x[2])
ans.append(dp[m][n])
f(lambda x: -x[0]-x[1]-x[2])
ans.append(dp[m][n])

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

import numpy as np
from itertools import permutations
from math import factorial

N = int(input())

points = []
for i in range(0,N):
    points.append(list(map(int,input().split())))

p = permutations(points,N)

average = 0
for j in p:
    for k in range(0,len(j)-1):
        average += np.linalg.norm(np.array(j[k+1])-np.array(j[k]))

print('{:.10f}'.format(average/factorial(N)))

### FIXED CODE ###

from itertools import permutations
from math import factorial

N = int(input())

points = []
for i in range(0,N):
    points.append(list(map(int,input().split())))

p = permutations(points,N)

average = 0

for j in p:
    for k in range(0,len(j)-1):
        average += ((j[k+1][0] -j[k][0])**2 + (j[k+1][1] -j[k][1])**2)**0.5

print('{:.10f}'.format(average/factorial(N)))
### BUGGY CODE ###

def go(s,b):
    count=-1
    for i in b:
        if s>=i:
           count+=1

    return count

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

a= (map(int,input().split(" ")))
b= (map(int,input().split(" ")))

c,d=[],[]
s=0
for i in a:
   s+=i
   c.append(s)
s=0
for i in b:
   s+=i
   d.append(s)

mx=0
for i,j in enumerate(c):
    if j<=k:
        for q,w in enumerate(d):
            if j+w<=k:
                if i+q+2>mx:
                    mx=i+q+2
            else:
                break
        if i+1>mx:
            mx=i+1
    else:
        break
for q,w in enumerate(d):
    if w<=k:
        if q+1>mx:
            mx=1+q
    else:
        break
print(mx)


### FIXED CODE ###

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

a = [0]+list(map(int, input().split(" ")))
b = [0]+list(map(int, input().split(" ")))

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

j,mx= m,0
for i in range(n+1):
    if a[i]>k:
        break
    while(b[j]>k-a[i]):
        j-=1
    if (i+j>mx):
        mx=i+j
print(mx)