Harryxun/stf_run huggingface dataset:
import numpy as np
N, M = map(int, input().split())
 
m10000 = -1
m5000 = -1
m1000 = -1
  
for a in range(N+1):
  for b in range(N+1-a):
    c = np.abs(N - a - b)
    X = 10000*a + 5000*b + 1000*c
    
    if X == M:
      m10000 = a
      m5000 = b
      m1000 = c
 
print(m10000, " ", m5000, " ", m1000)

### FIXED CODE ###


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

m10000 = -1
m5000 = -1
m1000 = -1
  
for a in range(N+1):
  for b in range(N+1-a):
    c = abs(N - a - b)
    X = 10000*a + 5000*b + 1000*c
    
    if X == M:
      m10000 = a
      m5000 = b
      m1000 = c

print(m10000, " ", m5000, " ", m1000)
import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

mod = 10**9+7

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % mod
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i == k - 1 or i_n+1 >= len(a_neg) or (i_p+1 >= len(a_pos) and a_pos[i_p] * a_pos[i_p+1] > a_neg[i_n] * a_neg[i_n+1]):
            ans = ans * a_pos[i_p] % mod
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % mod * a_neg[i_n+1] % mod
            i_n += 2
            i += 2
print(ans)


### FIXED CODE ###

import sys

input = sys.stdin.readline

n_k = list(map(int, input().split()))
n = n_k[0]
k = n_k[1]
a = list(map(int, input().split()))
a_pos = list(filter(lambda v: v >= 0, a))
a_neg = list(filter(lambda v: v < 0, a))

a_pos.sort(reverse=True)
a_neg.sort()

mod = 10**9+7

ans = 1
if n == k:
    for a_i in a:
        ans = ans * a_i % mod
elif len(a_pos) == 0 and k % 2 == 1:
    for i in reversed(range(len(a_neg) - k, len(a_neg))):
        ans = ans * a_neg[i] % mod
else:
    i_p = 0
    i_n = 0
    i = 0
    while i < k:
        if i_p < len(a_pos) and (i == k - 1 or i_n+1 >= len(a_neg) or a_pos[i_p] * (a_pos[i_p+1] if i_p+1 < len(a_pos) else 1) > a_neg[i_n] * a_neg[i_n+1]):
            ans = ans * a_pos[i_p] % mod
            i_p += 1
            i += 1
        else:
            ans = ans * a_neg[i_n] % mod * a_neg[i_n+1] % mod
            i_n += 2
            i += 2
print(ans)
print(input().tranprint(input().translate(str.maketrans("1", "9"))))slate(str.maketrans("1", "9")))

### FIXED CODE ###

print(input().translate(str.maketrans("19", "91")))
a,b,c = map(int,input().split())
counter = 0
if a ==1:
    counter += 1
if b ==1:
    counter += 1
if c ==1:
    counter += 1

print(counter)

### FIXED CODE ###

print(input().count("1"))
import sys
sys.setrecursionlimit(10**9)
input = lambda:sys.stdin.readline().rstrip()

def Warshall_Floyd(d):
    #dist[i][j]:iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d
############################
n, m, l = map(int, input().split())
f_inf = float('inf')
dist = [[f_inf]*n for _ in range(n)]
for i in range(m): dist[i][i] = 0

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

dist = Warshall_Floyd(dist)

dist2 = [[f_inf]*n for _ in range(n)]
for i in range(m): dist2[i][i] = 0
for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            dist2[i][j] = 1

dist2 = Warshall_Floyd(dist2)

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    ans = dist2[s-1][t-1]-1
    if dist2[s-1][t-1] == f_inf:
      ans = -1
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, L = map(int, input().split())
    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if e[s][t] == float('inf'):
            print(-1)
            continue
        ans = e[s][t]
        print(ans-1)


if __name__ == "__main__":
    main()
# 095 c
a, b, c, x, y = map(int,input().split())

mast = max(x,y)
ans =  c *2 *i

for i in range(mast+1):
    price = a * max(x-i,0) + b * max(y-i,0) + c *2 *i
    ans =min(ans,price) 
    
print(ans)

### FIXED CODE ###

a, b, c, x, y = map(int,input().split())

