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

#16:38
n,m = map(int,input().split())
raw = [set() for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].add(b)
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [10**6 for _ in range(n)]
now = [r]
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      if pre[x] == y:
        continue
      pre[y] = x
      now.append(y)
for x in pre:
  if x != 10**6:
    print(x+1)
  else:
    print(0)

### FIXED CODE ###

#16:38
n,m = map(int,input().split())
raw = [[] for _ in range(n)]
precnt = [0 for _ in range(n)]
root = [1 for _ in range(n)]
for _ in range(n-1+m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw[a].append(b)
  precnt[b] += 1
  root[b] = 0
for i in range(n):
  if root[i] == 1:
    r = i
    break
pre = [-1 for _ in range(n)]
now = [r]
#print(precnt)
while now:
  last = now
  now = []
  for x in last:
    for y in raw[x]:
      precnt[y] -= 1
      if precnt[y] == 0:
        now.append(y)
      pre[y] = x
#print(pre)
#print(precnt)
for x in pre:
  print(x+1)
### BUGGY CODE ###

X,Y,Z,K = list(map(int,input().split()))
import numpy as np
A = np.array([(sorted(list(map(int,input().split())))[::-1]) for i in range(3)])
from itertools import product
AB = sorted([sum(i) for i in list(product(A[0],A[1]))])[::-1][:K]
for i in sorted([sum(i) for i in list(product(AB,A[2]))])[::-1][:K]:
    print(i)

### FIXED CODE ###

X,Y,Z,K = list(map(int,input().split()))
A = [(sorted(list(map(int,input().split())))[::-1]) for i in range(3)]
b = sorted([i+j for i in A[0] for j in A[1]])[-K:]
for i in sorted([i+j for i in b for j in A[2]])[-K:][::-1] :
  print(i)
### BUGGY CODE ###

def gcd(a, b, c):
    while b:
        a, b = b, a % b
    while c:
        a, c = c, a % c
    return a

n = int(input())
ans = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += gcd(i,j,k)
print(ans)    

### FIXED CODE ###

def gccd(a, b, c):
    while b:
        a, b = b, a % b
    while c:
        a, c = c, a % c
    return a

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

n = int(input())
ans = n * (n+1) //2
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans += gcd(i,j) * 6
if n >2:
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            for k in range(j+1,n+1):
                ans += gccd(i,j,k) * 6
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

k = int(input().rstrip())

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

ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            ans += gcd([a, b, c])

print(ans)

### FIXED CODE ###

import math

k = int(input().rstrip())


ans = 0
for a in range(1, k + 1):
    if a == 1:
        ans += k * k
    else:
       for b in range(1, k + 1):
            if b == 1:
               ans += k
            else:
                if a == b:
                    tmp = a
                    if tmp == 1:
                        ans += k
                    else:
                        for c in range(1, k + 1):
                            if c == 1:
                                ans += 1
                            else:
                                ans += math.gcd(tmp, c)
                else:
                    tmp = math.gcd(a, b)
                    if tmp == 1:
                        ans += k
                    else:
                        for c in range(1, k + 1):
                            if c == 1:
                                ans += 1
                            else:
                                ans += math.gcd(tmp, c)

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

R,G,B,N=map(int,input().split())
 
cnt =0
 
# R*r + G*g + B*b == N
 
rm =int(N/R)
gm =int(N/G)
bm = int(N/B)
 
for r in range(rm+1):
    for g in range(gm+1):
        if R*r + G*g > N :
                break
        for b in range(bm+1):
            if R*r + G*g + B*b > N :
                break
            if R*r + G*g + B*b == N :
                cnt +=1
print(cnt)

### FIXED CODE ###

R,G,B,N=map(int,input().split())

#R*r+G*g+B*b==n
ir=int(N/R)+1
ig=int(N/G)+1
ib=int(N/B)+1
s=0
for r in range(ir):
    for g in range(ig):
        if(R*r+G*g>N):
            break;
        if((N-R*r-G*g)%B==0):
            s+=1
print(s)
### BUGGY CODE ###

from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def conb(n,r): return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n,k = inpl()
s = input()
cntlr = []
tmp = ''
cnt = 0
for i in range(n):
    if i == 0:
        tmp = s[i]
        cnt = 1
    else:
        if tmp == s[i]:
            cnt += 1
        else:
            cntlr.append(cnt)
            tmp = s[i]
            cnt = 1
cntlr.append(cnt)
# print(cntlr)
nn = len(cntlr)
if nn == 1:
    print(n-1)
    quit()
if nn%2==0:
    for i in range(k):
        if len(cntlr) > 4:
            cntlr[0] += cntlr[len(cntlr)-3]
            cntlr[len(cntlr)-2] += cntlr[1]
            del(cntlr[len(cntlr)-3])
            del(cntlr[1])
            for k in range((len(cntlr)-3)//2):
                cntlr[k+1],cntlr[len(cntlr)-3-k]=cntlr[len(cntlr)-3-k],cntlr[k+1]
        elif len(cntlr) ==  4:
            cntlr[0] += cntlr[1] + cntlr[2]
            del(cntlr[1:3])
        else:
            print(n-1)
            quit()
else:
    for i in range(k):
        if len(cntlr) > 3:
            cntlr[0] += cntlr[len(cntlr)-2]
            cntlr[-1] += cntlr[1]
            del(cntlr[len(cntlr)-2])
            del(cntlr[1])
            for k in range((len(cntlr)-2)//2):
                cntlr[k+1],cntlr[-2] = cntlr[-2],cntlr[k+1]
        else:
            print(n-1)
            quit()
res = 0
for i in cntlr:
    if i >= 2:
        res += i-1
print(res)


### FIXED CODE ###

from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def conb(n,r): return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n,k = inpl()
s = input()
cnt = 0
for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
print(min(cnt+2*k, n-1))
### BUGGY CODE ###

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

s = []

for i in range(n):
    a, b = map(int, input().split())
    for j in range(b):
        s.append(a)

s = sorted(s)

print(s[k-1])

### FIXED CODE ###

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

A = []

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

A.sort(key=lambda x:x[0])


f = k
i = 0
while f > 0:
    f -= A[i][1]
    i += 1

print(A[i-1][0])
### BUGGY CODE ###

n = int(input())
s = str(input())
ans = ''
for i in range(n):
  if i == 0:
    ans += s[i]
  elif ans[-1] != s[i]:
    ans += s[i]
print(len(ans))
  

### FIXED CODE ###

n = int(input())
s = input()
prev = ''
ans = 0
for i in range(n):
  if s[i] != prev:
    ans += 1
    prev = s[i]
print(ans)
### BUGGY CODE ###

def sol(l,o):
    t=len(bin(o))

    for i in range(o,0,-1):
        x=bin(i)
        if len(x)<t: break
        for a,b in enumerate(x[::-1]):
            if b=="b": break
            if b=="1": l[a]=(l[a]+1)%2
    return l


l=[0]*42
n,k=map(int,input().split())
#"ans=n
ans=0
l=sol(l,n-1)
l=sol(l,k)
p=1
for i in l:
    ans+=i*p
    p*=2
print(ans)

### FIXED CODE ###

p=[0]*42
q=[0]*42
x=1
a,b=map(int,input().split())
if a==b:
    print(a)
    exit()

a-=1
for i in range(42):
    if b//x<1: break
    if x==1:
        q[0]=((b+1)//2)%2
    else:
        q[i]=[0,((b+1)%x)%2][(b//x)%2]
    x*=2
x=1
for i in range(42):
    if a//x<1: break
    if x==1:
        p[0]=((a+1)//2)%2
    else:
        p[i]=[0,((a+1)%x)%2][(a//x)%2]
    x*=2
x=1
ans=0
for i in range(42):
    ans+=(p[i]^q[i])*x
    x*=2
print(ans)
### BUGGY CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

H,W = map(int,input().split())

S = [list(input()) for i in range(H)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

start = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            start.append((i,j))

def distance(i,j):
    not_visited = [[-1]*W for i in range(H)]
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j,"#"))

    while stack != deque([]):
        y,x,mark = stack.popleft()
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and mark != S[y+dy[i]][x+dx[i]]  and not_visited[y+dy[i]][x+dx[i]] == -1:
                not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
                if mark == "#":
                    stack.append((y+dy[i],x+dx[i],"."))
                else:
                    stack.append((y+dy[i],x+dx[i],"#"))

    odd = 0
    for i in range(H):
        for j in range(W):
            if not_visited[i][j] > 0 and not_visited[i][j] % 2 == 1:
                odd += 1
    
    return odd

ans = 0
if start:
    for sta in start:
        i,j = sta[0],sta[1]
        ans += distance(i,j)
    print(ans)
else:
    print(ans)

### FIXED CODE ###

import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

H,W = map(int,input().split())

S = [list(input()) for i in range(H)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

start = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            start.append((i,j))

not_visited = [[-1]*W for i in range(H)]
def distance(i,j):
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j,"#"))

    b,w = 1,0

    while stack != deque([]):
        y,x,mark = stack.popleft()
        for i in range(4):
            if 0<= x+dx[i] <W and 0<= y+dy[i] <H and mark != S[y+dy[i]][x+dx[i]]  and not_visited[y+dy[i]][x+dx[i]] == -1:
                not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x] + 1
                if mark == "#":
                    stack.append((y+dy[i],x+dx[i],"."))
                    w += 1
                else:
                    stack.append((y+dy[i],x+dx[i],"#"))
                    b += 1
    
    return b*w

ans = 0
for i in range(H):
    for j in range(W):
        if not_visited[i][j] == -1 and S[i][j] == "#":
            ans += distance(i,j)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
li = []
li.append(N)
aoki = N
while aoki <= min(li):
    aoki = abs(min(li) - K)
    li.append(aoki)
print(min(li))


### FIXED CODE ###

n, k = map(int, input().split())
if n==0 or k==1:
    print(0)
    exit()
elif n<k:
    print(min(n, abs(n-k)))
    exit()
elif n % k == 0:
    print(0)
    exit()
else:
    mx = n%k
print(min(abs(mx-k), mx))
### BUGGY CODE ###

h,w,k=map(int,input().split())
sx,sy,tx,ty=map(int,input().split())
b=[[-1]*(w+2)]
for i in range(h):
  s=input()
  bb=[-1]
  for j in s:
    if j==".":bb.append(0)
    else:bb.append(-1)
  bb.append(-1)
  b.append(bb)
b.append([-1]*(w+2))
from collections import deque
d=deque()
d.append((sx,sy))
while d:
  x,y=d.popleft()
  if x==tx and y==ty:
    exit(print(b[x][y]))
  for i in range(1,k+1):
    if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
    b[x-i][y]=b[x][y]+1
    d.append((x-i,y))
  for i in range(1,k+1):
    if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
    b[x+i][y]=b[x][y]+1
    d.append((x+i,y))
  for j in range(1,k+1):
    if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
    b[x][y-j]=b[x][y]+1
    d.append((x,y-j))
  for j in range(1,k+1):
    if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
    b[x][y+j]=b[x][y]+1
    d.append((x,y+j))
print(-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###

def main():
    n=int(input())
    s=input()
    r=[]
    g=[]
    b=[]
    ans=0
    for i in range(n):
        if s[i]=='R':
            r.append(i)
        if s[i]=='G':
            g.append(i)
        if s[i]=='B':
            b.append(i)
    for i in r:
        for j in g:
            for k in b:
                if k+i!=2*j and i+j!=2*k and j+k!=2*i:
                    ans+=1
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    r=[]
    g=[]
    b=[]
    rdict={}
    gdict={}
    bdict={}
    ans=0
    for i in range(n):
        if s[i]=='R':
            r.append(i)
            rdict[2*i]=2*i
        if s[i]=='G':
            g.append(i)
            gdict[2*i]=2*i
        if s[i]=='B':
            b.append(i)
            bdict[2*i]=2*i
    ans=len(r)*len(g)*len(b)
    for i in r:
        for j in g:
            if i+j in bdict:
                ans-=1
    for i in g:
        for j in b:
            if i+j in rdict:
                ans-=1
    for i in b:
        for j in r:
            if i+j in gdict:
                ans-=1
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mi=abs(sum(a)-2*a[0])
k=a[0]
t=sum(a)
for i in range(1,n-1):
    k=k+a[i]
    if abs(sum(a)-2*k) < mi:
        mi=abs(sum(a)-2*k)
print(mi)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
t=sum(a)
mi=abs(t-2*a[0])
k=a[0]

for i in range(1,n-1):
    k=k+a[i]
    if abs(t-2*k) < mi:
        mi=abs(t-2*k)
print(mi)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
SIZE=1000003; MOD=998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
inv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]

num = [0]*SIZE
db = [0]*SIZE
for i in a:
    num[i] += i
    db[i] += i*i
    db[i] %= MOD

def zeta(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(n//p,0,-1):
                sieve[k*p] = False
                a[k] += a[k*p]
                a[k] %= MOD
    return a


def meb(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(1,n):
                if k*p >= n: break
                sieve[k*p] = False
                a[k] -= a[k*p] 
                a[k] %= MOD
    return a


#n = 1000000

n = 1000001

#zn = [i*i for i in zeta(num,n)]
#zdb = zeta(db,n)
#print(zn[:20])
#print(zdb[:20])

zn = [i*i for i in zeta(num,n)]
zdb = zeta(db,n)
ans = [i-j for i,j in zip(zn, zdb)]

#ans = [i*i-j for i,j in zip(zeta(num,n), zeta(db,n))]

#print(ans[:20])
#print(meb(ans,n)[:20])

res = 0
for i,c in enumerate(meb(ans,n)):
    res = (res + c*inv[i])%MOD
        
print(res*inv[2]%MOD)









### FIXED CODE ###

# coding: utf-8
# Your code here!
SIZE=1000001; MOD=998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
inv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]

num = [0]*1000001
db = [0]*1000001
for i in a:
    num[i] += i
    db[i] += i*i
    db[i] %= MOD

def zeta(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(n//p,0,-1):
                sieve[k*p] = False
                a[k] += a[k*p]
                a[k] %= MOD
    return a


def meb(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(1,n):
                if k*p >= n: break
                sieve[k*p] = False
                a[k] -= a[k*p] 
                a[k] %= MOD
    return a


#n = 1000000

n = 1000000

#zn = [i*i for i in zeta(num,n)]
#zdb = zeta(db,n)
#print(zn[:20])
#print(zdb[:20])

zn = [i*i for i in zeta(num,n)]
zdb = zeta(db,n)
ans = [i-j for i,j in zip(zn, zdb)]

#ans = [i*i-j for i,j in zip(zeta(num,n), zeta(db,n))]

#print(ans[:20])
#print(meb(ans,n)[:20])

res = 0
for i,c in enumerate(meb(ans,n+1)):
    res = (res + c*inv[i])%MOD
        
print(res*inv[2]%MOD)
### BUGGY CODE ###

#!/usr/bin/env python3

# from functools import lru_cache

n = int(input())


# @lru_cache(maxsize=None)
# def dp(num, typ, mod=10 ** 9 + 7):
#     print(num, typ)
#     if num == 1:
#         if typ == 1:  # contain 0 not 9
#             return 1
#         elif typ == 2:  # contain 9 not 0
#             return 1
#         elif typ == 3:  # not contain
#             return 8
#         elif typ == 0:
#             return 0

#     if typ == 0:
#         return (dp(num - 1, 1) + dp(num - 1, 2) + dp(num - 1, 0) * 10) % mod
#     elif typ == 1:  # contain 0 not 9
#         return (dp(num - 1, 1) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 2:  # contain 9 not 0
#         return (dp(num - 1, 2) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 3:  # not contain
#         return (dp(num - 1, 3) * 8) % mod


# print(dp(n, 0))

dp = [[0 for j in range(4)] for i in range(n + 1)]

mod = 10 ** 9 + 7
for i in range(1, n + 1):
    for j in range(4):
        if j == 0:
            dp[i][j] = (dp[i - 1][0] * 10 + dp[i - 1][1] + dp[i - 1][2]) % mod
            if i == 1:
                dp[i][j] = 0
        elif j == 1:
            dp[i][j] = (dp[i - 1][1] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 2:
            dp[i][j] = (dp[i - 1][2] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 3:
            dp[i][j] = (dp[i - 1][3] * 8) % mod
            if i == 1:
                dp[i][j] = 8

print(dp[n][0])


### FIXED CODE ###

# from functools import lru_cache

n = int(input())


# @lru_cache(maxsize=None)
# def dp(num, typ, mod=10 ** 9 + 7):
#     print(num, typ)
#     if num == 1:
#         if typ == 1:  # contain 0 not 9
#             return 1
#         elif typ == 2:  # contain 9 not 0
#             return 1
#         elif typ == 3:  # not contain
#             return 8
#         elif typ == 0:
#             return 0

#     if typ == 0:
#         return (dp(num - 1, 1) + dp(num - 1, 2) + dp(num - 1, 0) * 10) % mod
#     elif typ == 1:  # contain 0 not 9
#         return (dp(num - 1, 1) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 2:  # contain 9 not 0
#         return (dp(num - 1, 2) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 3:  # not contain
#         return (dp(num - 1, 3) * 8) % mod


# print(dp(n, 0))

dp = [[0 for j in range(4)] for i in range(n + 1)]

mod = 10 ** 9 + 7
for i in range(1, n + 1):
    for j in range(4):
        if j == 0:
            dp[i][j] = (dp[i - 1][0] * 10 + dp[i - 1][1] + dp[i - 1][2]) % mod
            if i == 1:
                dp[i][j] = 0
        elif j == 1:
            dp[i][j] = (dp[i - 1][1] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 2:
            dp[i][j] = (dp[i - 1][2] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 3:
            dp[i][j] = (dp[i - 1][3] * 8) % mod
            if i == 1:
                dp[i][j] = 8

print(dp[n][0])
### BUGGY CODE ###

N,M = input().split()
N = int(N)
M = int(M)
price_list = input().split()
 
price_list = list(map(int, price_list))
 
for m in range(M):
  price_list.sort(reverse=True)
  price_list[0] = int(price_list[0] / 2)
print(sum(price_list))

### FIXED CODE ###

import heapq

N,M = input().split()
N = int(N)
M = int(M)
price_list = input().split()
 
heap_list = []
for i in price_list:
  heapq.heappush(heap_list, int(i) * (-1))

for _ in range(M):
  max_num = heapq.heappop(heap_list)
  heapq.heappush(heap_list, int(max_num /2))
  
print(sum(heap_list) * (-1))
### BUGGY CODE ###

import collections
def c():
    n, k = map(int, input().split())
    h = []
    for i in range(n):
        h.append(int(input()))
    h.sort()
    d = collections.deque(maxlen = k)
    mins = []
    while len(d) < k:
        d.append(h.pop())
    while h:
        mins.append(max(d) - min(d))
        d.append(h.pop())
    mins.append(max(d) - min(d))
    print(min(mins))
c()


### FIXED CODE ###

import collections
def c():
    n, k = map(int, input().split())
    h = []
    for i in range(n):
        h.append(int(input()))
    h.sort()
    d = collections.deque(maxlen = k)
    mins = []
    while len(d) < k:
        d.append(h.pop())
    while h:
        mins.append(d[0] - d[k-1])
        d.append(h.pop())
    mins.append(d[0] - d[k-1])
    print(min(mins))
c()
### BUGGY CODE ###

s=input()
S=""
i=0
leng=len(s)
while(i<leng):
    if s[i]=="A":
        S+="A"
        i+=1
    elif i+1<leng and s[i]=="B" and s[i+1]=="C":
        S+="B"
        i+=2
    else:
        S+="C"
        i+=1
T=S[::-1]
l=[0]*len(T)
ans=0
t=len(T)
for i in range(len(T)-1):
    if T[i]=="B":
        l[i+1]=l[i]+1
    elif T[i]=="A":
        l[i+1]=l[i]
        ans+=l[i]
if T[-1]=="A":
    ans+=l[-1]
print(ans)


### FIXED CODE ###

s=input()
S=""
i=0
leng=len(s)
while(i<leng):
    if s[i]=="A":
        S+="A"
        i+=1
    elif i+1<leng and s[i]=="B" and s[i+1]=="C":
        S+="B"
        i+=2
    else:
        S+="C"
        i+=1
T=S[::-1]
l=[0]*len(T)
ans=0
t=len(T)
for i in range(len(T)-1):
    if T[i]=="B":
        l[i+1]=l[i]+1
    elif T[i]=="A":
        l[i+1]=l[i]
        ans+=l[i]
if T[-1]=="A":
    ans+=l[-1]
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        if A[j]<c:
            A[j]=c
    A.sort()
print(sum(A))

### FIXED CODE ###

n,m = map(int,input().split())
A = list(map(int, input().split()))
BC = []
for i in range(m):
    b,c = map(int, input().split())
    BC.append([c,b])
A.sort()
BC=sorted(BC, key=lambda x :x[0])
BC.reverse()
ans = sum(A)
cnt=0
for i in range(m):
    for j in range(cnt,BC[i][1]+cnt):
        if BC[i][0]>A[j]:
            ans+=BC[i][0]-A[j]
            cnt+=1
            if j==n-1:
                print(ans)
                exit()
        else:
            break
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
p = [int(_) for _ in input().split()]

ans = 0
ans = [sum(p[i:i+k]) for i in range(n-k+1)]

print((k+max(ans))/2)


### FIXED CODE ###

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

ans = sum(p[0:k])
tmp = ans
for i in range(n-k):
  tmp = tmp - p[i] + p[i+k]
  ans = max(ans,tmp)

print((k+ans)/2)