Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]


n = int(input())
xy = [[map(int,input().split()),i] for i in range(n)]
xy2 = sorted(xy)
u = Unionfind(n)

l = []
for x,y,ind in xy2:
    M = y
    le = ind
    while l and xy[l[-1]][1] < y:
        v = l.pop()
        if M > xy[v][1]:
            M = xy[v][1]
            le = v
        u.union(ind,v)
    l.append(le)
for i in range(n):
    print(u.size(i))



### FIXED CODE ###

import sys
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

def main():
    n = int(input())
    xy = [list(map(int,input().split())) for i in range(n)]
    xy2 = [[x[0],x[1],i] for (i,x) in enumerate(xy)]
    xy2.sort()
    u = Unionfind(n)

    l = []
    for x,y,ind in xy2:
        M = y
        le = ind
        while l and xy[l[-1]][1] < y:
            v = l.pop()
            if M > xy[v][1]:
                M = xy[v][1]
                le = v
            u.union(ind,v)
        l.append(le)
    for i in range(n):
        print(u.size(i))

if __name__ == "__main__":
    main()
# coding : utf-8
s=list(map(lambda c:ord(c)-ord('a'),input()))
k=int(input())
for i in range(len(s)):
    if 26-s[i]<=k:
        k-=(26-s[i])
        s[i]=0
s[-1]+=k
for n in s:
    print(chr(ord('a')+n),end='')
print()


### FIXED CODE ###

# coding : utf-8
s=list(map(lambda c:ord(c)-ord('a'),input()))
k=int(input())
for i in range(len(s)):
    if 26-s[i]<=k and s[i]!=0:
        k-=(26-s[i])
        s[i]=0
s[-1]=(s[-1]+k)%26
for n in s:
    print(chr(ord('a')+n),end='')
print()
from sys import stdin
from math import gcd
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
lcm = a[0]
for i in range(1,n):lcm = (lcm*a[i])//gcd(lcm,a[i])
b = [lcm // i for i in a]
print(sum(b)%1000000007)

### FIXED CODE ###

from sys import stdin
def gcd(x, y):
	while(y):x, y = y, x % y 
	return x
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
lcm = a[0]
for i in range(1,n):lcm = (lcm*a[i])//gcd(lcm,a[i])
b = [lcm // i for i in a]
print(sum(b)%1000000007)
N=int(input())
M=int(input())
array = list(map(int, input().strip().split()))
if(N>=sum(array)):
    print(N-sum(array))
else:
    print('-1')

### FIXED CODE ###

N, M = map(int, input().split())
a = list(map(int, input().split()))
if(N>=sum(a)):
    print(N-sum(a))
else:
    print('-1')
from math import gcd
def lcm(x, y):
    return x * y // gcd(x, y)

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

### FIXED CODE ###

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
l%=mod
for i in range(n):
  ans+=l*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)
n, len(a)= map(int, input().split())
a= list(map(int, input().split()))
c= n-sum(a)
print(c)


### FIXED CODE ###

n,m= map(int, input().split())
a = list(map(int, input().split()))
c = n-sum(a)
if m == len(a) and c>= 0:
    print(c)
else:
    print(-1)
a,b=input().split()

wa = a + b
sa = a - b
seki = a * b

if wa >= sa and wa >= seki:
    print(str(wa))
elif sa >= wa and sa >= seki:
    print(str(sa))
else:
    print(str(seki))

### FIXED CODE ###

a,b=input().split()

wa = int(a) + int(b)
sa = int(a) - int(b)
seki = int(a) * int(b)

if wa >= sa and wa >= seki:
    print(str(wa))
elif sa >= wa and sa >= seki:
    print(str(sa))
else:
    print(str(seki))
import math

N = int(input())

Klist = [0]*(int(N**(1/2))+1)
count = 1###int(N**(1/2))+1以上についてカウント
###あらかじめK=Nはカウント

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1) % i == 0:
        Klist[i] = 1
        count += 1
        ###
        #print(i,(N-1)//i)
        ###

if int((N-1)**(1/2)) == (N-1)**(1/2):
    count -= 1

M = int(math.log2(N))

