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

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

dp = [float('INF')] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if n > i+j >= 0:
            dp[i+j] = min(dp[i+j], dp[i] + abs(hi[i] - hi[i+j]))

print(dp[-1])


### FIXED CODE ###

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

dp = [float('INF')] * n
dp[0] = 0

for i in range(n):
    for j in range(1, k+1):
        if n > i+j >= 0:
            dp[i+j] = min(dp[i+j], dp[i] + abs(hi[i] - hi[i+j]))

print(dp[-1])
### BUGGY CODE ###

import bisect

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

hist = []
count = 0
for i in range(n):
    count += 1
    if i == n - 1 or k[i] != k[i + 1]:
        hist.append(count)
        count = 0
hist.sort()

sumh = [0]
for i in range(len(hist)):
    sumh.append(sumh[-1] + hist[i])

def ok(h, d):
    i = bisect.bisect_left(hist, h)
    s = sumh[i] + h * (len(hist) - i)
    return s >= h * d

def binary_search(d):
    lo, hi = 0, 10 ** 10
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid, d):
            lo = mid
        else:
            hi = mid
    return lo

for d in range(1, n + 1):
    print(binary_search(d))


### FIXED CODE ###

import bisect

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

hist = []
count = 0
for i in range(n):
    count += 1
    if i == n - 1 or k[i] != k[i + 1]:
        hist.append(count)
        count = 0
hist.sort()

sumh = [0]
for i in range(len(hist)):
    sumh.append(sumh[-1] + hist[i])

def ok(h, d):
    i = bisect.bisect_left(hist, h)
    s = sumh[i] + h * (len(hist) - i)
    return s >= h * d

def binary_search(d):
    lo, hi = 0, n // d + 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid, d):
            lo = mid
        else:
            hi = mid
    return lo

for d in range(1, n + 1):
    print(binary_search(d))
### BUGGY CODE ###

_ = input()
a = [int(i) for i in input().split(' ')]
res = 9999999999999999999999999
for i in range(1,len(a)):
    s = sum(a[:i])
    t = sum(a[i:])
    temp = abs(s-t)
    res = min(temp,res)
print(res)

### FIXED CODE ###

import sys

n = int(input())
a = []
b = input().split(" ")
for i in range(n):
	a.append(int(b[i]))

for i in range(1, n):
	a[i] += a[i-1]

mn = abs(a[n-1] - 2*a[0])
for i in range(1, n-1):
	mn = min(mn, abs(a[n-1] - 2*a[i]))

print(mn)
### BUGGY CODE ###

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

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

cnt = 0

for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                cnt += 1

print(cnt)


### FIXED CODE ###

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

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

cnt = 0

for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
                cnt += 1

print(cnt)
### BUGGY CODE ###


K = int(input())
ans = 0
def gcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(gcd(a, b), c)
print(ans)

### FIXED CODE ###

K = int(input())
ans = 0
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(gcd(a, b), c)
print(ans)
### BUGGY CODE ###

xy = input()
XY = xy.split()
X = int(XY[0])
Y = int(XY[1])

a = True
for i in range(1, 1000000000):
    if i % X == 0:
        if i % Y != 0:
            a = False
            print(i)
            break
        else:
            break
if a:
    print(-1)

### FIXED CODE ###

xy = input()
XY = xy.split()
X = int(XY[0])
Y = int(XY[1])

a = True
i = 1

if X < Y:
    print(X)
    a = False
elif X > Y and X % Y != 0:
    while X * i <= X * Y:
        if (X * i) % Y != 0:
            print(X * i)
            a = False
            break
        else:
            i += 1
if a:
    print(-1)
### BUGGY CODE ###

import math
N = int(input())
S = [input() for i in range(N)]
count = 0
l = [False for i in range(N)]
for i, s in enumerate(S):
    if l[i]:
        continue
    sset = set(s)
    d = 0
    for j in range(i+1, N):
        if l[j]:
            continue
        for c in sset:
            if s.count(c) != S[j].count(c):
                break
        else:
            d += 1
            l[j] = True
    count += d if d <= 1 else d + math.factorial(d) / (2 * math.factorial(d - 2))
print(int(count))


### FIXED CODE ###

N = int(input())
S = [input() for i in range(N)]

