Harryxun/stf_run huggingface dataset:
from itertools import groupby

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if self.rank[root_x] < self.rank[root_y]:
            self.parents[root_x] = root_y
            self.size[root_y] += self.size[root_x]
        else:
            self.parents[root_y] = root_x
            self.size[root_x] += self.size[root_y]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

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

    def get_group(self):
        arr = sorted([(self.find(node), node) for node in range(self.n)])
        groups = []
        for _, g in groupby(arr, key=lambda x: x[0]):
            groups.append([u[1] for u in g])
        return groups

N, M = map(int, input().split())
bridges = []
for _ in range(M):
  bridges.append(list(map(lambda x: int(x)-1, input().split())))

U = UnionFind(N)
F = [N * (N-1) / 2]
for i in range(M-1):
  F.append(F[-1] - U.get_size(bridges[M-i-1][0]) * U.get_size(bridges[M-i-1][1]))
  F.append(U.union(*bridges[M-i-1]))
for f in F.reverse():
  print(f)

### FIXED CODE ###

from itertools import groupby
 
class UnionFind:
 
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n
 
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if self.rank[root_x] < self.rank[root_y]:
            self.parents[root_x] = root_y
            self.size[root_y] += self.size[root_x]
        else:
            self.parents[root_y] = root_x
            self.size[root_x] += self.size[root_y]
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
 
    def get_size(self, x):
        return self.size[self.find(x)]
 
    def get_group(self):
        arr = sorted([(self.find(node), node) for node in range(self.n)])
        groups = []
        for _, g in groupby(arr, key=lambda x: x[0]):
            groups.append([u[1] for u in g])
        return groups

    
N, M = map(int, input().split())
bridges = []
for _ in range(M):
    bridges.append(list(map(lambda x: int(x)-1, input().split())))