for m in range(1,M+1):
    if m >= 2 and N**(1/m) == int(N**(1/m)):###m=1のときはK=Nの話なのでpass
        Klist[int(N**(1/m))] = 1
    for K in range(2,int(N**(1/(m+1))+1)):
        if (N-K**m)%(K**(m+1)) == 0:
            Klist[K] = 1
###
#print("count",count)
#print(Klist)
###
print(sum(Klist)+count-Klist[1])


### FIXED CODE ###

###草

import math

N = int(input())

Klist = [0]*(int(N**(1/2))+1)
count = 1###int(N**(1/2))+1以上についてカウント
###あらかじめK=Nはカウント

for i in range(1,int((N-1)**(1/2))+1):
    if (N-1) % i == 0:
        Klist[i] = 1
        count += 1
        ###
        #print(i,(N-1)//i)
        ###

if  (N-1)**(1/2) - int((N-1)**(1/2)) < 1e-10 or 1 + int((N-1)**(1/2)) - ((N-1)**(1/2)) < 1e-10:
    count -= 1

M = int(math.log2(N))

for m in range(1,M+1):
    if m >= 2 and (N**(1/m) - int(N**(1/m)) < 1e-10 or 1+int(N**(1/m))-N**(1/m) < 1e-10):###m=1のときはK=Nの話なのでpass
        Klist[round(N**(1/m))] = 1
    for K in range(2,int(N**(1/(m+1))+1)):
        if (N-K**m)%(K**(m+1)) == 0:
            Klist[K] = 1
###
#print("count",count)
#print(Klist[:100])
###
print(sum(Klist)+count-Klist[1])
# -*- coding: utf-8 -*-

import math

r = float(raw_input())
print "%f %f" %(r*r*math.pi, 2*r*mat.pi)

### FIXED CODE ###

# -*- coding: utf-8 -*-

import math

r = float(raw_input())
print "%f %f" %(r*r*math.pi, 2*r*math.pi)
import sys
def frog2(N,h,k):
    dp=[sys.maxsize-1]*N
    dp[0]=0
    for i in range(N):
        for j in range(i+1,i+k+1):
            if j<N:
                dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))
    return dp[N-1]

N,k=map(int,input().split())
h=list(map(int,input().split()))
print(frog2(N,h,k))

### FIXED CODE ###

import sys
def frog2(N,h,k):
    dp=[sys.maxsize-1]*N
    dp[0]=0
    for i in range(N):
        for j in range(i+1,i+k+1):
            if j<N:
                dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))
    return dp[N-1]

N,k=map(int,input().split())
h=list(map(int,input().split()))
print(frog2(N,h,k))
pi = 3.141592653589793

r = int(input())

s = r * r * pi
l = r * 2 * pi

print(s, l)

### FIXED CODE ###

import sys
import math
from decimal import Decimal

r = Decimal(sys.stdin.readline())
area = r ** Decimal(2) * Decimal(math.pi)
circumference = r * Decimal(2) * Decimal(math.pi)

print(round(area, 5), round(circumference, 5))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B, N = MAP()

left, right = 0, N

def f(x):
    return int(A*x/B) - A*int(x/B)


# while right-left > 1:
#     mid1 = (left + right)*1// 3
#     mid2 = (left + right)*2// 3

#     if f(mid1) < f(mid2):
#         if left == mid1:
#             break
#         left = mid1
#     else:
#         if right == mid1:
#             break
#         right = mid2

# ans = f(left)
# for i in range(left, right+1):
#     ans = max(ans, f(i))
# print(ans)
# ans = 0
# # whilefor i in range(1, N+1):
# #     ans = max(ans, f(i))
# # print(ans)

# x = N//2
# if f(x) <= f(x)
# direc = "R"

ans = 0
if B > N:
    ans = f(N)
else:
    f(i*B-1)

print(ans)

### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

A, B, N = MAP()

left, right = 0, N

def f(x):
    return int(A*x/B) - A*int(x/B)


# while right-left > 1:
#     mid1 = (left + right)*1// 3
#     mid2 = (left + right)*2// 3

#     if f(mid1) < f(mid2):
#         if left == mid1:
#             break
#         left = mid1
#     else:
#         if right == mid1:
#             break
#         right = mid2

# ans = f(left)
# for i in range(left, right+1):
#     ans = max(ans, f(i))
# print(ans)
# ans = 0
# # whilefor i in range(1, N+1):
# #     ans = max(ans, f(i))
# # print(ans)

