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

import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort()
ylist.sort()

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort(key=itemgetter(0))
ylist.sort(key=itemgetter(0))

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(key=itemgetter(0), reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)
### BUGGY CODE ###

T = int(input())
from collections import deque
for _ in range(T):
  N = int(input())
  KLR = [list(map(int,input().split())) for _ in range(N)]
  left = deque([])
  right = deque([])
  mid = deque([])
  for K,L,R in KLR:
    x = L - R
    if x==0:
      mid.append([K-1,L,R,x])
    elif x>0:
      left.append([K-1,L,R,x])
    else:
      right.append([K-1,L,R,x])

  left = sorted(left,key = lambda x:x[3],reverse = True)
  right = sorted(right, key = lambda x:x[3])
  flag = [False] * (N)
  ans = 0
  for i in range(len(left)):
    klr = left[i]
    x = klr[0]
    while True:
      if x<0:
        ans += klr[2]
        break
      if flag[x]:
        x -= 1
      else:
        flag[x] = True
        ans += klr[1]
        break
  flag = [False] * (N)
  for i in range(len(right)):
    klr = right[i]
    x = klr[0] + 1
    while True:
      if x>=N:
        ans += klr[1]
        break
      if flag[x]:
        x += 1
      else:
        flag[x] = True
        ans += klr[2]
        break
  for i in range(len(mid)):
    ans += mid[i][1]
    
  print(ans)

### FIXED CODE ###

def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  from heapq import heapify,heappop,heappush
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    ans = 0
    for K,L,R in KLR:
      x = L - R
      if x==0:
        ans += L
      elif x>0:
        left.append([K,L,R])
        ans += R
      else:
        right.append([K+1,L,R])
        ans += L

    left = sorted(left)
    right = sorted(right,reverse=True)
      
    S = []
    heapify(S)
    x = 1
    i = 0
    length = len(left)
    while x<=N:
      while i<length:
        klr = left[i]
        if klr[0]==x:
          heappush(S,klr[1]-klr[2])
          i += 1
          
        else:
          break
      
      y = len(S) - x
      if y<=0:
        x += 1
        continue
      else:
        for _ in range(y):
          heappop(S)
          
    ans += sum(S)
    
    S = []
    heapify(S)
    x = N+1
    i = 0
    length = len(right)
    while x>=0:
      while i<length:
        klr = right[i]
        if klr[0]==x:
          heappush(S,klr[2]-klr[1])
          i += 1
 
        else:
          break
      
      y = len(S) + x - N - 1
      if y<=0:
        x -= 1
        continue
      else:
        for _ in range(y):
          heappop(S)    
    ans += sum(S)
    print(ans)
    
main()
### BUGGY CODE ###

import sys
N, Ma, Mb = map(int, input().split())

G = []
for i in range(N):
 a, b, c = map(int, input().split())
 G.append( (a,b,c) )

M = 401
INF = 1000000000
dp = [ [ INF ] * M for _ in range(M) ]

dp[0][0] = 0
for a, b, c in G:
  for i in reversed(range(0, M - a)):
    for j in reversed(range(0, M - b)):
      dp[i+a][j+b] = min(dp[i+a][j+b], dp[i][j] + c)

ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x][Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())

G = []
for i in range(N):
 a, b, c = map(int, input().split())
 G.append( (a,b,c) )

M = 1 + min(sum([ a for a, b, c in G ]),
            sum([ b for a, b, c in G ]) )
INF = 1000000000
dp = [INF] * (M * M)
dp[0] = 0
for a, b, c in G:
  i = M - a - 1
  while i >= 0:
    j = M - b - 1
    while j >= 0:
      dp[(i+a)*M+(j+b)] = min(dp[(i+a)*M+(j+b)], dp[i*M+j] + c)
      j -= 1
    i -= 1

ans = INF
x = 1
while Ma * x < M and Mb * x < M:
  ans = min(ans, dp[Ma * x * M + Mb * x])
  x += 1
if ans >= INF:
  ans = -1
print(ans)
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import deque

k = ni()
que = deque([(1,1)])

kmod = [0]*k

while kmod[0] == 0:
    cost, cur = que.popleft()
    if kmod[cur%k] == 0:
        kmod[cur%k] = cost
        que.appendleft((cost, 10*cur))
        que.append((cost+1, cur+1))            
        
print(kmod[0])

### FIXED CODE ###

from collections import deque

def bfs(K:int) -> list:
    hasChecked = [False]*(K+1)
    cost_list = [0]*(K+1)
    cost_list[1] = 1
    
    que = deque([(cost_list[1], 1)])
    
    while que:
        cost, res = que.popleft()
        if hasChecked[res]:
            continue
        
        hasChecked[res] = True
        cost_list[res] = cost
        
        if not hasChecked[10*res%K]:
            que.appendleft((cost, 10*res%K))
            
        if not hasChecked[(res+1)%K]:
            que.append((cost+1, (res+1)%K))
            
            
    return cost_list