count = 0
appeared = {}
for i in range(N):
    S[i] = "".join(sorted(list(S[i])))
    if S[i] in appeared:
        count += appeared[S[i]]
        appeared[S[i]] += 1
    else:
        appeared[S[i]] = 1
print(int(count))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A_ = [0] * (N+1)
for a in A:
    A_[a] += 1
A_ = sorted(A_)
c = 0
for i in range(N+1):
    A_[i] = c = A_[i] + c
A_.reverse()

Ans = [float("inf")] * (N+1)
for i in range(N):
    for j, a in enumerate(A_):
        d = a//(i+1)
        if Ans[i+j] > d:
            Ans[i+j] = d
        if d==0:
            break
    if j==0:
        for ii in range(i+1, N):
            Ans[ii] = 0
        break
del Ans[-1]
print("\n".join(map(str, Ans)))


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = [0] * (N+1)
    Cnt_A = [0] * (N+1)
    for a in A:
        Cnt_A[a] += 1
        cnt = Cnt_A[a]
        C[cnt] += 1
    cum_C = []
    cu = 0
    for c in C:
        cu += c
        cum_C.append(cu)
    Ans = []
    for k in range(1, N+1):
        # K = k のとき、 n 組以上作れる <=> 使えるカードが nk 枚以上
        # n 組以上作れる <=> 同じカードは n 枚以下
        # 同じカードは n 枚以下で全体として nk 枚以上用意できるか？
        ok, ng = 0, N//k+1
        while ok + 1 < ng:
            n = ok+ng>>1
            if cum_C[n] >= n*k:
                ok = n
            else:
                ng = n
        Ans.append(ok)
    print("\n".join(map(str, Ans)))

main()
### BUGGY CODE ###

k,s = map(int, input().split())
xyz = list(range(k+1))
cnt = 0
for x in xyz:
  for y in xyz:
    for z in xyz:
      if x+y+z == s:
        cnt += 1
print(cnt)

### FIXED CODE ###

k,s = map(int, input().split())
xyz = list(range(k+1))
cnt = 0
for x in xyz:
  for y in xyz:
    if 0 <= s - (x+y) <= k:
      cnt += 1
print(cnt)
### BUGGY CODE ###

n, m = map(int, input().split())
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for _ in range(m):
  price, _ = map(int, input().split())
  treasure = sum(1 << c-1 for c in map(int, input().split()))
  for bit in range((1 << n) - 1):
    next_bit = treasure | bit
    next_cost = price + dp[bit]
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

### FIXED CODE ###

n, m = map(int, input().split())
price = [0] * m
treasure = [0] * m
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << c-1
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for bit in range((1 << n) - 1):
  cost = dp[bit]
  for i in range(m):
    next_bit = treasure[i] | bit
    next_cost = price[i] + cost
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int,input().split())) for _ in range(q)]

# sum = sum(a)

for i in bc:
    b = i[0]
    c = i[1]
    a = [c if i==b else i for i in a]
    # print(a)
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
query = [list(map(int,input().split())) for _ in range(q)]

all_sum  = sum(a)

cnt = {}
for i in a:
    if i not in cnt:
        cnt[i] = 0
    cnt[i] += 1

for (b, c) in query:
    if b in cnt:
        all_sum -= b * cnt[b]
        all_sum += c * cnt[b]
        if c not in cnt:
            cnt[c]=0 
        cnt[c] += cnt[b]
        cnt[b] = 0
    print(all_sum)
### BUGGY CODE ###

s = input()
t = input()

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[(0, 0)] * (lent + 1) for _ in range(lens + 1)]
dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            length, pattern = dp[aindex + 1][bindex + 1]
            r = (length + 1, pattern | (2 << aindex))
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r
for aindex in range(lens):
    if (2 << aindex) & dp[0][0][1]:
        print(s[aindex], end="")
print()



### FIXED CODE ###

s = input()
t = input()

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

shift = [1 << x for x in range(3000 + 1)]

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r

ans = ""
ls = len(s)
lt = len(t)
ls = 0
lt = 0
while ls < lens and lt < lent:
    if dp[ls][lt] == dp[ls + 1][lt]:
        ls += 1
    elif dp[ls][lt] == dp[ls][lt + 1]:
        lt += 1
    else:
        ans += t[lt]
        ls += 1
        lt += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