# x = N//2
# if f(x) <= f(x)
# direc = "R"

ans = 0
if B > N:
    ans = f(N)
else:
    ans = f(B-1)

print(ans)
import decimal
import math

N, K = map(int, input().split())
coin = [decimal.Decimal('0.5')**k for k in range(10**4)]
ans = 0

for i in range(1,N+1):
    tmp = decimal.Decimal(str(math.log2(K/i)))
    x = int(math.log2(K/i))
    if i >= K:
        ans += decimal.Decimal(1/N)
    else:
        if tmp - x != 0:
            x += 1
        ans += decimal.Decimal(1/N) * coin[x]

print(ans)


### FIXED CODE ###

import math
N,K = map(int,input().split())
ans = 0
 
for i in range(1,N+1):
    if i >= K:
        ans += (1/N)
        continue
    X = int(math.log((K/i), 2))
    if (K/i) % 2**X == 0:
        pass
    else:
        X += 1
    ans += (1/N) * (1/2) ** X
print(ans)
a, b = map(int(input().split()))
 
if a >= 13:
  print(b)
elif a >= 6:
  print((int)b/2)
else:
  print(0)

### FIXED CODE ###

a,b = map(int, input().split())
 
ans=0
if a <= 5:
	ans = 0
elif a >= 6 and a<=12:
	ans = b/2
else:
	ans = b
 
print(int(ans))
n,q=map(int,input().split())
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

lis = [0 for i in range(n)]
for i in range(q):
    p,x=map(int,input().split())
    lis[p-1]+=x

def dfs(i,j,k):
    nex=g[i]
    lis[i]=k
    for d in nex:
        if d==j: continue
        nk=k+lis[d]
        dfs(d,i,nk)