mast = max(x,y)
ans = float('INF')

for i in range(mast+1):
    price = a * max(x-i,0) + b * max(y-i,0) + c *2 *i
    ans =min(ans,price) 
    
print(ans)
s = input()
stack = [s[0]]
for i in range(1,len(s)):
    cur_str = stack[-1]
    new_str = s[i]
    if cur_str+new_str=="ST":
        stack.pop()
    else:
        stack.append(new_str)
print(len(stack))


### FIXED CODE ###

s = input()
stack = [s[0]]
for i in range(1,len(s)):
    if len(stack)==0:
        stack.append(s[i])
        continue
    else:
        cur_str = stack[-1]
        new_str = s[i]
        if cur_str+new_str=="ST":
            stack.pop()
        else:
            stack.append(new_str)
print(len(stack))
a = int(input())
b = int(input())
sum = 0
sum += max(a,b)
if a < b:
  a -= 1
else:
  b -= 1
sum += max(a,b)
print(sum)

### FIXED CODE ###

a,b = (int(i) for i in input().split())  
sum = 0
sum += max(a,b)
if a > b:
  a -= 1
else:
  b -= 1
sum += max(a,b)
print(sum)
n=int(input())
m=list(map(int,input().split()))
ans=[]
for i in range(n):
  for j in range(n-1-i,-1,-1):
    if not m[j]==j+1:
      continue
    #m[j]==j
    ans.append(j+1)
    m=m[:j]+m[j+1:]
if not len(m)==0:
  print(-1)
else:
  for i in range(n):
    print(ans[n-1-i])
    

### FIXED CODE ###

n=int(input())
m=list(map(int,input().split()))
ans=[]
for i in range(n):
  for j in range(n-1-i,-1,-1):
    if not m[j]==j+1:
      continue
    #m[j]==j
    ans.append(j+1)
    m=m[:j]+m[j+1:]
    break
if not len(m)==0:
  print(-1)
else:
  for i in range(n):
    print(ans[n-1-i])
n, k = map(int,input().split())
S = input()
S[k-1] = S[k-1].lower()
print(S)

### FIXED CODE ###

n, k = map(int,input().split())
S = input()
S = S[:k-1] + S[k-1].lower() + S[k:]
print(S)
a,b　=　input().split()
 