L = len(format(max(a), 'b'))
x = [[0 for j in range(60)] for i in range(2)]
ans = 0
MOD = 10 ** 9 + 7
for i in a:
    i_str = list(format(i, '0' + str(L) + 'b'))[::-1]
    for j, s in enumerate(i_str):
        x[int(s)][j] += 1
for i in range(60):
    x0 = x[0][i]
    x1 = x[1][i]
    y = x0 * x1
    ans += y * 2 ** i % MOD
    ans %= MOD
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
L = len(format(max(a), 'b'))
x = [0 for i in range(L)]
ans = 0
MOD = 10 ** 9 + 7
for i in a:
    i_str = list(format(i, '0' + str(L) + 'b'))[::-1]
    for j, s in enumerate(i_str):
        if s == '1':
            x[j] += 1
b = 1
for i, xi in enumerate(x):
    ans += xi * (n - xi) * b % MOD
    ans %= MOD
    b *= 2
    b %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 10**9
for i in range(N):
    ans = min(S[0:i].count('W')+S[i+1:N].count('E'), ans)
    
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

wcnt = [(S[0]=='W')*1]+[0]*(N-1)
for i in range(1, N):
    wcnt[i] = wcnt[i-1]+(S[i]=='W')*1

w = wcnt[N-1]
e = N-w
ans = 10**9
for j in range(N):
    tmp = wcnt[j]
    ans = min(e+2*wcnt[j]-(S[j]=='W')*1-1-j, ans)
    
print(ans)
### BUGGY CODE ###

n = int(input())
ls = list(map(int,input().split()))
ls.sort()
p = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if ls[k] < ls[i] + ls[j]:
                p += 1
print(p)

### FIXED CODE ###

n = int(input())
ls = list(map(int,input().split()))
ls.sort()
p = 0
def is_ok(arg,l):
    return ls[arg] < l
def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        l = ls[i] + ls[j]
        if is_ok(mid,l):
            ok = mid
        else:
            ng = mid
    return ok
for i in range(n-2):
    for j in range(i+1,n-1):
        ng = n
        ok = j
        m = meguru_bisect(ng, ok)
        p += m-j 
print(p)
### BUGGY CODE ###

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

X.sort()

Y = []
for i in range(M-1):
  Y.append(abs(X[i]-X[i+1]))
  Y.sort()
  
res=0
for i in range(M-N):
  res=res+Y[i]

print(res)

### FIXED CODE ###

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

X.sort()

Y = []
for i in range(M-1):
  Y.append(abs(X[i]-X[i+1]))
  
Y.sort()
  
res=0
for i in range(M-N):
  res=res+Y[i]

print(res)
### BUGGY CODE ###

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

def check(A):
  if 0 in A:
    return 0
  a=1
  for i in A:
      a=a*i
  if a>1000000000000000000:
    return(-1)
  return a

print(check(A))


### FIXED CODE ###

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

ans=1

if 0 in A:
    print(0)
    exit()

for i in A:
   ans=ans*i
   if ans>10**18:
    print(-1)
    exit()


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

a,b=map(int,input().split())
import fractions
n=fractions.gcd(a,b)
c=int(n**0.5)+2
import math

# 0以上整数x「未満」の素数をリストに格納して返す
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
kosuu=0
pri=0
for p in range(2, n):
    if n % p == 0:
        pri+=1
if pri==0:
    j=n+1
else:
    j=c

for i in primes(j):
    if n%i==0:
        kosuu+=1
print(kosuu+1)

### FIXED CODE ###

a,b=map(int,input().split())
import fractions
n=fractions.gcd(a,b)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
#print(factorization(n))
if factorization(n)==[[1,1]]:
  print(1)
else:
  print(len(factorization(n))+1)
### BUGGY CODE ###

A_cards = list(input())
B_cards = list(input())
C_cards = list(input())
who = "a"
while(True):
    if(who == "a"):
        if(len(A_cards)==0):
            print("A")
            exit()
        else:
            who = A_cards[0]
            del A_cards[0]
    elif(who == "b"):
        if(len(B_cards)==0):
            print("B")
            exit()
        else:
            who = B_cards[0]
            del B_cards[0]
    else:
        if(len(C_cards)==0):
            print("C")
            exit()