K = int(input())
cost_list = bfs(K)
print(cost_list[0])
### BUGGY CODE ###

H, W = map(int,input().split())
G = [input() for k in range(H)]
yoko = [[0 for k in range(W)] for k in range(H)]
tate = [[0 for k in range(W)] for k in range(H)]


for h in range(H):
    t = 0
    s = 0
    for w in range(W):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,w):
                    yoko[h][k] = t
            s = w+1
            t = 0
    if t > 0:
        for k in range(s,W):
            yoko[h][k] = t


for w in range(W):
    t = 0
    s = 0
    for h in range(H):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,h):
                    tate[k][w] = t
            s = h+1
            t = 0
    if t > 0:
        for k in range(s,H):
            tate[k][w] = t

ans = 0
for w in range(W):
    for h in range(H):
        ans = max(ans,tate[h][w]+yoko[h][w]-1)
print(ans)


### FIXED CODE ###

H, W = map(int,input().split())
G = [input() for k in range(H)]
yoko = [[0 for k in range(W)] for k in range(H)]
tate = [[0 for k in range(W)] for k in range(H)]


for h in range(H):
    t = 0
    s = 0
    for w in range(W):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,w):
                    yoko[h][k] = t
            s = w+1
            t = 0
    if t > 0:
        for k in range(s,W):
            yoko[h][k] = t


for w in range(W):
    t = 0
    s = 0
    for h in range(H):
        if G[h][w] == ".":
            t += 1
        else:
            if t > 0:
                for k in range(s,h):
                    tate[k][w] = t
            s = h+1
            t = 0
    if t > 0:
        for k in range(s,H):
            tate[k][w] = t

ans = 0
for w in range(W):
    for h in range(H):
        ans = max(ans,tate[h][w]+yoko[h][w]-1)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(1,20))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
T.sort(key=len, reverse=True)
ans = 0
for word in T:
    tt.register(word)
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    df = [node]
    while df:
        node = df.pop()
        for c, nnode in node.ch.items():
            if c == last:
                ans += node.ch[last].cnt
            else:
                df.append(nnode)
    ans -= 1
    
print(ans)


### FIXED CODE ###

import sys
import string
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
T = [input()[::-1].strip() for i in range(N)]

#N = 100
#M = 10000
#import random
#import string
#T = [''.join(random.choices(string.ascii_lowercase, k=random.randint(M,M))) for i in range(N)]

class TrieTree:
    class Node:
        def __init__(self):
            #self.clue = defaultdict(int)
            self.clue = [0]*26
            self.ch = defaultdict(TrieTree.Node)
            self.cnt = 0
            self.end = False

    def __init__(self):
        self.root = self.Node()

    def register(self,word):
        node = self.root
        for w in word:
            node.cnt += 1
            node = node.ch[w]
        node.cnt += 1
        node.end = True
    
    def prefix(self, word):
        node = self.root
        for w in word:
            if w not in node.ch:
                return False
            else:
                node = node.ch[w]
        return node

tt = TrieTree()
for word in T:
    tt.register(word)

route = []

st = [tt.root]
while st:
    node = st.pop()
    route.append(node)
    st.extend(node.ch.values())

f = lambda c : ord(c)-97
for node in route[::-1]:
    for c,nnode in node.ch.items():
        for i,v in enumerate(nnode.clue):
            node.clue[i] += v
        node.clue[f(c)] += nnode.cnt - nnode.clue[f(c)]

ans = 0
for word in T:
    pre = word[:-1]
    last = word[-1]
    node = tt.prefix(pre)
    if not node:
        continue
    ans += node.clue[f(last)] - 1
    
print(ans)
### BUGGY CODE ###

from itertools import permutations
n=int(input())
li=[int(i) for i in input().split()]

ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            a=li[i]
            b=li[j]
            c=li[k]
            if a<b+c and b<a+c and c<a+b:
                ans+=1
                  
print(ans)
        


### FIXED CODE ###

import bisect
n=int(input())
li=[int(i) for i in input().split()]
li.sort()

ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        a=li[i]
        b=li[j]
        c=bisect.bisect_left(li,a+b)
        ans+=c-j-1
                  
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
l, r = [], []
for i in range(Q):
    temp, temp2 = map(int, input().split())
    l.append(temp)
    r.append(temp2)

