Harryxun/stf_run huggingface dataset:
def General_Binary_Search(L,R,cond,Integer=True,ep=1/(1<<20)):
    """一般的な二部探索を行う.
    L:解の下限
    R:解の上限
    cond:条件(1変数関数,単調減少を満たす)
    Integer:解を整数に制限するか?
    ep:Integer=Falseのとき,解の許容する誤差
    """

    if Integer:
        R+=1
        while R-L>1:
            C=L+(R-L)//2
            if cond(C):
                L=C
            else:
                R=C
        return L
    else:
        C=(R-L)/2
        while (R-C)>ep:
            if cond(C):
                L=C
            else:
                R=C
            C=L+(R-L)/2
        return C
#======================================
N,K=map(int,input().split())
A=list(map(int,input().split()))

def f(x):
    r=0
    for a in A:
        r+=(a+x-1)//x
    return r-N

print(-General_Binary_Search(-max(A),0,lambda x:f(-x)<=K))

### FIXED CODE ###

def BC(A,K):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    N=max(A)+1
    
    L,R=0,N
    while R-L>1:
        C=L+(R-L)//2

        M=0
        for a in A:
            M+=(a+C-1)//C-1

        if M<=K:
            R=C
        else:
            L=C
    return R


N,K=map(int,input().split())
A=list(map(int,input().split()))
print(BC(A,K))
print((N // 2) * (N - N // 2))

### FIXED CODE ###

N = int(input())
print((N // 2) * (N - N // 2))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
def main():
    s = input() 
    s = ''.join(reversed(s))
    n = len(s)
    T = ['0']
    for i in range(n):
        T.append(s[i]+T[i])
    mod_kind = []
    for i in T:
        mod_kind.append(int(i)%2019)
    d = Counter(mod_kind)
    ans = 0
    for i in d.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter 
from collections import defaultdict 

def main():
    s = input() 
    n = len(s)
    T = [0]
    P = 2019
    dd = defaultdict(int) 
    dd[0] += 1
    for i in range(1, n+1):
        x = (int(s[-i])*pow(10, i-1, P) + T[i-1])%P
        T.append(x)
        dd[x] += 1
    ans = 0
    for i in dd.values():
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()
import sys
S = list(input())
n = len(S)
def Remove(binList,lenList):
    for i in range(0,lenList-1):
        if (binList[i] == "0" and binList[i+1] == "1") or (binList[i] == "1" and binList[i+1] == "0"):
            del binList[i:i+2]
            return Remove(binList,lenList - 2)
    return binList
if n > 10**5:
    sys.exit()
S = Remove(S,n)
print(n-len(S))

### FIXED CODE ###

S = list(input())
obj = min(S.count("0"),S.count("1"))
print(obj*2)
N = int(input())
p = [0]*N
s = 0

for i in range(N):
   p[i] = int(input())
   s = s + p[i]
   
print(s-max(p)//2)
    


### FIXED CODE ###

D = int(input())

print("Christmas" + " Eve" * (25-D))
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_output(self, a=0, b=-1):
        return self.get_input(self.get_output_index(a,b))

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

inpl = lambda: list(map(int,input().split()))

if __name__ == '__main__':
    N, M = inpl()
    A = inpl()
    segt = SegmentTree(A, reverse=True)
    for _ in range(M):
        i = segt.get_output_index()
        v = segt.get_input(i)
        segt.set_input(i, v//2)
    print(sum(segt.value))

### FIXED CODE ###

import heapq
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
A = inpl()
q = []
for a in A:
    heapq.heappush(q,-a)
for _ in range(M):
    a = -heapq.heappop(q)
    a //= 2
    heapq.heappush(q,-a)
print(-sum(q))
import numpy as np
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))

hw = []

for i, ai in enumerate(a):
    for j in range(ai):
        hw.append(i+1)
        
hw = np.asarray(hw)
HW = np.reshape(hw, (H, W))

for i in range(H):
#     print(*HW[i])
    if i % 2 == 1:
        print(*HW[i][::-1])
    else:
        print(*HW[i])


### FIXED CODE ###

h,w=map(int,input().split())
n=int(input())
a=[int(i) for i in input().split()]
f=0
d=[]
for i in range(n):
  for j in range(a[i]):
    d.append(i+1)
    if len(d)==w and f:
      print(*d[::-1])
      f=0
      d=[]
    elif len(d)==w:
      print(*d)
      f=1
      d=[]
n=int(input())
l=list(map(int,input().split()))
ans="Yes"
for i in l:
  if i>=sum(L)-i:
    ans="No"
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
ans="Yes"
for i in l:
  if i>=sum(l)-i:
    ans="No"
print(ans)
int main():
  x = 0
  if N%2:
    x = N/2
  else:
    x = (N-1) / 2
   
  return K<=x

### FIXED CODE ###

N, K = [int(s) for s in input().split(' ')]
x = 0
if N%2:
    x = (N + 1) / 2
else:
    x = N/ 2
if x>=K:
    print("YES")
else:
    print("NO")
N, M = map(int, input().split())
wa, ac = [0]*(N+1), [0]*(N+1)
wa_ac = 0
for i in range(1, M+1):
  pi, Si = input().split()
  pi = int(pi)
  if Si == 'WA' and ac[pi] == 0: 
    wa[pi] += 1
  elif Si == 'AC' and ac[pi] == 0:
    ac[pi] += 1

for i in range(1, M+1):
  if ac[i] == 1:
    wa_ac += wa[i]

print('{} {}'.format(sum(ac), wa_ac))


### FIXED CODE ###

N, M = map(int, input().split())
wa, ac = [0]*(N+1), [0]*(N+1)
wa_ac = 0
for i in range(1, M+1):
  pi, Si = input().split()
  pi = int(pi)
  if Si == 'WA' and ac[pi] == 0: 
    wa[pi] += 1
  elif Si == 'AC' and ac[pi] == 0:
    ac[pi] += 1

for i in range(1, N+1):
  if ac[i] == 1:
    wa_ac += wa[i]

print('{} {}'.format(sum(ac), wa_ac))
#N = str(input())
N,A,B = map(int,input().split())
#X=list(map(int,input().split()))

if A==0:
    print(0)
else:
    b=N//(A+B)
    x=N%(A+B)

if x>A:
    x=A

print(b*A+x)


### FIXED CODE ###

#N = str(input())
N,A,B = map(int,input().split())
#X=list(map(int,input().split()))

if A==0:
    print(0)
    exit()
else:
    b=N//(A+B)
    x=N%(A+B)

    if x>A:
        print(b*A+A)
    else:
        print(b*A+x)
a = [list(map(int, input().split())) for i in range(3)]
n = int(input())
b = []
for i in range(7):
    b.append(int(input()))

for i in range(3):
    #for j in range(3):
    if a[0 + i][0] in b and a[0 + i][1] in b and a[0 + i][2] in b:
        print('Yes')
        quit()

for i in range(3):
    #for j in range(3):
    if a[0][0 + i] in b and a[1][0 + i] in b and a[2][0 + i] in b:
        print('Yes')
        quit()
        
if a[0][0] in b and a[1][1] in b and a[2][2] in b:
    print('Yes')
    quit()
if a[2][0] in b and a[1][1] in b and a[0][2] in b:
    print('Yes')
    quit()
print('No')

### FIXED CODE ###

a = [list(map(int, input().split())) for i in range(3)]
n = int(input())
b = []
for i in range(n):
    b.append(int(input()))
flag = False
for i in range(3):
    #for j in range(3):
    if a[0 + i][0] in b and a[0 + i][1] in b and a[0 + i][2] in b:
        #print('Yes')
        #quit()
        flag = True
for i in range(3):
    #for j in range(3):
    if a[0][0 + i] in b and a[1][0 + i] in b and a[2][0 + i] in b:
        #print('Yes')
        #quit()
        flag = True
        
if a[0][0] in b and a[1][1] in b and a[2][2] in b:
    #print('Yes')
    #quit()
    flag = True
if a[2][0] in b and a[1][1] in b and a[0][2] in b:
    #print('Yes')
    #quit()
    flag = True
#print('No')
if flag:
    print('Yes')
else:
    print('No')
S=input()  
  a, b, c = (int(i) for i in S.split())  
    d=(a+b+c)/17
    e=(max(a,b)-2+max(a,c)+max(b,c))/17
     
    if(d==1 and e==1): print("YES")
    else: print("NO")

### FIXED CODE ###

a, b, c = (int(i) for i in input().split())
d=(a+b+c)/17
e=(max(a,b)-2+max(a,c)+max(b,c))/17
     
if(d==1 and e==1): print("YES")
else: print("NO")
N = int(input())
A = [int(x) for x in input.split()]
B = [int(x) for x in input.split()]

tot = 0
for i in range(N):
    if A[i] <= B[i]:
        tot += A[i]
        B[i] -= A[i]
        A[i] = 0
    else:
        tot += B[i]
        B[i] = 0
        A[i] = A[i] - B[i]
    if B[i] >= 0:
        if A[i+1] <= B[i]:
            tot += A[i+1]
            A[i+1] = 0
            B[i] -= A[i+1]
        else:
            A[i+1] -= B[i]
            tot += B[i]
            B[i] = 0

print(tot)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

tot = 0
for i in range(N):
    if A[i] <= B[i]:
        tot += A[i]
        B[i] -= A[i]
        A[i] = 0
    else:
        tot += B[i]
        B[i] = 0
        A[i] = A[i] - B[i]
    if B[i] >= 0:
        if A[i+1] <= B[i]:
            tot += A[i+1]
            A[i+1] = 0
            B[i] -= A[i+1]
        else:
            A[i+1] -= B[i]
            tot += B[i]
            B[i] = 0

print(tot)
s = int(input())
l=[s]
i=1
def func(a):
  if a%2==0:
    return(a/2)
  else:
    return(3*a+1)

def Collatz(s):
  i+=1
  l.append(func(s))
  if not len(l) == len(set(l)):
    print(i)
    break
  else:
    continue

Collatz(s)

### FIXED CODE ###

s = int(input())
l=[s]
i=1
def func(a):
  if a%2==0:
    return(a/2)
  else:
    return(3*a+1)

while (len(l)==len(set(l))):
  i+=1
  s = func(s)
  l.append(s)
print(i)
s = input()
q = int(input())
ans_list1 = []
ans_list2 = []
flag = 1
for i in range(q):
    i = input().split()
    if i[0]=="1":
        flag *= -1
    else:
        if i[1]=='1':
            if flag==1:
                ans_list1.append(i[2])
            else:
                ans_list2.append(i[2])
        else:
            if flag==1:
                ans_list2.append(i[2])
            else:
                ans_list1.append(i[2])
    
    if flag==1:
        print(''.join(ans_list1[::-1]) + s +''.join(ans_list2))
    else:
        print(''.join(ans_list2[::-1]) + s[::-1] +''.join(ans_list1))

if flag==1:
    print(''.join(ans_list1[::-1]) + s +''.join(ans_list2))
else:
    print(''.join(ans_list2[::-1]) + s[::-1] +''.join(ans_list1))

### FIXED CODE ###

s = input()
q = int(input())
ans_list1 = []
ans_list2 = []
flag = 1
for i in range(q):
    i = input().split()
    if i[0]=="1":
        flag *= -1
    else:
        if i[1]=='1':
            if flag==1:
                ans_list1.append(i[2])
            else:
                ans_list2.append(i[2])
        else:
            if flag==1:
                ans_list2.append(i[2])
            else:
                ans_list1.append(i[2])

if flag==1:
    print(''.join(ans_list1[::-1]) + s +''.join(ans_list2))
else:
    print(''.join(ans_list2[::-1]) + s[::-1] +''.join(ans_list1))
s = input() #efabdd
t = input() #abcd
sl = len(s) #6
tl = input(t) #4
ans = tl #4
for i in range(sl-tl+1): #6-4+1 => 0, 1, 2
    c = 0
    for j in range(min(tl, sl): #min(4, 6) => 4
        if (s[i+j] != t[j]: #s[0] != t[0]..t[3]
            c += 1
    ans = min(c, ans) #min(0..4, 4)
print(ans)


### FIXED CODE ###

s = input() #efabdd
t = input() #abcd
sl = len(s) #6
tl = len(t) #4
ans = tl #4
for i in range(sl-tl+1): #6-4+1 => 0, 1, 2
    c = 0
    for j in range(min(tl, sl)): #min(4, 6) => 4
        if (s[i+j] != t[j]): #s[0] != t[0]..t[3]
            c += 1
    ans = min(c, ans) #min(0..4, 4)
print(ans)
K,X=map(int,input().split());print(for i in range(min(-1000000,X-K+1),max(1000000,X+K-1)))

### FIXED CODE ###

K,X=map(int,input().split())
for i in range(max(-1000000,X-K+1),min(1000000,X+K-1)+1):
    print(i)
import math
a, b, c, d = map(int, input().split())
cd_lcm = c * d // math.gcd(c, d)
l = b - a
print(l - (l // c + l // d - l // cd_lcm))

### FIXED CODE ###

from fractions import gcd
a, b, c, d = map(int, input().split())
if a == b:
    if a % c != 0 and a % d != 0:
        print(1)
    else:
        print(0)
    exit()
cd_lcm = c * d // gcd(c, d)
print(b - a + 1 - (b // c - (a-1) // c) - (b // d - (a-1) // d) + (b // cd_lcm - (a-1) // cd_lcm))
import math
from functools import reduce

def gcd(numbers):
    return reduce(math.gcd, numbers)

N, X = input().split(" ")
N = int(N)
X = int(X)
list = input().split(" ")
ans_list = [abs(X- int(list[i])) for i in range(N)]
print(gcd(ans_list))

### FIXED CODE ###

from fractions import gcd

N, X = map(int, input().split())
xlist = list(map(int, input().split()))
gaplist = []
for i in range(N):
    tmp = abs(xlist[i] - X)
    if tmp==0:
        tmp = 1
    gaplist.append(tmp)

ans = gaplist[0]
for i in range(1,N):
    ans = gcd(ans, gaplist[i])
    #次のxとの最大公約数を動的計画法求めるメソッド O(logX)

print(ans)
letters = list(input().split())
new_letters = []

for i, item in enumerate(letters, 1)
  if i % 2 != 0
    new_letters.append(item)
print(''.join(new_letters))

### FIXED CODE ###

letters = list(input())
new_letters = []

for i, ltr in enumerate(letters, 1):
  if i % 2 == 1:
    new_letters.append(ltr)

print(''.join(new_letters))
n,k=map(int,input().split())
kashi = [0] * n
cnt = 0
M = 0
for s in range(n):
	i=int(input())
	li=list(map(int,input().split()))
	for m in li:
		kashi[m-1] +=1

for i in kashi:
	if i == 0:
		cnt += 1

print(cnt)
    

### FIXED CODE ###

n,k=map(int,input().split())
kashi = [0] * n
cnt = 0
M = 0
for s in range(k):
	i=int(input())
	li=list(map(int,input().split()))
	if i > 0:
		for m in li:
			kashi[m-1] +=1

for i in kashi:
	if i == 0:
		cnt += 1

print(cnt)
n = int(input()) 
s = input()

t = []
for i in range(1, len(s)):
    if s[i] == s[i - 1]:
        continue
    else:
        t.append(s[i - 1])
t.append(s[i])
print(len(t))

### FIXED CODE ###

n = int(input()) 
s = input()

t = ""
cnt = 0
for i in s:
    if i != t:
        cnt += 1
        t = i
print(cnt)
x, y, a, b, c = map(int, input().split())
pn = list(map(int, input().split()))
qn = list(map(int, input().split()))
rn = list(map(int, input().split()))

pn.sort(reverse=True)
qn.sort(reverse=True)
rn.sort(reverse=True)

pn = pn[:x]
qn = qn[:y]
rcount = 0

while min(pn[-1], qn[-1]) <= rn[0]:
  if pn[-1] >= qn[-1]:
    rcount += rn[0]
    del qn[-1]
  else:
    rcount += rn[0]
    del pn[-1]
  del rn[0]
  if len(rn) == 0:
    break
  
print(sum(pn) + sum(qn) + rcount)


### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
pn = list(map(int, input().split()))
qn = list(map(int, input().split()))
rn = list(map(int, input().split()))

pn.sort(reverse=True)
qn.sort(reverse=True)

pqr = pn[:x] + qn[:y] + rn
pqr.sort(reverse=True)
  
print(sum(pqr[:x+y]))
s = input()

l = len(s)


def dfs(i):
    if i == l:
        print("YES")
        exit()
    if s[i:i+5] == "dream":
        if i+7 < l and s[i+5:i+7] == "er":
            dfs(i+7)
        dfs(i+5)
    elif s[i:i+5] == "erase":
        if i+6 < l and s[i+5] == "r":
            dfs(i+6)
        dfs(i+5)


dfs(0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

s = input()
l = len(s)


def dfs(i):
   #    print("->", s[i:])
    if i == l:
        print("YES")
        exit()
    if s[i:i+5] == "dream":
        if i+6 < l and s[i+5:i+7] == "er":
            dfs(i+7)
        dfs(i+5)
    elif s[i:i+5] == "erase":
        if i+5 < l and s[i+5] == "r":
            dfs(i+6)
        dfs(i+5)


dfs(0)
print("NO")
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
co = ['A','B','C','D','E','F','G','H','I','J']

for i in range(h):
    s = nn()
    if 'snuke' in s:
        j = s.index('snuke')
        print(co[j]+str(i+1))
        exit()

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
co = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']

for i in range(h):
    s = nn()
    if 'snuke' in s:
        j = s.index('snuke')
        print(co[j]+str(i+1))
        exit()
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    i = N - 1
    j = 0
    big = A[i]
    small = A[j]
    i -= 1
    j += 1
    res = []
    while i <= j:
        if i == j:
            small -= A[i]
            res.append((small, A[i]))
            break
        big -= A[j]
        res.append((big, A[j]))
        small -= A[i]
        res.append((small, A[i]))
        i -= 1
        j += 1

    print(big - small)
    for x, y in res:
        print(x, y)


solve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    big = A[-1]
    small = A[0]
    res = []
    for i in range(1, N - 1):
        if A[i] > 0:
            res.append((small, A[i]))
            small -= A[i]
        else:
            res.append((big, A[i]))
            big -= A[i]
    res.append((big, small))
    print(big - small)
    for x, y in res:
        print(x, y)


solve()
import fractions
a, b, c, d = [int(i) for i in input().split()]

c_left = [a // c - 1, a // c][a % c != 0]
c_right = b // c

c_number = c_right - c_left

d_left = [a // d - 1, a // d][a % d != 0]
d_right = b // d

d_number = d_right - d_left
cdgcd = (c * d) // fractions.gcd(c, d)

cd_left = [a // (cdgcd - 1), a // (cdgcd)][a % (cdgcd) != 0]
cd_right = b // (cdgcd)

cd_number = cd_right - cd_left

print(b - a + 1 -  (c_number + d_number - cd_number))

### FIXED CODE ###

import fractions

a, b, c, d = [int(i) for i in input().split()]

if c == 1 or d == 1:
    print(0)
    exit()

c_left = max(0, [a // c - 1, a // c][a % c != 0])
c_right = b // c

d_left = max(0, [a // d - 1, a // d][a % d != 0])
d_right = b // d

cdgcd = (c * d) // fractions.gcd(c, d)

cd_left = max(0, [a // cdgcd - 1, a // (cdgcd)][a % (cdgcd) != 0])
cd_right = b // (cdgcd)

c_number = c_right - c_left
d_number = d_right - d_left
cd_number = cd_right - cd_left

print(b - a + 1 - (c_number + d_number - cd_number))
def main():
    N, M, K = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    time = 0
    i = 0
    while (time + A[i] <= K):
        time += A[i]
        i += 1
        if i == N:
            break

    i2 = i-1#i2はAの一番下の変数を指すポインタ
    h = 0
    while (time + B[h] <= K):
        time += B[h]
        h += 1
        i += 1
        if h == M:
            break
    max = i
    #iは冊数

    i3 = i#今後比べていくときの合計冊数
    #print(time,i)
    if h == M:
        return max

    for j in range(i2+1):
        time -= A[i2]
        i3 -= 1
        while (time + B[h] <= K):
            time += B[h]
            h += 1
            i3 += 1
            if h == M:
                break
        #print(time,i3)

        if i3 > max:
            max = i3

        i2 -= 1

    return max

print(main())


### FIXED CODE ###

def main():
    N, M, K = map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    time = 0
    i = 0
    while (time + A[i] <= K):
        time += A[i]
        i += 1
        if i == N:
            break

    i2 = i-1#i2はAの一番下の変数を指すポインタ
    h = 0
    while (time + B[h] <= K):
        time += B[h]
        h += 1
        i += 1
        if h == M:
            break
    max = i
    #iは冊数

    i3 = i#今後比べていくときの合計冊数
    #print(time,i)
    if h == M:
        return max

    for j in range(i2+1):
        if i2 < 0:
            return max
        time -= A[i2]
        i3 -= 1
        while (time + B[h] <= K):
            time += B[h]
            h += 1
            i3 += 1
            if h == M:
                break
        #print(time,i3)

        if i3 > max:
            max = i3

        i2 -= 1
        if h == M:
            return max

    return max

print(main())
class UnionFind:
    def __init__(self, n):
        self.group = list(range(n))
    
    def find(self, x):
        cv = self.group[x]
        if cv != x:
            self.group[x] = self.find(cv)
        return self.group[x]
    
    def union(self, x, y):
        self.group[self.find(x)] = self.find(y)

import itertools, operator, math
class Combination:
    def __init__(self, fact=math.factorial, div=operator.itruediv):
        self.fact = fact
        self.div = div
    def C(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.div(
                self.fact(n),
                self.fact(n - m) * self.fact(m)
            )
    def H(self, n, r):
        return self.C(n - 1 + r, r)

N, M = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]

uf = UnionFind(N + 1)
comb = Combination()

group_size = dict([(i, 1) for i in range(1, N+1)])
cur = comb.C(N, 2)
ans = [cur]
for a, b in reversed(AB):
    x = uf.find(a)
    y = uf.find(b)
    if x != y:
        uf.union(a, b)
        cur -= group_size[y] * group_size[x]
        group_size[y] += group_size[x]
        del group_size[x]

    ans.append(cur)
for n in reversed(ans[:-1]):
    print(int(n))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.group = list(range(n))
    
    def find(self, x):
        cv = self.group[x]
        if cv != x:
            self.group[x] = self.find(cv)
        return self.group[x]
    
    def union(self, x, y):
        self.group[self.find(x)] = self.find(y)

N, M = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(M)]

uf = UnionFind(N + 1)
group_size = dict([(i, 1) for i in range(N+1)])
cur = N * (N-1) // 2
ans = [cur]
for a, b in reversed(AB):
    x = uf.find(a)
    y = uf.find(b)
    if x != y:
        cur -= group_size[y] * group_size[x]
        uf.union(a, b)
        group_size[y] += group_size[x]
        del group_size[x]
    ans.append(cur)

for n in reversed(ans[:-1]):
    print(n)