dfs(0,-1,lis[0])
print(*lis)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
g=[[]for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

lis = [0 for i in range(n)]
for i in range(q):
    p,x=map(int,input().split())
    lis[p-1]+=x

def dfs(i,j):
    nex=g[i]
    for d in nex:
        if d==j: continue
        #print(d)
        lis[d]+=lis[i]
        dfs(d,i)

dfs(0,-1)
print(*lis)
g,r=map(int,input().split())
A=["."*r]
for i in range(g):
  w="."+input()+"."
  A.append(w)
A.append("."*r)
B=[]
for i in range(1,g+1):
  for j in range(1,r+1):
    if A[i][j]==".":
      for m in [i-1,i,i+1]:
        for k in [j-1,j,j+1]:
          B=append(A[m][k])
      A[i][j]=B.count("#")
for i in range(g):
  print(A[g])

    

### FIXED CODE ###

g,r=map(int,input().split())
A=["."*(r+2)]
for i in range(g):
  w="."+input()+"."
  A.append(w)
A.append("."*(r+2))

for i in range(1,g+1):
  for j in range(1,r+1):
    if A[i][j]==".":
      B=[]
      for m in [i-1,i,i+1]:
        for k in [j-1,j,j+1]:
          B.append(A[m][k])
     
      A[i]=A[i][1:r+1:].replace(".",str(B.count("#")),1)
      A[i]="."+A[i]+"."
for i in range(1,g+1):
  print(A[i][1:r+1:])
N,M=map(int,input().split())
cakes=[]
for i in range(N):
  x,y,z=map(int,input().split())
  cakes.append([x,y,z])
score=[0]*8
c=sorted(map(lambda c: [ c[0]+c[1]+c[2],*c], cakes),key=lambda c: c[0])[-M:]
score[0]=sum(list(map(abs,map(sum,zip(*c))))[1:])
c=sorted(map(lambda c: [ c[0]+c[1]-c[2],*c], cakes),key=lambda c: c[0])[-M:]
score[1]=sum(list(map(abs,map(sum,zip(*c))))[1:])
c=sorted(map(lambda c: [ c[0]-c[1]+c[2],*c], cakes),key=lambda c: c[0])[-M:]
score[2]=sum(list(map(abs,map(sum,zip(*c))))[1:])
c=sorted(map(lambda c: [ c[0]-c[1]-c[2],*c], cakes),key=lambda c: c[0])[-M:]
score[3]=sum(list(map(abs,map(sum,zip(*c))))[1:])
c=sorted(map(lambda c: [-c[0]+c[1]+c[2],*c], cakes),key=lambda c: c[0])[-M:]
score[4]=sum(list(map(abs,map(sum,zip(*c))))[1:])
c=sorted(map(lambda c: [-c[0]+c[1]-c[2],*c], cakes),key=lambda c: c[0])[-M:]
score[5]=sum(list(map(abs,map(sum,zip(*c))))[1:])
c=sorted(map(lambda c: [-c[0]-c[1]+c[2],*c], cakes),key=lambda c: c[0])[-M:]
score[6]=sum(list(map(abs,map(sum,zip(*c))))[1:])
c=sorted(map(lambda c: [-c[0]-c[1]-c[2],*c], cakes),key=lambda c: c[0])[-M:]
score[7]=sum(list(map(abs,map(sum,zip(*c))))[1:])
#print(list(map(sum,zip(*c))))
#print(list(map(sum,zip(*c)))[1:])
print(max(score))


### FIXED CODE ###

N,M=map(int,input().split())
cakes=[]
for i in range(N):
  x,y,z=map(int,input().split())
  cakes.append([x,y,z])
if M==0:
  print(0)
  quit()
score=[0]*8
score[0]=sum(sorted(map(lambda c: c[0]+c[1]+c[2], cakes))[-M:])
score[1]=sum(sorted(map(lambda c: c[0]+c[1]-c[2], cakes))[-M:])
score[2]=sum(sorted(map(lambda c: c[0]-c[1]+c[2], cakes))[-M:])
score[3]=sum(sorted(map(lambda c: c[0]-c[1]-c[2], cakes))[-M:])
score[4]=sum(sorted(map(lambda c:-c[0]+c[1]+c[2], cakes))[-M:])
score[5]=sum(sorted(map(lambda c:-c[0]+c[1]-c[2], cakes))[-M:])
score[6]=sum(sorted(map(lambda c:-c[0]-c[1]+c[2], cakes))[-M:])
score[7]=sum(sorted(map(lambda c:-c[0]-c[1]-c[2], cakes))[-M:])
print(max(score))
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
count =0
X = A[-1]
for i in range(N):
  if A[i] >= B[i]  and A[i] >= 0:
    count += B[i]
  elif A[i] < B[i] and A[i] >= 0:
    A[i+1] = A[i+1] - (B[i] - A[i])
    count += A[i]
if A[-1] >= 0:
  count += X - A[N+1]
else:
  count += X
print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
count =0
for i in range(N):
  if A[i] >= B[i]  and A[i] >= 0:
    count += B[i]
    A[i] = A[i] - B[i]
  elif A[i] < B[i] and A[i] >= 0:
    if A[i+1]-B[i]+A[i] > 0:
      count += B[i]
    else:
      count += A[i] +A[i+1]
    A[i+1] -=  B[i] - A[i]
    A[i] = -1
  elif A[i] < 0:
    if A[i+1] >= B[i]:
      count += B[i]
      A[i+1] = A[i+1]- B[i]
    else:
      count += A[i+1]
      A[i+1] -= B[i]
print(count)
h,w=map(int,(input().split()))
r=0
for i in range(h):
    if i % 2 == 0:
        r+=(w+1)//2
    else:
        r+= w//2
print(r)


### FIXED CODE ###

a=1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
K=int(input())
print(a[K-1])
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
numk={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
dp=[0]+[-float('inf')]*(N)
for i in range(N):
  for j in A:
    if i+numk[j]<=N:
      dp[i+numk[j]]=max(dp[i+numk[j]],dp[i]+1)
m=N
ans=[]
while m>0:
  for i in range(M):
    if dp[m-numk[A[i]]]+1==dp[m] and m-numk[A[i]]>=0:
      ans.append(str(A[i]))
      m-=numk[A[i]]
      break
print(''.join(ans))

### FIXED CODE ###

N,M=map(int,input().split())
num={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}
A=list(map(int,input().split()))
A.sort(reverse = True)
dp = [0]+[-1]*(N+1)
for i in range(N):
    for j in A:
        if i+num[j]<=N:
            dp[i+num[j]] = max(dp[i+num[j]],dp[i]+1)
ans = []
m=N
while m>0:
    for i in A:
        if m-num[i]>=0 and dp[m-num[i]]==dp[m]-1:
          m-=num[i]
          ans.append(str(i))
          break
print("".join(ans))
import math
a, b, c, d = map(int, input().split())
ans = 0
def notdiv(n, m):
  return n // m

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
a -= 1
e = b - notdiv(b, c) - notdiv(b, d) + notdiv(b, lcm(c, d))
f = a - notdiv(a, c) - notdiv(a, d) + notdiv(a, lcm(c, d))
ans = e - f
print(ans)

### FIXED CODE ###

import math
a, b, c, d = map(int, input().split())
e = b - ((b // c) + (b // d) - (b // (c * d // math.gcd(c, d))))
f = (a - 1) - (((a - 1) // c) + ((a - 1) // d) - ((a - 1) // (c * d // math.gcd(c, d))))
ans = e - f
print(ans)
import sys
import heapq


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


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(N):
       AA[i] = A[i] * (-1))
    heapq.heapify(AA)

    for i in range(M):
        maxaa=-1 * heapq.heappop(AA)
        if max(A) == 0:
            print("0")
            exit()
        heapq.heappush(AA,  maxaa // 2 * (-1))
    print(sum(AA) * (-1))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import heapq


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


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(N):
        A[i] *= -1
    heapq.heapify(A)

    for i in range(M):
        maxa = -1 * heapq.heappop(A)
        if maxa == 0:
            print("0")
            exit()
        heapq.heappush(A,  maxa // 2 * (-1))
    print(sum(A) * (-1))


if __name__ == '__main__':
    main()
N=int(raw_input())
lis = []
for i in range(0,N):
	lis.append(int(raw_input()))
if sum(lis) % 0 == 0:
	print sum(lis)-min(lis)
else:
	print sum(lis)


### FIXED CODE ###

N=int(raw_input())
lis = []
for i in range(0,N):
	num = int(raw_input())
	lis.append(num)
get = sum(lis)
if sum(lis) % 10 == 0:
	for j in range(0,N-1):
		if min(lis) % 10 != 0:
			print get - min(lis)
			break
		lis.remove(min(lis))
	else:
		print 0
else:
	print get
import sys
sys.setrecursionlimit(10**5)
def main():
    n = int(input())
    h = [int(x) for x in input().split()]
    memo = [None for i in range(n)]

    # def rec(n):
    #     if memo[n-1] == None:
    #         if n <= 1:
    #             memo[n-1] = 0
    #         elif n == 2:
    #             memo[n-1] = abs(h[1]-h[0])
    #         else:
    #             d1 = rec(n-2)+abs(h[n-1]-h[n-3])
    #             d2 = rec(n-1)+abs(h[n-1]-h[n-2])
    #             memo[n-1] = min(d1,d2)
    #     return memo[n-1]
        
    # print(rec(n))

    def f(n):
        if memo[n-1] == None:
          if n <= 1:
              memo[n-1] = 0
          elif n == 2:
              memo[n-1] = abs(h[1]-h[0])
          else:
              d1 = f(n-1) + abs(h[n-1]-h[n-2])
              d2 = f(n-2) + abs(h[n-1]-h[n-3])
              memo[n-1] = min(d1,d2)
        return memo[n-1]

    print(f(n))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
def main():
    n = int(input())
    h = [int(x) for x in input().split()]
    memo = [None for i in range(n)]

    def rec(n):
        if memo[n-1] == None:
            if n <= 1:
                memo[n-1] = 0
            elif n == 2:
                memo[n-1] = abs(h[1]-h[0])
            else:
                d1 = rec(n-2)+abs(h[n-1]-h[n-3])
                d2 = rec(n-1)+abs(h[n-1]-h[n-2])
                memo[n-1] = min(d1,d2)
        return memo[n-1]
        
    print(rec(n))

if __name__ == "__main__":
    main()
a = int(input())
b = int(input())

print(a*b)

### FIXED CODE ###

a , b = (input().split(' '))
a = int(a)
b = int(b)
print(a*b)
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
ans = [[0 for i in range(W)] for j in range(H)]
def f(h,w,x):
  global H,W,S,ans
  if h<0 or h>=H or w<0 or w>=W or S[h][w]=="#":
    return
  ans[h][w]+=1
  if x==0:
    f(h-1,w,1)
    f(h+1,w,2)
    f(h,w-1,3)
    f(h,w+1,4)
  elif x==1:
    f(h-1,w,1)
  elif x==2:
    f(h+1,w,2)
  elif x==3:
    f(h,w-1,3)
  elif x==4:
    f(h,w+1,4)
for h in range(H):
  for w in range(W):
    if S[h][w]=="#":
      continue
    f(h,w,0)
a = 0
for h in ans:
  a = max(a,max(h))
print(a)

### FIXED CODE ###

H,W = map(int,input().split())
S = [input() for i in range(H)]

L = [[0]*W for i in range(H)]
R = [[0]*W for i in range(H)]
U = [[0]*W for i in range(H)]
D = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            if h==0:D[h][w]=1
            else:D[h][w]=D[h-1][w]+1
            if w==0:R[h][w]=1
            else:R[h][w]=R[h][w-1]+1
for h in range(H-1,-1,-1):
    for w in range(W-1,-1,-1):
        if S[h][w]==".":
            if h==H-1:U[h][w]=1
            else:U[h][w]=U[h+1][w]+1
            if w==W-1:L[h][w]=1
            else:L[h][w]=L[h][w+1]+1

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,L[h][w]+R[h][w]+U[h][w]+D[h][w]-3)
print(ans)
a=input()
if a==a.upeer():
  print("A")
else:
  print("a")

### FIXED CODE ###

a=input()
if a==a.upper():
  print("A")
else:
  print("a")
n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b, c = map(int,input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

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

d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for leaf in tree[x]:
        if leaf[0] == p:
            continue
        else:
            dfs(leaf[0], leaf[1]+c, x)

dfs(k, 0, -1)
for i in range(q):
    a, b = map(int, input().split())
    print(d[a]+d[b])


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b, c = map(int,input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

q, k = map(int, input().split())
d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for l, c_ in tree[x]:
        if l == p:
            continue
        else:
            dfs(l, c_+c, x)

dfs(k, 0, -1)
for i in range(q):
    a, b = map(int, input().split())
    print(d[a]+d[b])
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

A,B=list(map(int,input().split()))
print(lcm_list([A,B]))

### FIXED CODE ###

import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

A,B=list(map(int,input().split()))
print(lcm_list([A,B]))
s=int(input())
mod=10**9+7
dp=[0]*s


for i in range(4,s+1):
	for j in range(0,(i-3)+1):
		dp[i]+=dp[j]
		dp[i]%=mod
print(dp[s])



### FIXED CODE ###

s=int(input())
mod=10**9+7
dp=[0]*(s+1)
dp[0]=1

for i in range(1,s+1):
	for j in range(0,(i-3)+1):
		dp[i]+=dp[j]
		dp[i]%=mod
print(dp[s])
# -*- coding: utf-8 -*-


def main():
    n, m, k = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    a = A[0]
    A2 = [a]
    b = B[0]
    B2 = [b]
    for i in range(1, n):
        a += A[i]
        A2.append(a)

    for i in range(1, m):
        b += B[i]
        B2.append(b)
    max = -2
    for ia, aa in enumerate(A2):
        for ib, bb in enumerate(B2):
            if aa + bb > k:
                break
            if ia + ib > max:

                max = ia + ib
    print(max + 2)


def answer():
    N, M, K = map(int, input().split())


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

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

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

### FIXED CODE ###

def main():
    a = int(input())
    print(a+a*a+a*a*a)
if __name__ == '__main__':
    main()
A,B=map(int,input().split())
if A>8 or b>8:
    print(":(")
else:
    print("Yay!")

### FIXED CODE ###

A,B=map(int,input().split())
if A>8 or B>8:
    print(":(")
else:
    print("Yay!")
S=str(input())
if S[0]=='1':S[0]='9'
if S[0]=='9':S[0]='1'
if S[1]=='1':S[1]='9'
if S[1]=='9':S[1]='1'
if S[2]=='1':S[2]='9'
if S[2]=='9':S[2]='1'
print(S)

### FIXED CODE ###

S = str(input())
print( 100*(10-int(S[0])) + 10*(10-int(S[1])) + 1*(10-int(S[2])) )