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

import copy
from collections import deque
H, W = map(int, input().split())
M = [['#' == x for x in input()] for _ in range(H)]

black = deque()
for i in range(H):
  for j in range(W):
    if M[i][j]:
      black.append((i, j))

ans = 0
while True:
  ans += 1
  next_black = deque()
  while black:
    bi, bj = black.popleft()
    if bi - 1 >= 0 and not M[bi - 1][bj]:
      M[bi - 1][bj] = True
      next_black.append((bi - 1, bj))
    if bj - 1 >= 0 and not M[bi][bj - 1]:
      M[bi][bj - 1] = True
      next_black.append((bi, bj - 1))
    if bi + 1 < H and not M[bi + 1][bj]:
      M[bi + 1][bj] = True
      next_black.append((bi + 1, bj))
    if bj + 1 < W and not M[bi][bj + 1]:
      M[bi][bj + 1] = True
      next_black.append((bi, bj + 1))
  if next_black:
     black = copy.copy(next_black)
  else:
     break
print(ans - 1)


### FIXED CODE ###

from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)

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

import sys


def B(T):
    global S, Z, D
    _last = [0] * Z
    cnt = 0
    for d in range(1, D + 1):
        t = T[d]
        _last[t] = d
        up = S[d][t]
        down = sum(C[i] * (d - _last[i]) for i in range(Z))
        cnt += up - down
    return cnt


def checkScore(r):
    global D
    L = last[r]
    rst = 0
    for d in range(1, D + 1):
        down = C[r] * (d - L[d])
        up = S[d][r] if down == 0 else 0
        rst += up - down
    return rst


Z = 26
D = int(input())
C = list(map(int, input().split()))
S = [tuple([0] * Z)]
S += [tuple(map(int, input().split())) for _ in range(D)]
T = [None] + [int(input()) - 1 for _ in range(D)]

M = int(input())
Q = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]


last = [[0] * (D + 1) for _ in range(Z)]
V = [0] * Z
for d in range(1, D + 1):
    t = T[d]
    for p in range(Z):
        last[p][d] = last[p][d - 1]
    last[t][d] = d
for p in range(Z):
    V[p] = checkScore(p)

score = sum(V)

for d, q in Q:
    d += 1

    p = T[d]
    T[d] = q

    for r, L in ((p, last[p]), (q, last[q])):
        for e in range(1, D + 1):
            L[e] = L[e - 1] if r != T[e] else e

    score -= V[p] + V[q]
    V[p] = checkScore(p)
    V[q] = checkScore(q)
    score += V[p] + V[q]
    # print(score == B(T), score, B(T))
    print(B(T))


### FIXED CODE ###

import sys


def B(T):
    global S, Z, D
    _last = [0] * Z
    cnt = 0
    for d in range(1, D + 1):
        t = T[d]
        _last[t] = d
        up = S[d][t]
        down = sum(C[i] * (d - _last[i]) for i in range(Z))
        cnt += up - down
    return cnt


def checkScore(r):
    global D, last
    L = last[r]
    rst = 0
    for d in range(1, D + 1):
        down = C[r] * (d - L[d])
        up = S[d][r] if L[d] == d else 0
        rst += up - down
    return rst


Z = 26
D = int(input())
C = list(map(int, input().split()))
S = [tuple([0] * Z)]
S += [tuple(map(int, input().split())) for _ in range(D)]
T = [None] + [int(input()) - 1 for _ in range(D)]

M = int(input())
Q = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]


last = [[0] * (D + 1) for _ in range(Z)]
V = [0] * Z
for d in range(1, D + 1):
    t = T[d]
    for p in range(Z):
        last[p][d] = last[p][d - 1]
    last[t][d] = d
for p in range(Z):
    V[p] = checkScore(p)

score = sum(V)

for d, q in Q:
    d += 1

    p = T[d]
    T[d] = q

    for r, L in ((p, last[p]), (q, last[q])):
        for e in range(1, D + 1):
            L[e] = L[e - 1] if r != T[e] else e

    score -= V[p] + V[q]
    V[p] = checkScore(p)
    V[q] = checkScore(q)
    score += V[p] + V[q]
    # # if M > 10 ** 4:
    #     print(score)
    # else:
    #     print(B(T))
    print(score)