print(min(a*int(b),b*(int(a)))

### FIXED CODE ###

a,b=map(int,input().split())
s=sum(map(int,input().split()))
print("Yes" if s>=a else "No")
a, b, c = map(int, input())
if b-a == c-b : print('YES')
else: print('NO')



### FIXED CODE ###

a, b, c = map(int, input().split())
if b-a == c-b : print('YES')
else: print('NO')
A,B,C = map(int, input().split())


if A<C<B or B<C<A
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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


#もし家1と家2までの距離
if A<C<B or B<C<A:
    print("Yes")
else:
    print("No")
a,b,c,d = map(int,input().split())
print(max(a*c,a*d,b*c,b*d))


### FIXED CODE ###

x = int(input())
if x == 0:
  print(1)
else:
  print(0)
N, M = map(int, input().split())
a = list(map(int, input().split())

homework = sum(a)

if homework > N:
    print("-1")

else:
    print(N - homework)

### FIXED CODE ###

R = int(input())

import math

circle = 2 * R * math.pi

print(circle)
import numpy
n = int(input())

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

right=numpy.cumsum(test)
left=numpy.cumsum(test[::-1])[::-1]

diff = []

for i in range(n-1):
    diff.append(abs(right[i]-left[i+1]))
    #print(right[i]-left[i+1])
print(min(diff))

### FIXED CODE ###

import numpy

n = int(input())

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

right=numpy.cumsum(test)
left=numpy.cumsum(test[::-1])[::-1]

diff = []

for i in range(n-1):
    diff.append(abs(right[i]-left[i+1]))
print(min(diff))
n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007
fib = [1,1,2]
for i in range(3,n+1):
    fib.append((fib[i-2]+fib[i-1])%mod)
ans = 0
ans += fib[a[0]-1]

for i in range(1,m):
    if (a[i]-a[i-1]!=1):
        ans *= fib[a[i]-a[i-1]-2]
        ans %= mod
    else:
        print(0)
        exit()
ans *= fib[n-a[m-1]-1]
print(ans%mod)

### FIXED CODE ###

n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]
mod = 1000000007
fib = [1,1,2]
for i in range(3,n+1):
    fib.append((fib[i-2]+fib[i-1])%mod)
if (m==0):
    print(fib[n])
    exit()
ans = 0
ans += fib[a[0]-1]

for i in range(1,m):
    if (a[i]-a[i-1]!=1):
        ans *= fib[a[i]-a[i-1]-2]
        ans %= mod
    else:
        print(0)
        exit()
ans *= fib[n-a[m-1]-1]
print(ans%mod)
N, M = map(int,input().split())
a = [] 
for i in range(M):
    a.append(int(input()))
a.sort()
diff = [a[i+1]-a[i] for i in range(M-1)] if M!=1 else []
if diff and min(diff)==1 :
    print(0)
else:
    if not(diff):
        stairs = [a[0]-1,N-a[0]-1]
    else :
        stairs = [a[0]-1]+[diff[i]-2 for i in range(M-1)]+[N-a[-1]-1]
    
    t = [1,1]
    for i in range(max(stairs)-1):
        t.append(t[-1]+t[-2])
    ans = 1
    for i in stairs:
        ans *= t[i]
    print(ans%1000000007)

### FIXED CODE ###

N, M = map(int,input().split())
a = [] 

for i in range(M):
    a.append(int(input()))
a.sort()
diff = [a[i+1]-a[i] for i in range(M-1)] if M!=1 else []
if diff and min(diff)==1 :
    print(0)
else:
    if M==0:
        stairs = [N]
    elif not(diff):
        stairs = [a[0]-1,N-a[0]-1]
    else :
        stairs = [a[0]-1]+[diff[i]-2 for i in range(M-1)]+[N-a[-1]-1]
    
    t = [1,1]
    for i in range(max(stairs)-1):
        t.append(t[-1]+t[-2])
    ans = 1
    for i in stairs:
        ans *= t[i]
    print(ans%1000000007)
import math
a,b=map(int,input().split())
print(a*b/math.gcd(a,b))


### FIXED CODE ###

import fractions
a,b=map(int,input().split())
print(int(a*b/fractions.gcd(a,b)))
def count_max(road):
    num = len(road)
    used = [False for i in range(num)]
    res = 0
    for i in range(num):
        if used[i]:
            continue
        used[i] = True
        line = road[i][:]
        for j in line:
            used[j] = True
        count = 1
        while len(line):
            now_point = line.pop()
            count += 1
            next = [j for j in road[now_point] if not used[j]]
            for j in next:
                used[j] = True
            line += next
        res += count * (count - 1) // 2
    return res


def getparent(parent, place):
    my_parent = parent[place]
    if my_parent == place:
        return place
    parent[place] = getparent(parent, my_parent)
    return parent[place]

def main():
    ans = []
    n, m = list(map(int, input().split()))
    broad = [[] for i in range(n)]
    b_pair = []
    parent = [i for i in range(n)]
    parent_sum = [1 for i in range(n)]
    for i in range(m):
        a, b = list(map(int, input().split()))
        a -= 1
        b -= 1
        broad[a].append(b)
        broad[b].append(a)
        b_pair.append((a, b))
    sum_count = count_max(broad)
    ans.append(sum_count)
    b_pair.reverse()
    b_pair.pop()
    for p, q in b_pair:
        if getparent(parent, p) != getparent(parent, q):
            p, q = getparent(parent, p), getparent(parent, q)
            sum_count -= parent_sum[p] * parent_sum[q]
            parent_sum[p] += parent_sum[q]
            parent[q] = p
        ans.append(sum_count)
    ans.reverse()
    for i in ans:
        print(i)


if __name__ == "__main__":
    main()



### FIXED CODE ###

def getparent(parent, place):
    childrens = [place]
    while place != parent[place]:
        place = parent[place]
        childrens.append(place)
    for i in childrens:
        parent[i] = place
    return place


def main():
    ans = []
    n, m = list(map(int, input().split()))
    pairs = []
    parent = [i for i in range(n)]
    parent_sum = [1 for _ in range(n)]
    for i in range(m):
        a, b = list(map(int, input().split()))
        pairs.append((a - 1, b - 1))
    sum_count = n * (n - 1) // 2
    ans.append(sum_count)
    for p, q in reversed(pairs[1:]):
        np, nq = getparent(parent, p), getparent(parent, q)
        if np != nq:
            sum_count -= parent_sum[np] * parent_sum[nq]
            parent_sum[np] += parent_sum[nq]
            parent[nq] = np
        ans.append(sum_count)
    ans.reverse()
    for i in ans:
        print(i)


if __name__ == "__main__":
    main()
import math 
import bisect
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A=sorted(A)
left=0
right=max(A)
mid=N//2
while(right-left>=0):
    numofcut=0
    mid=(left+right)//2
    for i in range(N):
        if A[i]%mid==0:
            numofcut+=A[i]//mid -1
        else:
            numofcut+=A[i]//mid
    #print(numofcut)
    if numofcut>K:
        left=mid+1
    else:
        right=mid-1
    

print(mid)

### FIXED CODE ###

import math 
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A=sorted(A)
left=0
right=max(A)
mid=max((left+right)//2,1)

while(right-left>=1):
    numofcut=0
    
    for i in range(N):
        if A[i]%mid==0:
            numofcut+=(A[i]//mid) -1
        else:
            numofcut+=A[i]//mid
    #print(numofcut)
    if numofcut>K:
        left=mid+1
    else:
        right=mid
    mid=max((left+right)//2,1)
    if mid==1:
        break
print(mid)
n, k = map(int,input().split())
nk_abs = abs(n - k)
if n < nk_abs and n < k:
  print(n)
if k == 1:
  print(0)
else:
  print(n % nk_abs)

### FIXED CODE ###

n, k = map(int, input().split())
print(min(n % k, k - n % k))
data = list(map(int,input().split()))

ans = data[2]-(data[0]-data[1])

if ans > 0:
     print(ans)
else:
    print("0")


### FIXED CODE ###

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

# AA AB BB
max = max(data[0]+data[0]-1, data[0]+data[1], data[1]+data[1]-1)

print(max)
import math

ABC = input().split()

a = int(ABC[0])
b = int(ABC[1])
c = int(ABC[2])
#a = b = c = pow(10,9)

l = 2*math.sqrt(a*b)
r = c - a - b

lint = int(l)

rl = r-l

# print(str(l) + " " + str(r))

# print(str(l-float(lint)) + " " + str(rl))

# print(math.isclose(0,rl))
if  math.isclose(0,rl):
    print("Yes")
elif 0 < rl:
    print("Yes")
else:
    print("No")




### FIXED CODE ###

import math

ABC = input().split()

a = int(ABC[0])
b = int(ABC[1])
c = int(ABC[2])
#a = b = c = pow(10,9)

l2  = 4 * a * b
r = c - a - b
r2 = r * r

# if l2 < r2:
#     print("Yes")
# else:
#     print("No")

if r > 0 :
    if l2 < r2:
        print("Yes")
    else:
        print("No")
else:
    print("No")
lst=list(map(int,input().split()))
if 5 in lst:
  lst.remove(5)
else:
    ans='No'
if 7 in lst:
  lst.remove(7)
else:
    ans='No'
if 7 in lst:
  ans='Yes'
print(ans)

### FIXED CODE ###

lst=list(map(int,input().split()))
if 7 in lst:
  lst.remove(5)
else:
    ans='NO'
if 5 in lst:
  lst.remove(7)
else:
    ans='NO'
if 5 in lst:
  ans='YES'
print(ans)
a = int(input())
b = list(map(int,list(a)))

if a % sum(b) == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

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

if int(a) % sum(b) == 0:
  print("Yes")
else:
  print("No")
N,H = list(map(int, input().split()))
A=0
B=[]
for _ in range(N):
    a,b = list(map(int, input().split()))
    A = max(A, a)
    B.append(b)

B.sort(reverse=True)
from itertools import accumulate
B = list(accumulate(B))
HP_after_throw = H - B[-1]
print(HP_after_throw)
if HP_after_throw <= 0:
    for i,b in enumerate(B,1):
        if H<b:
            print(i)
            exit()
    raise AssertionError('error')
else:
    q,r = divmod(HP_after_throw, A)
    print(N+q+min(1, r))


### FIXED CODE ###

N,H = list(map(int, input().split()))
A=0
B=[]
for _ in range(N):
    a,b = list(map(int, input().split()))
    A = max(A, a)
    B.append(b)

B = sorted([b for b in B if b>A], reverse=True)
from itertools import accumulate
B = list(accumulate(B))
total_throw_damage = (B[-1] if len(B)>0 else 0)

HP_after_throw = H - total_throw_damage
if HP_after_throw <= 0:
    for i,b in enumerate(B,1):
        if H<=b:
            print(i)
            exit()
    raise AssertionError('error')
else:
    q,r = divmod(HP_after_throw, A)
    print(len(B)+q+min(1, r))
str = input()

if(str == 'ABC'):
  print("ARC")
  el:
    print("ABC")

### FIXED CODE ###

str = input()

if str == 'ABC':
  print("ARC")
else:
  print("ABC")
X, Y = input().split()

if X > Y:
  print('>')
elif X = Y:
  print('=')
else:
  print('<')

### FIXED CODE ###

X, Y = input().split()

if X > Y:
  print('>')
elif X == Y:
  print('=')
else:
  print('<')
n,m=map(int,input().split())
cnt=1
def plot():
    if cnt>=10**9+7:
        cnt %=10**9+7
    return cnt
if abs(n-m)>1:print(0);exit()
elif (n+m)%2==1:
    for i in range(n):
        cnt *=(i+1)
        plot()
    for j in range(m):
        cnt *=(j+1)
        plot()
    print(cnt)
else:
    cnt *=(n+m)
    n -=1
    for i in range(n):
        cnt *=(i+1)
        plot()
    for j in range(m):
        cnt *=(j+1)
        plot()
    print(cnt)

### FIXED CODE ###

n,m=map(int,input().split())
cnt=1
if abs(n-m)>1:print(0);exit()
elif (n+m)%2==1:
    for i in range(n):
        cnt *=(i+1)
        if cnt>=10**9+7:cnt %=10**9+7
    for j in range(m):
        cnt *=(j+1)
        if cnt >= 10 ** 9 + 7: cnt %= 10 ** 9 + 7
    print(cnt)
else:
    cnt *=(n+m)
    n -=1
    for i in range(n):
        cnt *=(i+1)
        if cnt >= 10 ** 9 + 7: cnt %= 10 ** 9 + 7
    for j in range(m):
        cnt *=(j+1)
        if cnt >= 10 ** 9 + 7: cnt %= 10 ** 9 + 7
    print(cnt)
N, U, V = map(int, input().split())
A = [[] for _ in range(N)]

import sys
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N

def DFS(x, pre, cnt):
    if C[x] < cnt:
        C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        if a == (U - 1):
            C[a] = cnt
            continue:
        
        DFS(a, x, cnt)


DFS(V - 1, -1, 0)
ans = max(C) - 1
if ans < 0:
    ans = 0
print(ans)


### FIXED CODE ###

N, U, V = map(int, input().split())
A = [[] for _ in range(N)]

import sys
import numpy as np
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N
D = [0] * N

def DFS(x, pre, cnt, C):
    C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        DFS(a, x, cnt, C)


DFS(V - 1, -1, 0, C)
DFS(U - 1, -1, 0, D)

E = np.array(C) > np.array(D)
C = np.array(C)
ans = max(C[E]) - 1
print(ans)
import sys
sys.setrecursionlimit(20000)
n,k=map(int,input().split())
ans=k
t=[set()for i in range(n)]
dp=[k]+[0]*(n-1)
for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].add(b)
  t[b-1].add(a)
no=1
w=k
b=True
def a(noo):
  global ans
  w=k
  for i in t[noo-1]:
    t[i-1].discard(noo)
    if w==0 and b:print(0);b=False
    dp[i-1]=w-2;ans=(ans*(w-2))%(10**9+7)
    w-=1
    a(i)
for i in t[no-1]:
  t[i-1].discard(no)
  w-=1
  dp[i-1]=w;ans=(ans*w)%(10**9+7)
  a(i)
if b:print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
n,k=map(int,input().split())
ans=k
t=[set()for i in range(n)]
dp=[k]+[0]*(n-1)
for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].add(b)
  t[b-1].add(a)
no=1
w=k
b=True
def a(noo):
  global ans
  w=k
  for i in t[noo-1]:
    t[i-1].discard(noo)
    if w==0:print(0);exit()
    dp[i-1]=w-2;ans=(ans*(w-2))%(10**9+7)
    w-=1
    a(i)
for i in t[no-1]:
  t[i-1].discard(no)
  w-=1
  dp[i-1]=w;ans=(ans*w)%(10**9+7)
  a(i)
print(ans)
from math import gcd

a,b,k = map(int, input().split())
print(gcd(a,b))

### FIXED CODE ###

a,b,k = map(int, input().split())
Ans = []
for i in range(1, 101):
    if a%i== 0 and b%i ==0:
        Ans.append(i)

Ans.sort(reverse = True)
print(Ans[k-1])
import sys
import copy
import bisect
import numpy as np

def solve(a,n,N,M,V,P):
    if N-n+1 >= V:
        b = copy.deepcopy(a)
        b[n-1] += M
        tmp = b[n-1]
        b = sorted(b[0:n], reverse=True)
        k = bisect.bisect_left(b,tmp)
        if k<=P-1:
            return True
        else:
            return False
    else:
        V2 = V-N+n-1
        b = copy.deepcopy(a[0:n])
        b[n-1] += M
        tmp = b[n-1]
        b.sort()
        k = bisect.bisect_left(b,tmp)
        k = len(b)-k
        if k+N-1-n < V:
            if P<=k:
                return False
            elif P>=n:
                return True
            else:
                V2 = V-N+n-1
                num = P-k-N+n-1
                aaa = min([V2-1, num])
                if (np.sum(a[n-num:n])+M*aaa+num-1)//num <= tmp:
                    return True
                else:
                    return False
        else:
            b = copy.deepcopy(a)
            b[n-1] += M
            tmp = b[n-1]
            b = sorted(b[0:n])
            k = bisect.bisect_right(b,tmp)
            k = len(b)-k
            if k<=P:
                return True
            else:
                return False

def main():
    N,M,V,P = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort(reverse=True)
    lo = 0
    hi = 2*N
    while lo + 1 < hi:
        cnt = (lo + hi) // 2
        if solve(a,cnt,N,M,V,P):
            lo = cnt
        else:
            hi = cnt

    return hi

if __name__ == '__main__':
    ans = main()
    print(ans)


### FIXED CODE ###

import bisect
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
eps = 0.1
def func(k):
    # print("tsrget:"+str(k))
    used = 0
    tmp = a[:k]+a[k+1:]
    val = a[k]+M
    x1 = N-1-bisect.bisect(tmp, val+eps)
    x2 = bisect.bisect(tmp, val-eps)
    x3 = N-(x1+x2+1)
    # print(tmp,val,x1,x2,x3)
    if x1 >= P:
        return False
    v = V - (x1+1)
    p = P - (x1+1)
    used += x1+1
    if v <= 0:
        return True
    # x2+x3問からあとp問はa[k]+Mを超えてもよい
    # x3が十分ある
    if x3 >= p > 0:
        x3 -= p
        v -= p
        used += p
        p = 0
    if p>0:
        p -= x3
        v -= x3
        used += x3
    if x2 >= p > 0:
        x2 -= p
        v -= p
        used += p
        p = 0
    if p>0:
        p -= x2
        v -= x2
        used += x2
    if v <= 0:
        return True
    # x2問からあとp問はa[k]+Mを超えてもよい
    tmp2 = tmp[:N-used]
    rest = sum([min(M,val-val2) for val2 in tmp2])
    # print(tmp2,N,x1,x3,p,v, rest)
    if rest >= M*v:
        return True
    return False

ok = N-1  # exist
ng = -1  # not exist
while abs(ok - ng) > 1:
    cnt = (ok + ng) // 2
    t = func(cnt)
    # print(t)
    if t:
        ok = cnt
    else:
        ng = cnt
print(N-ok)