### FIXED CODE ###

A_cards = list(input())
B_cards = list(input())
C_cards = list(input())
who = "a"
while(True):
    if(who == "a"):
        if(len(A_cards)==0):
            print("A")
            exit()
        else:
            who = A_cards[0]
            del A_cards[0]
    if(who == "b"):
        if(len(B_cards)==0):
            print("B")
            exit()
        else:
            who = B_cards[0]
            del B_cards[0]
    if(who == "c"):    
        if(len(C_cards)==0):
            print("C")
            exit()
        else:
            who = C_cards[0]
            del C_cards[0]
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n // r + 1):
  for j in range((n - i * r) // g + 1):
    if (n - r * i - g * j) / b == abs(int((n - r * i - g * j) / b)):
      ans += 1
print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
ans = 0
for i in range(n // r + 1):
  for j in range((n - r * i) // g + 1):
    if (n - r * i - g * j) % b == 0 and (n - r * i - g * j) // b >= 0:
      ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
for i in range(N):
    Ai = A[i]
    A[i] = 0
    print(max(A))
    A[i] = Ai

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
max_num0 = max(A)
temp = A.index(max_num0)
A[temp] = 0
max_num1 = max(A)
A[temp] = max_num0

for i in range(N):
    if A[i] != max_num0:
        print(max_num0)
    else:
        print(max_num1)
### BUGGY CODE ###

N = int(input())
S = []
ans = N
for i in range(N):
    S.append(input())
    flg = 0
    j  = 0
    while(flg == 0 and j < i):
        if i != j:
            if len(S[j]) == len(S[i]):
                if S[j][0] == S[i][0]:
                    if S[j] == S[i]:
                        S[j] = ''
                        ans = ans - 1
                        flg = 1
        j = j+1
print(ans)

### FIXED CODE ###

N = int(input())
S = []
ans = N
S = [input() for i in range(N)]
#for i in range(N):
#    S.append(input())
S.sort()
for i in range(N-1):
    if S[i] == S[i+1]:
        ans = ans - 1
print(ans)
### BUGGY CODE ###

def main():
    r,g,b,n = map(int, input().split())
    res = 0
    for i in range(n+1):
        for j in range(n+1):
            if r*i + g*j <= n:
                if (n-(r*i + g*j)) % b==0:
                    res += 1           
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    r,g,b,n = map(int, input().split())
    tmp = [r,g,b]
    r,g,b = sorted(tmp, reverse=True)
    res = 0
    for i in range(n//r + 1):
        if i*r > n:
            break
        for j in range(n//g + 1):
            if r*i + g*j > n:
                break
            if (n-(r*i + g*j)) % b==0:
                res += 1           
    print(res)

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

s = input()
q = int(input())
hanten = 0
check = 0
for i in range(q):
    l = list(map(str, input().split()))
    if l[0] == "1":
        hanten += 1
    else:
        if l[1] == "1":
            if hanten%2 == 0:
                s = l[2] + s
            else:
                s = s + l[2]
        else:
            if hanten%2 == 0:
                s = s + l[2]
            else:
                s = l[2] + s
 
if hanten%2 == 1:
    s = s[::-1]
 
print(s)

### FIXED CODE ###

s = input()
q = int(input())
hanten = True
atm = ""
kts = ""
for i in range(q):
    l = input().split()
    if l[0] == "1":
        hanten = not hanten
    else:
        if l[1] == "1":
            if hanten:
                atm = l[2] + atm
            else:
                kts = kts + l[2]
        else:
            if hanten:
                kts = kts + l[2]
            else:
                atm = l[2] + atm

ans = atm + s + kts
if hanten == False:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

N = int(input())
X = input()
for i in range(N):
    if X[i] == '0':
        b = int(X, 2)
        b += 2**(N-i-1)
    else:
        b = int(X, 2)
        b -= 2**(N-i-1)
    a = bin(b)
    pop = str(a).count('1')
    c = 0
    while b != 0:
        b = b%pop
        a = bin(b)
        pop = str(a).count('1')
        c += 1
    print(c)

### FIXED CODE ###

n = int(input())
x = input()
pop = x.count("1")
lst1 = [1]
for i in range(n-1):
    lst1.append(lst1[-1] * 2 % (pop + 1))
lst1.reverse()
num1 = 0
for i in range(n):
    if x[i] == "1":
        num1 += lst1[i]
        num1 %= (pop + 1)
if pop == 1 or pop == 2:
    lst2 = [0] * n
else:
    lst2 = [1]
    for i in range(n-1):
        lst2.append(lst2[-1] * 2 % (pop - 1))
    lst2.reverse()
    num2 = 0
    for i in range(n):
        if x[i] == "1":
            num2 += lst2[i]
            num2 %= (pop - 1)
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        if pop == 1:
            print(0)
            continue
        elif pop == 2:
            print(1)
            continue
        else:
            num = num2 - lst2[i]
            num %= (pop - 1)
    else:
        num = num1 + lst1[i]
        num %= (pop + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
result = 0

for i in range(len(P)):
    subary = P[:i+1]
    if (min(subary) >= P[i]):
        result += 1

print(result)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
result = 0

minValue = P[0]

for i, p in enumerate(P):
  if (minValue >= p):
    result += 1
    minValue = p

print(result)
### BUGGY CODE ###

def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    #from bisect import bisect_left
    #print(a[5]+m)
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        # 3 2 2 1 1 0
        if ((a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-(i-p+1))*m)>=v*m:
            cnt+=1  
    print(cnt)

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    #from bisect import bisect_left
    #print(a[5]+m)
    s=sum(a[p-1:p])
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        # 3 2 2 1 1 0
        
        cnt+= ((a[i]+m)*(i-p+1)-s+(n-(i-p+1))*m)>=v*m
        try: s+=a[i]
        except: continue      
    print(cnt)

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

import math
from functools import reduce

n = int(input())
a_list = list(map(int, input().split()))

for i in range(n):
    for j in range(i + 1, n):
        if math.gcd(a_list[i], a_list[j]) != 1:
            if reduce(math.gcd, a_list) == 1:
                print("setwise coprime")
                exit()
            else:
                print("not coprime")
                exit()

print("pairwise coprime")


### FIXED CODE ###

import math
from functools import reduce
L = 10**6 + 1
n = int(input())
a_list = list(map(int, input().split()))
memo = [0] * L

for a in a_list:
    memo[a] += 1

for i in range(2, L):
    if sum(memo[i::i]) > 1:
        if reduce(math.gcd, a_list) == 1:
            print("setwise coprime")
            exit()
        else:
            print("not coprime")
            exit()

print("pairwise coprime")
### BUGGY CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if 2*j - i <= n - 1:
            k = 2*j - i
            if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]:
                cnt += 1
print(R*G*B - cnt)

### FIXED CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if j - i <= n - 1 - j:
            if s[i] != s[j] and s[j] != s[2*j - i] and s[i] != s[2*j - i]:
                cnt += 1
print(R*G*B - cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
h,w = map(int, raw_input().split())

area = [0,0,0]
ans = 999999999999
if(h%3 == 0 or w%3 == 0):
    ans = 0
for i in range(1,h/2+1):
    area[0] = i*w
    for j in range(w/2-int(math.sqrt(w/2)),w/2+1):
        area[1] = j*(h-i)
        area[2] = (w-j)*(h-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
    
for i in range(1,w/2+1):
    area[0] = i*h
    for j in range(h/2-int(math.sqrt(h/2)),h/2+1):
        area[1] = (j)*(w-i)
        area[2] = (h-j)*(w-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
print(ans)
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
h,w = map(int, raw_input().split())
 
area = [0,0,0]
ans = 10**15
if(h%3 == 0 or w%3 == 0):
    ans = 0
else:
    for i in range(1,h/2+1):
        area[0] = i*w
        tmp = w/2
        area[1] = tmp*(h-i)
        area[2] = (w-tmp)*(h-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        tmp = (h-i)/2
        area[1] = tmp*w
        area[2] = (h-i-tmp)*w
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        
    for i in range(1,w/2+1):
        area[0] = i*h
        tmp = h/2
        area[1] = tmp*(w-i)
        area[2] = (h-tmp)*(w-i)
        S = max(area)-min(area)
        if(S<ans):
            ans = S
        tmp = (w-i)/2
        area[1] = tmp*h
        area[2] = (w-i-tmp)*h
        S = max(area)-min(area)
        if(S<ans):
            ans = S
print(ans)