U = UnionFind(N)
F = [N * (N-1) // 2]
for i in range(M-1):
    if not U.is_same(*bridges[M-i-1]):
        F.append(F[i] - U.get_size(bridges[M-i-1][0]) * U.get_size(bridges[M-i-1][1]))
        U.union(*bridges[M-i-1])
    else:
        F.append(F[i])
F.reverse()
for f in F:
    print(f)
a = list(input())
for i in range(3):
  if a[i] = "1":
    a[i] = 9
  else:
    a[i] = 1
print("".join(a))

### FIXED CODE ###

a = list(input())
for i in range(3):
  if a[i] == "1":
    a[i] = "9"
  else:
    a[i] = "1"
print("".join(a))
A, B, C = LI()
X = max(A,B,C)
result1 = 3*X - (A+B+C)
result2 = 3*(X+1) - (A+B+C)
if result1%2 == 0:
    print(result1/2)
else:
    print(result2/2)


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

A, B, C = LI()

nums = sorted([A,B,C])
set_nums = list(set([A,B,C]))
result = 0
if len(set_nums) == 1:
    print(0)
elif len(set_nums) == 2:
    # 2種類は一緒
    #前２つが一緒かつはぐれが大きい
    if nums[0] == nums[1]:
        result += nums[2]-nums[1]
        print(result)
        exit()
    elif nums[1] == nums[2]:
        # 後ろ２つが等しく、はぐれが最小
        result += (nums[1] - nums[0])//2
        if (nums[1]-nums[0]) % 2 != 0:
            result += 2
        print(result)
        exit()
else:
    # 全数字が異なる
    result += nums[2]-nums[1]
    nums[0] += nums[2]-nums[1]
    result += (nums[2] - nums[0]) // 2
    if (nums[2] - nums[0]) % 2 != 0:
        result += 2

    print(result)
q,h,s,d=map(int,input().split())
n=int(input())
n*=4
if q*2<h:
    if h*2<s:
        if q*8<d:
            print(n*q);exit()
        else:
            print(q*(n%8)+d*(n//8));exit()
    elif 2*s<d:
      if q*4<s:
        print(n*q)
      else:
        print(s*(n//4));exit()
    else:
      if q*4<s:
        print(d*(n//8)+q*(n%8))
      else:
        print(d*(n//8)+s*((n%8)//4);exit()
else:
    if 2*h<s:
        if 2*s>d:
            print(d*(n//8)+h*((n%8)//2));exit()
        else:
            print(h*(n//2));exit()
    else:
        if 2*s<d:
            print(s*(n//4))
        else:
            print(d*(n//8)+s*((n%8)//4)) 
            


### FIXED CODE ###

q,h,s,d=map(int,input().split())
n=int(input())
n*=4
j=4*(2*q<h)+2*(2*h<s)+(4*q<s)
if j%4==0:
  if 2*s<d:
    print(s*(n//4))
  else:
    print(d*(n//8)+s*((n%8)//4))
  
if j==2 or j==3:
  if 4*h<d:
    print(h*(n//2))
  else:
    print(d*(n//8)+h*((n%8)//2))

if j==5 or j==7:
  if q*8<d:
    print(q*n)
  else:
    print(d*(n//8)+q*(n%8))
N, K = map(int, input().split())
x = list(map(int, input().split()))



for i, v in enumerate(x):
    if v == 0:
        point = i
        break
    elif v > 0:
        point = i - 1
        break

if len(x[:point+1]) <= K:
    start = 0
else:
    start = point - K + 1

end = start + K -1
ans = 10 ** 9
        
for i in range(K):
    if abs(x[start+i]) <= x[end+i]:
        time = abs(x[start+i] * 2) + x[end+i]
    else:
        time = abs(x[start+i]) + (x[end+i] * 2)
    ans = min(ans, time)
    if end + i == len(x) - 1:
        break
    
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
x = list(map(int, input().split()))

point= len(x) - 1
for i, v in enumerate(x):
    if v == 0:
        point = i
        break
    elif v > 0:
        point = i - 1
        break

start = max(0, point - K + 1)
end = start + K - 1

if x[point] != 0:
    point += 1
    
ans = float('inf')

while True:
    if x[start] >= 0:
        time = x[end]
    elif x[end] <= 0:
        time = abs(x[start])
    elif abs(x[start]) <= x[end]:
        time = abs(x[start] * 2) + x[end]
    else:
        time = abs(x[start]) + (x[end] * 2)
    ans = min(ans, time)
    
    start += 1
    end += 1

    if start > point or end == len(x):
        break
    
print(ans)
import sys

N,K=map(int,input().split())
N=list(map(int,input().split()))
a={}
 
b=1
a[1]=1
count=0
while(count<=K+1):
  count+=1
  b=N[b-1]
  #print(b)
  if b in a:
    #print(a)
    #print(b)
    #print(count)
    cycle=count-a[b]
    rest=K-count+1
    ans=rest%cycle
    for i in range(ans-1):
      b=N[b-1]
      count+=1
      if count==K+1:
        print(b)
        sys.exit()
    print(b)
    break
  a[b]=count
  if count==K+1:
    print(b)
    break

### FIXED CODE ###

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

count=0
k=1
countlist={}
#countlist[1]=A[0]
count=1
while True:    
    k=A[k-1]
    
    if k in countlist:
        cycle=count-countlist[k]
        rest=K-count
        move=rest%cycle
        for i in range(min(rest,move)):
            k=A[k-1]
        print(k)
        break
    
    countlist[k]=count
    
    if count==K:
        print(k)
        break
    
    count+=1
x = int(input())
h, remainder = divmod(x, 60*60)
m, s = divmod(remainder, 60)
print(f"{h}:{m}:{s}")

### FIXED CODE ###

x = int(input())
h, r = divmod(x, 60*60)
m, s = divmod(r, 60)
print(h, m, s, sep=':')
N, K = map(int, input().split())
d = list(map(int, input().split()))
left = [0]
left_m = []
right = [0]
right_m = []
for i, l, r in zip(range(K), d, d[::-1]):
    left.append(left[i] + l)
    left_m.append(l if l < 0 else 0)
    right.append(right[i] + r)
    right_m.append(r if r < 0 else 0)
point = 0
for i in range(K):
    for j in range(K - i):
        p = K - i - j
        minus = list(sorted(left_m[:i] + right_m[:j]))
        point = max(point, left[i] + right[j] - sum(minus[:p]))
print(point)


### FIXED CODE ###

N, K = map(int, input().split())
d = list(map(int, input().split()))
left = [0]
left_m = []
right = [0]
right_m = []
for i, l, r in zip(range(K), d, d[::-1]):
    left.append(left[i] + l)
    left_m.append(l if l < 0 else 0)
    right.append(right[i] + r)
    right_m.append(r if r < 0 else 0)
point = 0
m = min(N, K)
for i in range(m + 1):
    for j in range(m - i + 1):
        p = K - i - j
        minus = list(sorted(left_m[:i] + right_m[:j]))
        point = max(point, left[i] + right[j] - sum(minus[:p]))
print(point)
a, b = map(int, raw_input())

if a <= 8 and b <= 8:
    print 'Yay!'
else:
    print ':('

### FIXED CODE ###

a,b = map(int,raw_input().split())

if (a <= 8 and b <= 8):
	print("Yay!")
else:
	print(":(")
N = int(input().split())
S = str(input().split())
i = 0
count = 0
for i in range(N-2):
  if S[i] == "A" and S[i+1] == "B" and S[i+2] == "C":
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = str(input())
i = 0
count = 0
for i in range(N-2):
  if S[i] == "A" and S[i+1] == "B" and S[i+2] == "C":
    count += 1
print(count)
x = input().split()

a = int(x[0])
b = int(x[1])
c = int(x[2])
k = int(x[3])

if(a > k): # a > k
  print(a-k)
  exit()
elif(a == k):
  print(a)
  exit()
elif(k-a < b):  # k > a 
  print(a)
  exit()
elif(k-a == b):
  print(a)
  exit()
elif(k-a-b != 0)
  x = k - a - b
  print(a-x)
  exit()
  
  

### FIXED CODE ###

x = input().split()

a = int(x[0])
b = int(x[1])
c = int(x[2])
k = int(x[3])

if(a > k): # a > k
  print(k)
  exit()
elif(a == k):
  print(a)
  exit()
elif(a+ b > k):  # k > a 
  print(a)
  exit()
elif(k-a == b):
  print(a)
  exit()
else:
  x = k - a - b
  print(a-x)
  exit()
N, M=map(int,input().split())
if M==0:
	print("0 0")
else:
	ac=0
	pe=0
	ch=[0]*N
    Ch=[0]*N
	for i in range(M):
		a, b=input().split()
		a=int(a)-1
		if ch[a]==1:
			continue
		elif b=="WA":
			Ch[a]+=1
		else:
			ch[a]=1
			ac+=1
			pe+=Ch[a]
	print(ac,pe)

### FIXED CODE ###

N, M=map(int,input().split())
if M==0:
	print("0 0")
else:
	ac=0
	pe=0
	ch=[0]*N
	Ch=[0]*N
	for i in range(M):
		a, b=input().split()
		a=int(a)-1
		if ch[a]==1:
			continue
		elif b=="WA":
			Ch[a]+=1
		else:
			ch[a]=1
			ac+=1
			pe+=Ch[a]
	print(ac,pe)
print(x * 3)

### FIXED CODE ###

x = int(input())
print(x ** 3)
h, w, n = [int(i) for i in input().split()]
a, b = zip(*
  [[int(i) for i in input().split()] for j in range(n)])

board = [[0]*(w+1) for i in range(h+1)]

ans = [0] * 10
ans[0] = (h-2) * (w-2)

for a, b in zip(a, b):
  for i in range(max(2, a-1), min(h, a+2)):
    for j in range(max(2, b-1), min(w, b+2)):
      try:
        ans[board[i][j]] -= 1
        board[i][j] += 1
        ans[board[i][j]] += 1
      except:
        pass

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

### FIXED CODE ###

h, w, n = [int(i) for i in input().split()]
if n == 0:
  a = b = [0] 
else:
  a, b = zip(*
  [[int(i) for i in input().split()] for j in range(n)])

board = { }

ans = [0] * 10
ans[0] = max(0, (h-2)) * max(0, (w-2))

for a, b in zip(a, b):
  for i in range(max(2, a-1), min(h, a+2)):
    for j in range(max(2, b-1), min(w, b+2)):
      try:
        ans[board.get((i, j), 0)] -= 1
        board[(i, j)] = board.get((i, j), 0) + 1
        ans[board[(i, j)]] += 1
      except:
        pass

for i in range(10):
  print(ans[i])
import math

A, B, C ,D = map(int, input().split())


C_multiple = B // C - A // C
D_multiple = B // D - A // D 

if A % C == 0:
    C_multiple += 1
if A % D == 0:
    D_multiple += 1
        

CD_gcd = C * D / math.gcd(C,D) 
CD_multiple = B // CD_gcd - A// CD_gcd 
if A % CD_gcd == 0:
    CD_multiple += 1
***
print(C_multiple)
print(D_multiple)
print(CD_gcd)
print(CD_multiple)
***
ans = ( B - A + 1 ) - (C_multiple + D_multiple - CD_multiple)
print(int(ans))

### FIXED CODE ###

import math

A, B, C ,D = map(int, input().split())


C_multiple = B // C - A // C
D_multiple = B // D - A // D 

if A % C == 0:
    C_multiple += 1
if A % D == 0:
    D_multiple += 1
        

CD_gcd = C * D // math.gcd(C,D) 
CD_multiple = B // CD_gcd - A// CD_gcd 
if A % CD_gcd == 0:
    CD_multiple += 1



ans = ( B - A + 1 ) - (C_multiple + D_multiple - CD_multiple)
print(int(ans))
x, y, z = map(int, raw_input().split())
  
print(z+" "+x+" "+y)

### FIXED CODE ###

x, y, z = map(int, raw_input().split())
  
print(str(z)+" "+str(x)+" "+str(y))
import numpy as np
n,x = map(int, input().split())
l = list(map(int, input().split()))
pop = [0] * (n)
pre = 0
for idx,i in enumerate(l):
  pop[idx] = pre + i
  pre = pop[idx]

print(np.sum(np.array([0]+pop) <= x))

### FIXED CODE ###

import numpy as np
n,x = map(int, input().split())
l = list(map(int, input().split()))
pop = [0] * (n)
pre = 0
for idx,i in enumerate(l):
  pop[idx] = pre + i
  pre = pop[idx]

print(np.sum(np.array([0]+pop) <= x))
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    n = int(input)
    N = list(str(n))
    
    tmp = 0
    for i in N:
        tmp += i
        
    if n % tmp == 0:
        print("Yes")
    else:
        print("No")
            	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    n = int(input())
    N = list(str(n))
    
    tmp = 0
    for i in N:
        tmp += int(i)
        
    if n % tmp == 0:
        print("Yes")
    else:
        print("No")
            	
if __name__ == "__main__":
	main()
import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = round(np.median(numbers))
numbers-= b
number = np.abs(numbers)
print(number.sum())

### FIXED CODE ###

import numpy as np
N = int(input())
num = list(map(int,input().split()))
for i in range(1, N+1):
    num[i-1] -= i
numbers = np.array(num)
b = int(round(np.median(numbers)))
numbers-= b
number = np.abs(numbers)
print(number.sum())
import itertools
import math

D, G = map(int, input().split())

P = set()
p = {}
c = {}
s = {}
for i in range(1, D + 1):
    pi, ci = map(int, input().split())
    score = 100 * i * pi + ci
    P.add(i)
    s[i] = score
    p[i] = pi
    c[i] = ci


def complete(pset):
    score = 0
    solved = 0
    comped = set()
    i = 1
    for b in pset:
        if b:
            score += s[i]
            solved += p[i]
            comped.add(i)
        i += 1
    return score, solved, comped


def left(norm, comped):
    if norm <= 0:
        return 0
    for i in sorted(list(P - comped), reverse=True):
        res = int(math.floor(norm / (100 * i)))
        if res < p[i]:
            return res


ans = float("inf")
for pset in itertools.product((True, False), repeat=D):
    score, solved, comped = complete(pset)
    solved += left(G - score, comped)
    ans = min(ans, solved)

print(ans)


### FIXED CODE ###

import itertools
import math

D, G = map(int, input().split())

p = {}
c = {}
s = {}
for i in range(1, D + 1):
    pi, ci = map(int, input().split())
    score = 100 * i * pi + ci
    s[i] = score
    p[i] = pi
    c[i] = ci


def complete(pset):
    score = 0
    solved = 0
    comped = set()
    for i, b in zip(range(1, D + 1), pset):
        if b:
            score += s[i]
            solved += p[i]
            comped.add(i)
    leftset = set(list(range(1, D + 1))) - comped
    return score, solved, leftset


def left(norm, leftset):
    if norm <= 0 or len(leftset) == 0:
        return 0
    i = max(leftset)
    res = int(math.ceil(norm / (100 * i)))
    if res < p[i]:
        return res
    return float("inf")


ans = float("inf")
for pset in itertools.product((True, False), repeat=D):
    score, solved, leftset = complete(pset)
    solved += left(G - score, leftset)
    ans = min(ans, solved)

print(ans)
d,t,s=map(int,input().split())
if d<=t*s:
  print('Yes')
 e;se:
  print('No')

### FIXED CODE ###

d,t,s=map(int,input().split())
if d<=t*s:
  print('Yes')
else:
  print('No')
import sys
a, b = sys.stdin.readlines()
c = a*b
if (c % 2) == 0:
    print("Even")
else:
    print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
if ((a*b) % 2) == 0:
    print("Even")
else:
    print("Odd")
k = int(input())
s = input()
if len(s) <= k:
  print(s)
else:
  print(s[:k] _ '...')

### FIXED CODE ###

k = int(input())
s = input()
if len(s) <= k:
  print(s)
else:
  print(s[:k] + '...')
x=[]
for i in range(3):
  x[i]=int(input())
 print((x[0]+x[1])*x[2]/2)

### FIXED CODE ###

x=[]
for i in range(3):
  x.append(int(input()))
print(int((x[0]+x[1])*x[2]/2))
A,B=map(int,input().split())
if　(A+B)%2 !=0:
  print('IMPOSSIBLE')
else:
  print((A+B)//2)

### FIXED CODE ###

A,B=map(int,input().split())
if (A+B)%2 !=0:
  print('IMPOSSIBLE')
else:
  print((A+B)//2)
n = int(raw_input())
max = -10^9
min = 10^9
ans = -10^9
for i in range(n):
 x[i] = int(raw_input())
for s in range(n):
 for t in range(n):
  if ans < (x[n-1-s]-x[n-1-t]):
   ans=x[n-1-s]-x[n-1-t]
print ans

### FIXED CODE ###

n = int(raw_input())
max = -10**9
x1 = input() 
min = x1

for i in range(n-1):
 x = int(raw_input())

 if max < x-min:
  max = x- min
 if x< min:
  min = x
  
print max
n, m = map(int, input().split())
l = [0]*m
r = [0]*m
for i in range(m):
  p, q = map(int, input().split())
  l[i], r[i] = map(int, input().split())
print(max(min[r] - max[l] + 1, 0))

### FIXED CODE ###

n, m = map(int, input().split())
l = [0]*m
r = [0]*m
for i in range(m):
  l[i], r[i] = map(int, input().split())
print(max(min(r) - max(l) + 1, 0))
import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 0
cnt = 0
L = []
for i in range(N):
    if i < num:
        continue
    s = S[i]
    for j in range(i,N):
        if S[j] != s:
            L.append(j-num)
            num = j
            break
s = S[-1]
for i in range(N-1,-1,-1):
    if S[i] != s:
        L.append(N-1-i)
        break
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
start = 0
ans = 0
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
    start = 1
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
    if start == 1:
        cnt = (N+1)//2
    else:
        cnt = N//2
else:
    cnt = N//2
if cnt <= K:
    print(N)
    exit()
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
print(ans)

### FIXED CODE ###

import itertools
def s(): return input()
def I(): return map(int,input().split())

N,K = I()
S = list(s())
num = 1
cnt = 0
L = []
for i in range(N-1):
    if S[i] != S[i+1]:
        L.append(num)
        num = 0
        if S[i] == '0':
            cnt += 1
    num += 1
L.append(num)
if S[-1] == '0':
    cnt += 1
ruiseki = [0]+list(itertools.accumulate(L))
l = len(ruiseki)
if cnt <= K:
    print(N)
    exit()
start = 0
ans = 0
if S[0] == '0':
    start = 1
for i in range(start,l,2):
    if i+K*2+1 > l-1:
        break
    ans = max(ans,ruiseki[i+K*2+1]-ruiseki[i])
if S[0] == '0':
    ans = max(ans,ruiseki[K*2])
if S[-1] == '0':
    ans = max(ans,ruiseki[-1]-ruiseki[l-K*2-1])
print(ans)
S=input()

if S[1]==B:
  print('ARC')
else:
  print('ABC')

### FIXED CODE ###

S=input()

if S[1]=='B':
  print('ARC')
else:
  print('ABC')
import sys
import random
import bisect
from collections import deque

def cumsum(a):
    tmp = 0
    ret = []
    for i in range(len(a)):
        tmp += a[i]
        ret.append(tmp)
    return ret

x = input().split()
a = list(map(int, input().split()))
b = list(map(int, input().split()))
n, m, time = int(x[0]), int(x[1]), int(x[2])

#n, m = 100000, 100000
#time = 100000000
#a = list(random.choices(range(10000), k=n))
#b = list(random.choices(range(10000), k=m))

a_sum, b_sum = cumsum(a), cumsum(b)

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

print (ans)


### FIXED CODE ###

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)
while True:
    n, x = map(int, input().split())
    if (n == x == 0):
    break

    count = 0
    for a in range(1, n):
        for b in range((a + 1), n):
            for c in range((b + 1), n):
                Sum = a + b + c
                if (Sum == x):
                    count += 1
    print(count)

### FIXED CODE ###

while True:
    n, x = map(int, input().split())
    if (n == x == 0):
        break

    count = 0
    for a in range(1, x // 3):
        for b in range(a + 1, x // 2):
            for c in range(b + 1, n + 1):
                Sum = a + b + c
                if (Sum == x):
                    count += 1 
    print(count)
s=list(input())

int a = 0
while a < 3:
  if s[a] == "1":
    s[a] = "9"
  else s[a] == "9":
    s[a] = "1"
  a += 1

print(int(s))

### FIXED CODE ###

s=list(input())


a = 0
while a < 3:
  if s[a] == "1":
    s[a] = "9"
  elif s[a] == "9":
    s[a] = "1"
  a += 1

s = ''.join(s)


print(s)
n=input()
if A in n and B in n:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

a = input()
if 'A' in a and 'B' in a:
    print("Yes")
else:
    print("No")
import math

inp = str(input())

N, M = map(int, input().split())
count = 0
for _ in range(M):
    
    for i in inp:
        x, y = map(int, input().split())

        xx = int(x) ** 2
        yy = int(y) ** 2

        ans = math.sqrt(xx + yy)
        print(ans)

        if ans >= M:
            count += 1
        j += 1
    print(count)

### FIXED CODE ###

import math

N, D = map(int, input().split())
count = 0
for _ in range(N):
    x, y = map(int, input().split())
    xx = x ** 2
    yy = y ** 2

    ans = math.sqrt(xx + yy)
    if ans <= D:
        count += 1

print(count)
n, w = list(map(int, raw_input().split()))
weights = []
values = []

for _ in range(n):
    wi, vi = list(map(int, raw_input().split()))
    weights.append(wi)
    values.append(vi)

dp = [[0 for __ in range(w+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, w+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1] if weights[i-1] <= j else 0)

print(dp[n][w])

### FIXED CODE ###

n, w = list(map(int, raw_input().split()))
weights = []
values = []

for _ in range(n):
    wi, vi = list(map(int, raw_input().split()))
    weights.append(wi)
    values.append(vi)

dp = [[0 for __ in range(w+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, w+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1] if weights[i-1] <= j else 0)

print(dp[n][w])