counter = 0
for i in range(len(l)):
    for j in range(l[i]-1, r[i]-1):
        temp3 = S[j:j+2]
        if j == len(S):
            continue
        elif j == r[i]:
            continue
        elif temp3 == "AC":
            counter += 1
    print(counter)
    counter = 0


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
l, r = [], []
t = [0] * (N+1)
for i in range(N):
    t[i + 1] = t[i] +(1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1 = A.count(1)
    n2 = A.count(2)
    n3 = A.count(3)

    dp = [[[-1.0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]

    def solve(n1, n2, n3):

        if dp[n1][n2][n3] >= 0.0:
            return dp[n1][n2][n3]
        if n1 == n2 == n3 == 0:
            return 0.0

        cnt = n1 + n2 + n3
        ret = 0
        if n3 >= 1:
            ret += solve(n1, n2 + 1, n3 - 1) * n3
        if n2 >= 1:
            ret += solve(n1 + 1, n2 - 1, n3) * n2
        if n1 >= 1:
            ret += solve(n1 - 1, n2, n3) * n1

        ret = (ret + N) / cnt
        dp[n1][n2][n3] = ret
        return ret

    print(solve(n1, n2, n3))


if __name__ == '__main__':
    main()


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

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

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

unique_ball = []

for ball in balls:
    if not (ball in unique_ball):
        unique_ball.append(ball)

ball_counts = []

for ball in unique_ball:
    ball_counts.append(balls.count(ball))

c = 0

while len(unique_ball) > k:
    c += ball_counts[ball_counts.index(min(ball_counts))]
    del unique_ball[ball_counts.index(min(ball_counts))]
    del ball_counts[ball_counts.index(min(ball_counts))]
    
print(c)


### FIXED CODE ###

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

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

max_n = 200000

ball_counts = [0]*max_n

for ball in balls:
    ball_counts[ball-1] += 1


counts = []

for n in ball_counts:
    if n !=0:
        counts.append(n)
        
counts = sorted(counts)

print(sum(counts[0:len(counts)-k]))
### BUGGY CODE ###

N=int(input())
P=list(map(int,input().split()))
count = 0
for i in range(N):
    if P[i]<=min(P[:i+1]):
        count += 1
print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
P=list(map(int,input().split()))
count = 0
saisyouti = P[0]
for i in range(N):
    if P[i]<=saisyouti:
        count += 1
        saisyouti=P[i]
print(count)
### BUGGY CODE ###

n=int(input())
ta=[list(map(int, input().split())) for _ in range(n)]
a,b=0,0
for i in range(n):
    x,y=ta[i]
    j,k=x,y
    t=0
    while(1):
        t+=1
        if j*t>=a and k*t>=b:
            break
    a,b=j*t,k*t
print(a+b)

### FIXED CODE ###

n=int(input())
ta=[list(map(int, input().split())) for _ in range(n)]
a,b=1,1
import math
for i in range(n):
    x,y=ta[i]
    t=max(-(-a//x),-(-b//y))
    a,b=t*x,t*y
print(a+b)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
maxnum = max(a)
for i in range(n):
    if a[i] == maxnum:
        tmp = a[i]
        a[i] = 0
        print(max(a))
        a[i] = tmp
    else:
        print(max(a))

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
sorted_a = []
for item in a:
    sorted_a.append(item)
sorted_a.sort(reverse=True)
for num in a:
    if num == sorted_a[0]:
        print(sorted_a[1])
    else:
        print(sorted_a[0])
### BUGGY CODE ###

def g(i,j):
    if i+j<10:
        return 1,i+j
    else:
        a = i+j
        b = a%10+a//10
        return 2,b
def f(c,d):
    if d==1:
        return 0,c
    if d==2:
        return g(c,c)
    if d%2==0:
        a,b = f(c,d//2)
        x,y = g(b,b)
        return 2*a+x,y
    else:
        a,b = f(c,d-1)
        x,y = g(c,b)
        return a+x,y
M = int(input())
A = [list(map(int,input().split())) for _ in range(M)]
cnt = 0
B = []
for i in range(M):
    c,d = A[i][0],A[i][1]
    a,b = f(c,d)
    cnt += a
    B.append(b)
b = B[0]
for i in range(1,M):
    a,b = g(b,B[i])
    cnt += a
print(cnt)   


### FIXED CODE ###

def g(i,j):
    if i+j<10:
        return 1,i+j
    else:
        a = i+j
        b = a%10+a//10
        return 2,b
def f(c,d):
    if d==1:
        return 0,c
    if d==2:
        return g(c,c)
    if d%2==0:
        a,b = f(c,d//2)
        x,y = g(b,b)
        return 2*a+x,y
    else:
        a,b = f(c,(d-1)//2)
        x1,y1 = g(b,b)
        x2,y2 = g(c,y1)
        return 2*a+x1+x2,y2
M = int(input())
A = [list(map(int,input().split())) for _ in range(M)]
cnt = 0
B = []
for i in range(M):
    c,d = A[i][0],A[i][1]
    a,b = f(c,d)
    cnt += a
    B.append(b)
b = B[0]
for i in range(1,M):
    a,b = g(b,B[i])
    cnt += a
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for j in range(N):
        for i in range(j+A[j]+1,N):
            if A[i] + A[j] == i-j:
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_left,bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [i+A[i] for i in range(N)] 
    B.sort()
    C = [i-A[i] for i in range(N)] 
    C.sort()
    ans = 0
    for i in range(N):
        ans += bisect_right(C,B[i]) - bisect_left(C,B[i])
    print(ans)

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

N=int(input())
ans=0
for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=min(u-1,v-1),max(u-1,v-1)
    ans-=(u+1)*(N-v)
for i in range(N):
    for j in range(i,N):
        ans+=j-i+1
print(ans)

### FIXED CODE ###

N=int(input())
ans=0
for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=min(u-1,v-1),max(u-1,v-1)
    ans-=(u+1)*(N-v)
for i in range(1,N+1):
    ans+=i*(i+1)//2
print(ans)
### BUGGY CODE ###

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

dp=[[0 for j in range(K+1)] for i in range(max(N,M)+1)]
if(N<M):
    ma=M
    mi=N
    turn='M'
else:
    ma=N
    mi=M
    turn='N'

if(turn=='M'):
    for i in range(ma):
        for j in range(K+1):
            if(mi<=i):
                if(B[i]<j):
                    dp[i+1][j]=max(dp[i][j-B[i]]+1,dp[i][j])
                else:
                    dp[i+1][j]=dp[i][j]
            else:

                if(A[i]<j and B[i]<j):

                    dp[i+1][j]=max(dp[i][j-A[i]-B[i]]+2,dp[i][j])

                elif(A[i]<j):
                    dp[i+1][j]=max(dp[i][j-A[i]]+1,dp[i][j])
                elif(B[i]<j):
                    dp[i+1][j]=max(dp[i][j-B[i]]+1,dp[i][j])
                else:
                    dp[i+1][j]=dp[i][j]
else:
    for i in range(ma):
        for j in range(K+1):
            if(mi<=i):
                if(A[i]<j):
                    dp[i+1][j]=max(dp[i][j-A[i]]+1,dp[i][j])
                else:
                    dp[i+1][j]=dp[i][j]
            else:
                if(A[i]<j and B[i]<j):
                    dp[i+1][j]=max(dp[i][j-A[i]-B[i]]+2,dp[i][j])

                elif(A[i]<j):
                    dp[i+1][j]=max(dp[i][j-A[i]]+1,dp[i][j])
                elif(B[i]<j):
                    dp[i+1][j]=max(dp[i][j-B[i]]+1,dp[i][j])
                else:
                    dp[i+1][j]=dp[i][j]

print(dp[ma][K])


### FIXED CODE ###

N,M,K=map(int,input().split())
A=[]
B=[]
A=list(map(int,input().split()))
B=list(map(int,input().split()))
a=[0 for i in range(len(A)+1)]
for i in range(1,len(A)+1):
    a[i]=a[i-1]+A[i-1]

b=[0 for i in range(len(B)+1)]
for i in range(1,len(B)+1):
    b[i]=b[i-1]+B[i-1]

j=M
ans=0
for i in range(len(A)+1):

    if(K<a[i]):
        break
    #print(a[i]+b[j])
    while(a[i]+b[j]>K):
        j=j-1
    ans=max(ans,i+j)

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


def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = sum_lr(d, d, 0)
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
import sys
input = sys.stdin.readline
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    nums += tmp_nums
    cnt += tmp_cnt
    
for d, c in nums:
    for _ in range(c):
        l, tmp_cnt = sum_lr(l,d,0)
        cnt += tmp_cnt

print(cnt-1)

### FIXED CODE ###

def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

from collections import defaultdict
aaa = defaultdict(lambda:{})
for l in range(10):
    for r in range(10):
        aaa[l][r] = sum_lr(l,r,0)
        

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = aaa[d][d]
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
import sys
input = sys.stdin.readline
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    for t,_ in tmp_nums:
        nums.append(t)
    
    cnt += tmp_cnt
    
#print(nums)    
    
for d in nums:
    l, tmp_cnt = aaa[l][d]
    cnt += tmp_cnt

print(cnt-1)
### BUGGY CODE ###

A, B, K = map(int, input().split())
for i in range(K):
    if A>=1:
        A -= 1
    elif A==0 and B >=1:
        B -= 1
    elif A == B == 0:
        break
print(A, B, sep=' ')

### FIXED CODE ###

A, B, K = map(int, input().split())
if A>=K:
    A = A - K
    print(A,B)
else:
    K -= A
    A = 0
    B = max(0,B-K)
    print(A,B)