### BUGGY CODE ###

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

if n%k == 0:
    ans = 0
else:
    for i in range(-k,k+1):
        if (i%k == n%k and i < 0):
            nega = -i
        elif (i%k == n%k and i >= 0):
            posi = i
    ans = (min(nega, posi))
print(ans)

### FIXED CODE ###

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

a = n%k
b = abs(a-k)
print(min(n,a,b))
### BUGGY CODE ###

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

if M % N == 0:
    ans = int(M/N)

elif M / N > 100000000:
    ans = 1

else:
    amax = M // N
    for i in range(amax, 0, -1):
        if (M - (i * N)) % i == 0:
            ans = i
            break

print(ans)

### FIXED CODE ###

import math

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

# N = 100000
# M = 1000000000

def pfac(n):
    values = [1, n]
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            values.append(i)
            values.append(n // i)
    return values

L = pfac(M)
L = [i for i in L if i * N <= M]

ans = []

for i in L[::-1]:
    # if (M - (N * i)) % i == 0:
    if M % i == 0:
        ans.append(i)

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

import numpy as np

n, k = map(int, input().split())
p_list = [int(i) for i in input().split()]

p_list = np.array(p_list)
b = np.ones(k)/k
p2 = np.convolve(p_list, b, mode='valid')
index = np.argmax(p2)
kitaichi = k/2 + k*p2[index]/2
print(kitaichi)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
p_list = [int(i) for i in input().split()]

p_list = [0] + p_list

cum_list = []
p_sum = 0
for p in p_list:
    p_sum += p
    cum_list.append(p_sum)
    
cum_list = np.array(cum_list)
sum_list = cum_list[k:]-cum_list[:-k]
index = np.argmax(sum_list)

kitaichi = k/2 + sum_list[index]/2

print(kitaichi)
### BUGGY CODE ###

n = int(input())
s = input()
ans = []

for i in range(n + 1):
    b = s[0:i].count('#')
    w = s[i+1:n].count('.')
    ans.append(b + w)

print(min(ans))

### FIXED CODE ###

n = int(input())
s = input()
b = [0] * (n + 1)
w = [0] * (n + 1)

for i in range(n):
    if s[i] == '#':
        b[i + 1] = b[i] + 1
    else:
        b[i + 1] = b[i]

for i in range(n - 1, -1, -1):
    if s[i] == '.':
        w[i] = w[i + 1] + 1
    else:
        w[i] = w[i + 1]

ans = [vb + vw for vb, vw in zip(b, w)]
print(min(ans))
### BUGGY CODE ###

import queue
n = int(input())
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int,input().split())
    u,v = u-1,v-1
    way[u].append(v)
    way[v].append(u)

stst = [[] for i in range(n)]
stst[0] = [a[0]]
q = queue.Queue()
for i in way[0]:
    q.put((i,0))

while not q.empty():
    i,pi = q.get()
    for j in way[i]:
        if pi == j:
            continue
        q.put((j,i))
    stst[i] = stst[pi]+[a[i]]

def lenlis(arr):
    mns = [10**18 for i in range(len(arr)+2)]
    mns[0] = 0
    mai = 0
    for i in arr:
        for j in range(len(arr)):
            if i > mns[j]:
                if i < mns[j+1]:
                    mns[j+1] = i
                    break
            else:
                break
    return mns.index(10**18)-1

for i in stst:
    print(lenlis(i))


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)



def main():
    n = int(ipt())
#    n = 2*10**5
    a = [int(i) for i in ipt().split()]
#    a = [i+1 for i in range(n)]
    way = [[] for i in range(n)]
    for i in range(n-1):
        u,v = map(int,ipt().split())
        u -= 1;v -= 1
        way[u].append(v)
        way[v].append(u)
#    way = [[i-1,i+1] for i in range(n)]
#    way[0] = [1]
#    way[n-1] = [n-2]
    ans = [0]*n
    dp = [10**18]*n
    stk = []

    def solve(ni,pi):
        ai = a[ni]
        pt = bisect.bisect_left(dp,ai)
        stk.append((pt,dp[pt]))
        dp[pt] = ai
        ans[ni] = bisect.bisect_left(dp,10**18-1)
        for i in way[ni]:
            if i == pi:
                continue
            else:
                solve(i,ni)
        pl,val = stk.pop()
        dp[pl] = val
        return None

    solve(0,-1)

    for i in ans:
        print(i)

    return None

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

import math
from operator import mul
from functools import reduce
x,y = map(int, input().split())
n = (x+y)//3
r = (2*x-y)//3
mod = 10**9+7

def combinations_count(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

if (x+y)%3!=0:
    print(0)
elif 2*x-y<0:
    print(0)
elif -x+2*y<0:
    print(0)
else:
    # print((math.factorial((x+y)//3)//(math.factorial((2*x-y)//3)*math.factorial((2*y-x)//3)))%mod)
    print(combinations_count(n,r)%mod)


### FIXED CODE ###

# import math
# from operator import mul
# from functools import reduce
x,y = map(int, input().split())
n = (x+y)//3
r = (2*x-y)//3
mod = 10**9+7
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if (x+y)%3!=0:
    print(0)
elif 2*x-y<0:
    print(0)
elif -x+2*y<0:
    print(0)
else:
    # print((math.factorial((x+y)//3)//(math.factorial((2*x-y)//3)*math.factorial((2*y-x)//3)))%mod)
    # print(combinations_count(n,r)%mod)
    print(cmb(n,r,mod))
### BUGGY CODE ###

num = int(input())

print(sum(range(1, num + 1)[:-1]))

### FIXED CODE ###

num = int(input())

print(((num - 1) * num) // 2)
### BUGGY CODE ###

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
x=[]
y=[]
for i,j in z:
    x.append(i)
    y.append(j)
x.sort()
y.sort()
a=10**20
for i,l in enumerate(x):
    for r in x[i+1:]:
        for v,d in enumerate(y):
            for u in y[v+1:]:
                if sum(l<=i<=r and d<=j<=u for i,j in z)>=k:
                    a=min(a,(r-l)*(u-d))
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
z=[list(map(int,input().split()))for _ in range(n)]
z.sort()
a=10**20
for i in range(n):
    for j in range(i+1,n):
        x=z[j][0]-z[i][0]
        l=sorted(t[1]for t in z[i:j+1])
        for u,v in zip(l,l[k-1:]):
            a=min(a,x*(v-u))
print(a)
### BUGGY CODE ###

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


for i in range(N):
    ans = 0
    pos = 0
    for j in range(len(A)):
        if j == i:
            continue
        ans += abs(A[j]-pos)
        #print('ans', ans)#debug
        pos = A[j]
        #print('pos:', pos)#debug
    ans += abs(pos)
    print(ans)

### FIXED CODE ###

N = int(input())
A = [0]

Astr = input().split()

for i in Astr:
    A.append(int(i))

A.append(0)

ans = 0
pos = 0
for i in range(len(A)):
    if i == 0:
        continue
    ans += abs(A[i]-pos)
    pos = A[i]

for i in range(len(A)):
    if i == 0 or i == len(A)-1:
        continue
    print(ans-abs(A[i]-A[i-1])-abs(A[i+1]-A[i])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[0]*n
b=[0]*n
ans=0
temp=0
for i in range(n):
  at,bt=map(int,input().split())
  a[i]=at
  b[i]=bt
import numpy as np
a=np.array(a)
b=np.array(b)
while temp<m:
  t=np.argmin(a)
  if temp+b[t]>=m:
    ans=ans+a[t]*(m-temp)
    break
  else:
    ans=ans+a[t]*b[t]
    temp=temp+b[t]
    a=np.delete(a,t)
    b=np.delete(b,t)
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
t=[0]*n
ans=0
temp=0
for i in range(n):
  at,bt=map(int,input().split())
  t[i]=[at,bt]
t.sort()
i=0
while True:
  if temp+t[i][1]>=m:
    ans=ans+t[i][0]*(m-temp)
    break
  else:
    ans=ans+t[i][0]*t[i][1]
    temp=temp+t[i][1]
    i=i+1
print(ans)
### BUGGY CODE ###

def light(s,i,j):
    res=1
    k=0
    while i-k-1>=0 and not s[i-k-1][j]:
        k+=1
    res+=k
    k=0
    while i+k+1<=H-1 and not s[i+k+1][j]:
        k+=1
    res+=k
    k=0
    while j-k-1>=0 and not s[i][j-k-1]:
        k+=1
    res+=k
    k=0
    while j+k+1<=W-1 and not s[i][j+k+1]:
        k+=1
    res+=k
    return res

H,W=map(int,input().split())
s=[]
for i in range(H):
    si=[]
    Si=input()
    for j in range(W):
        si.append(Si[j]=='#')
    s.append(si)

ans=0
for i in range(H):
    for j in range(W):
        if not s[i][j]:
            ans=max(ans,light(s,i,j))

print(ans)


### FIXED CODE ###

H,W=map(int,input().split())
s=[]
for i in range(H):
    si=[]
    Si=input()
    for j in range(W):
        si.append(Si[j]=='.')
    s.append(si)

# 左に照らした場合 行ごとに見てゆく
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if j==0 and s[i][j]:
            L[i][j]=1
        elif s[i][j]:
            L[i][j]=L[i][j-1]+1

# 右に照らした場合 行ごとに見てゆく
R=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in reversed(range(W)):
        if j==W-1 and s[i][j]:
            R[i][j]=1
        elif s[i][j]:
            R[i][j]=R[i][j+1]+1

# 上に照らした場合 列ごとに見てゆく
U=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in range(H):
        if i==0 and s[i][j]:
            U[i][j]=1
        elif s[i][j]:
            U[i][j]=U[i-1][j]+1

# 下に照らした場合 列ごとに見てゆく
D=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in reversed(range(H)):
        if i==H-1 and s[i][j]:
            D[i][j]=1
        elif s[i][j]:
            D[i][j]=D[i+1][j]+1

ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

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

import sys
input = sys.stdin.readline

N=int(input())
A=[0]*N
B=[0]*N
C=[0]*N

for i in range(N):
  A[i],B[i] = map(int,input().split())
  C[i]=(A[i],B[i],A[i]-B[i],B[i]-A[i])

t=0
a=0

for i in range(N):
  if i%2==0: #高橋くんの番
    C.sort(key= lambda x: x[3],reverse=True)
    C.sort(key= lambda x: x[0],reverse=True)
    #print(i,C)
    t += C.pop(0)[0]
  if i%2==1: #青木さんの番
    C.sort(key= lambda x: x[2],reverse=True)
    C.sort(key= lambda x: x[1],reverse=True)
    #print(i,C)
    a += C.pop(0)[1]
  #print(i,C)
print(t-a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[0]*N
B=[0]*N
C=[0]*N

for i in range(N):
  A[i],B[i] = map(int,input().split())
  C[i]=(A[i],B[i],A[i]+B[i])

t=0
a=0

C.sort(key= lambda x: x[2],reverse=True)
#print(C)
#C.sort(key= lambda x: x[0],reverse=True)
for i in range(N):
  if i%2==0:
    t += C[i][0]
  else:
    a += C[i][1]

print(t-a)
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 8)


N, K = map(int, input().split())
M = 998244353
S = set()
for _ in range(K):
    L, R = map(int, input().split())
    for i in range(L, R + 1):
        S.add(i)


@lru_cache(None)
def dp(i):
    if i < 1:
        return 0
    elif i == 1:
        return 1
    else:
        res = 0
        for d in S:
            res += dp(i - d)
            res %= M
        return res
print(dp(N) % M)

### FIXED CODE ###

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

dp = [0] * N
dp[1] = 1
prefix = [1] * N

for i in range(1, N):
    cur = 0
    for L, R in K:
        a = i - R
        b = i - L
        if b < 0:
            continue
        cur += prefix[b] - (prefix[a - 1] if a - 1 >= 0 else 0)
    dp[i] = cur % M
    prefix[i] = prefix[i - 1] + dp[i]
    prefix[i] %= M
print(dp[N - 1])
### BUGGY CODE ###

_ = input()
seq = list(map(int,input().split()))

seq1 = seq[::2]
seq2 = seq[1::2]

if len(set(seq)) == 1:
    print(min(len(seq1),len(seq2)))
    exit()
    
def count_dictonary(seq):
    ret_dict={}
    for item in seq:
        if item not in ret_dict:
            ret_dict[item] = 1
        else:
            ret_dict[item]+=1
    return ret_dict

seq_dict1 = count_dictonary(seq1)
seq_dict2 = count_dictonary(seq2)

min_change=len(seq)
for i1 in seq_dict1:
    for i2 in seq_dict2:
        ch1 = len(seq1) - seq_dict1[i1]
        ch2 = len(seq2) - seq_dict2[i2]
        #print(i1,i2,ch1,ch2,ch1+ch2)
        change_ = ch1+ch2
        if(min_change > ch1+ch2):
            min_change = ch1+ch2
            
print(min_change)

### FIXED CODE ###

_ = input()
seq = list(map(int,input().split()))
 
seq1 = seq[::2]
seq2 = seq[1::2]
 
if len(set(seq)) == 1:
    print(len(seq2))
    exit()
    
def count_dictonary(seq):
    ret_dict={}
    for item in seq:
        if item not in ret_dict:
            ret_dict[item] = 1
        else:
            ret_dict[item]+=1
    return ret_dict
 
def modes(counting_dict):
    #(11,2),(2,1),(3,3)
    ret={}
    for item in counting_dict.items():
        no, count = item
        if counting_dict[no] in ret:
            ret[count].append(no)
        else:
            ret[count]=[no]
            
    return ret
 
 
counting1 = count_dictonary(seq1)
counting2 = count_dictonary(seq2)
 
modes1 = sorted(modes(counting1).items(),reverse=True)
modes2 = sorted(modes(counting2).items(),reverse=True)
 
min_change=len(seq)
if modes1[0][1] != modes2[0][1] or len(modes1[0][1]) >=2 or len(modes2[0][1]) >=2:
    min_change = (len(seq1) - modes1[0][0]) + (len(seq2) - modes2[0][0])
else:
    m01=len(seq)
    m10=len(seq)
    if len(modes2) !=1:
        m01 =  (len(seq1) - modes1[0][0]) + (len(seq2) - modes2[1][0])
    if len(modes1) !=1:
        m10 =  (len(seq1) - modes1[1][0]) + (len(seq2) - modes2[0][0])
    min_change = min(m01,m10)
    
print(min_change)
### BUGGY CODE ###

def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
p = 10 ** 9 + 7
ans = 0
for i in range(n - k + 1):
    ans += (a[n - i - 1] - a[i]) * comb(n - 1 - i, k - 1, p)
    ans %= p
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
a.sort()
b = 1
ans = 0
for i in range(k - 1, n):
    ans += b * (a[i] - a[n - i - 1])
    ans %= mod
    b = (i + 1) * b
    c = i + 1 - (k - 1)
    b = pow(c, mod - 2, mod) * b % mod
print(ans)
### BUGGY CODE ###

N = input()
N = int(N)
k =[]
x = []
for i in range(0,N):
    a = input()
    k.append(a)
for j in k:
    if j not in x:
        x.append(j)
m = len(x)
print (m)

### FIXED CODE ###

N = int(input())
k = set()
for _ in range(N):
    k.add(input())
print (len(k))
### BUGGY CODE ###

import sys
from collections import deque


def _tsundoku(n, m, k, a, b):
    # print(f'{a=}')
    # print(f'{b=}')
    a_len = len(a)
    b_len = len(b)

    ans = [0, 0, 0]

    L = []
    d = deque()
    d.append((0, 0, 0))
    while d:
        # print(d, L)
        a_readed, b_readed, t = d.popleft()
        if not (a_len > a_readed and t + a[a_readed] <= k) and not (b_len > b_readed and t + b[b_readed] <= k):
            # print(a_readed, b_readed, t)
            L.append(a_readed + b_readed)
        else:
            if a_len > a_readed and t + a[a_readed] <= k:
                d.append((a_readed + 1, b_readed, t + a[a_readed]))
            if b_len > b_readed and t + b[b_readed] <= k:
                d.append((a_readed, b_readed + 1, t + b[b_readed]))
    ans = max(L)
    return ans

def tsundoku(f):
    readline = f.readline
    n, m, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    b = list(map(int, readline().split()))

    return _tsundoku(n, m, k, a, b)

def main():
    ans = tsundoku(sys.stdin.buffer)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import accumulate


def _tsundoku(n, m, k, a, b):
    a_temp = tuple(accumulate(a, initial=0))
    b_temp = tuple(accumulate(b, initial=0))

    ans = 0
    b_index = m
    for a_index in range(n + 1):
        if a_temp[a_index] > k:
            break
        while a_temp[a_index] + b_temp[b_index] > k:
            b_index -= 1
        else:
            ans = max(ans, a_index + b_index)
    return ans


def tsundoku(f):
    readline = f.readline
    n, m, k = map(int, readline().split())
    a = list(map(int, readline().split()))
    b = list(map(int, readline().split()))

    return _tsundoku(n, m, k, a, b)


def main():
    ans = tsundoku(sys.stdin.buffer)
    print(ans)


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

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = sorted([sorted(input()) for i in range(n)])
    ans = 0
    while len(s) != 0:
        cnt = s.count(s[0])
        del s[0:cnt]
        if cnt > 1:
            ans += (cnt * (cnt - 1)) // 2
    print(int(ans))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    s = ["".join(sorted(input())) for i in range(n)]
    s = collections.Counter(s)
    ans = 0
    for i in s.values():
        ans += (i*(i-1))//2
    print(ans)

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

N = int(input())
s = [input() for i in range(N)]
ans = 0
str_list = []
for i in range(N):
  str_list.append(sorted(s[i]))
for i in range(N):
  for j in range(i+1,N):
    if str_list[i] == str_list[j]:
      ans += 1
      
print(int(ans))

### FIXED CODE ###

n = int(input())
ans = 0
dict = {}
for _ in range(n):
  	#文字列をキーとする辞書型に出現回数を保持する
    s = str(''.join(sorted(list(input()))))
    try:
        ans += dict[s]
        dict[s] += 1
    except:
        dict[s] = 1
print(ans)
### BUGGY CODE ###

import math
K,S = map(int,input().split())
ans=0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                ans += 1

print(ans)

### FIXED CODE ###

import math
K,S = map(int,input().split())
ans=0

for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if z >= 0 and K >= z:
            ans += 1
print(ans)
### BUGGY CODE ###

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

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

aa = [0]
bb = [0]

for i in range(n):
    aa.append(a[i] + aa[i])

for i in range(m):
    bb.append(b[i] + bb[i])

ans = 0
flag = 0
for i in range(n+1):
    if k - aa[i] < 0:
        flag = 1
        break
    for j in range(m+1):
        if k - aa[i] - bb[j] < 0:
            flag =1
            break
    if ans < i + j - 1:
        ans = i + j - 1


if flag == 0:
    print(i+j)
    exit()
print(ans)


### FIXED CODE ###

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

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

aa = [0]
bb = [0]

for i in range(n):
    aa.append(a[i] + aa[i])

for i in range(m):
    bb.append(b[i] + bb[i])

ans = 0
mstart = m
for i in range(n+1):
    if k - aa[i] < 0:
        break
    for j in range(mstart,-1,-1):
        if k - aa[i] - bb[j] >= 0:
            mstart = j
            break
    if ans < i + j :
        ans = i + j 

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

n = int(input())
a = list(map(int,input().split()))
count = 0
for i in range(n-1):
	count += a[i]*sum(a[i+1:])
print(count%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
count = 0
su = sum(a)
for i in range(n-1):
	su -= a[i]
	count += a[i]*su
print(count%(10**9+7))