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

n,a=map(int,input().split())
x=list(map(int,input().split()))

for i in range(n):
    x[i]=x[i]-a
    
n2=n//8
n3=n-n2*8

y1=[]
y2=[]
y3=[]
y4=[]
y5=[]
y6=[]
y7=[]
y8=[]
for i in range(n2):
    y1.append(x[i])
    y2.append(x[i+n2])
    y3.append(x[i+n2*2])
    y4.append(x[i+n2*3])
    y5.append(x[i+n2*4])
    y6.append(x[i+n2*5])
    y7.append(x[i+n2*6])
    y8.append(x[i+n2*7])
y9=[]
for i in range(n3):
    y9.append(x[i+n2*8])
    
# itertools 使用 bit全探索
import itertools

def xdic(n2,xx):
    xsum=dict()
    for i in itertools.product([0,1], repeat=n2):
        isum=0
        for ii in range(n2):
            if i[ii]==0:
                isum=isum+xx[ii]
        if isum in xsum:
            xsum[isum]=xsum[isum]+1
        else:
            xsum[isum]=1
    return xsum

xsum1=xdic(n2,y1)
xsum2=xdic(n2,y2)
xsum3=xdic(n2,y3)
xsum4=xdic(n2,y4)
xsum5=xdic(n2,y5)
xsum6=xdic(n2,y6)
xsum7=xdic(n2,y7)
xsum8=xdic(n2,y8)
xsum9=xdic(n3,y9)
    
icnt=0
for xs1 in xsum1.items():
    for xs2 in xsum2.items():
        for xs3 in xsum3.items():
            for xs4 in xsum4.items():
                for xs5 in xsum5.items():
                    for xs6 in xsum6.items():
                        for xs7 in xsum7.items():
                            for xs8 in xsum8.items():
                                for xs9 in xsum9.items():
                                    if xs1[0]+xs2[0]+xs3[0]+xs4[0]+xs5[0]+xs6[0]+xs7[0]+xs8[0]+xs9[0]==0:
                                        icnt=icnt+xs1[1]*xs2[1]*xs3[1]*xs4[1]*xs5[1]*xs6[1]*xs7[1]*xs8[1]*xs9[1]

print(icnt-1)                        


### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))

for i in range(n):
    x[i]=x[i]-a
    
nx=n*n
dp=[[0]*(2*nx+1) for i in range(n+1)]

#print(dp)

dp[0][nx]=1

for j in range(1,n+1):
    jj=j-1
    for t in range(2*nx+1):
        if t-x[jj]<0 or 2*nx<t-x[jj]:
            dp[j][t]=dp[j-1][t]
        elif 0<t-x[jj] and  t-x[jj]<2*nx:
            dp[j][t]=dp[j-1][t]+dp[j-1][t-x[jj]]
        else:
            dp[j][t]=0

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

import itertools
N = int(input())
S = list(input())
S = tuple(S)
X = list(itertools.combinations(S, 3))
print(len(set(X)))


### FIXED CODE ###

N = int(input())
S = input()
count = 0
for i in range(1000):
    t = str(i).zfill(3)
    a = S.find(t[0])
    b = S.find(t[1], a+1)
    c = S.find(t[2], b+1)
    if a != -1 and b != -1 and c != -1:
        count += 1
print(count)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())

cnt=0
for R in range(n//r+1):
 for G in range(n//g+1):
  num=n-R*r-G*g
  if num>=0 and num%b==0:
   cnt+=1
print(cnt)

### FIXED CODE ###

r,g,b,n=map(int,input().split())

cnt=0
for R in range(n//r+1):
 for G in range((n-r*R)//g+1):
  num=n-R*r-G*g
  if num>=0 and num%b==0:
   cnt+=1
print(cnt)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

    for i in range(1, k + 1):
        baig[i] = (k // i) ** n % MOD

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD

    print(int(ans))


if __name__ == '__main__':
    main()







### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    """"ここに今までのコード"""
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

    for i in range(1, k + 1):
        baig[i] = pow(k // i , n , MOD)

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD
    print(int(ans))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
d = dict(zip(range(0,n), x))
x.sort()
for i in range(0, n):
    if d[i] in x[0:n//2] :
        print(x[n//2])
    else :
        print(x[n//2-1])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
d = dict(zip(range(0,n), x))
x.sort()
for i in range(0, n):
    if d[i] <= x[n//2-1] :
        print(x[n//2])
    else :
        print(x[n//2-1])
### BUGGY CODE ###

from sys import stdin
def read():
    return stdin.readline().strip()

dict={}
output=[]

iteration=int(read())

max_val=-1

for _ in range(iteration):
    item=read()
    
    if dict.get(item) is None:
        dict[item]=0 
    dict[item]+=1 
    max_val = max(dict[item],max_val)

while(bool(dict)):
    max_key=max(dict,key=dict.get)
    if(max_val!=dict[max_key]):
        break
    output.append(max_key)
    
    del dict[max_key]
output.sort()
print('\n'.join(output))


### FIXED CODE ###


from sys import stdin
def read():
    return stdin.readline().strip()

dict={}
output=[]

iteration=int(read())

max_val=-1

for _ in range(iteration):
    item=read()
    
    if dict.get(item) is None:
        dict[item]=0 
    dict[item]+=1 
    max_val = max(dict[item],max_val)
#max_val=max(dict.values())
for k,v in dict.items():
    
    if(max_val==v):
        output.append(k)
    
    
output.sort()
print('\n'.join(output))
### BUGGY CODE ###

from collections import deque
import sys


def bfs(x1, y1, d):
    q = deque()
    q.append((d, x1, y1))

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)


### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
s_max = 0
max_i=0
ret = 0
for i in range(n-k+1):
  p_s=sum(p[i:i+k])
  if s_max<p_s:
    s_max=p_s
    max_i=i
for i in range(k):
  p_i = p[max_i+i]
  ret+=(1+p_i)*p_i/(2*p_i)
  
print(ret)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
max_i=0
ret = 0
p_s=sum(p[0:k])
s_max=p_s
for i in range(n-k):
  p_s=p_s-p[i]+p[i+k]
  if s_max<p_s:
    s_max=p_s

print(s_max/2+k/2)
### BUGGY CODE ###

from fractions import gcd

def init(a):
    for i in range(n):
        seg[num+i-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = st_func(seg[2*i+1], seg[2*i+2])

def query(l, r):
    if r <= l:
        return ide_ele
    
    l += num - 1
    r += num - 2
    res = ide_ele

    while r - l > 1:
        if l % 2 == 0:
            res = st_func(res, seg[l])
        if r % 2 == 1:
            res = st_func(res, seg[r])
            r -= 1
        l = l // 2
        r = (r - 1) // 2
    
    if l == r:
        res = st_func(res, seg[l])
    else:
        res = st_func(res, st_func(seg[l], seg[r]))
    
    return res

def update(i, v):
    i += num - 1
    seg[i] = v
    while i > 0:
        i = (i - 1) // 2
        seg[i] = st_func(seg[i*2+1], seg[i*2+2])

def st_func(x, y):
    return gcd(x, y)


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

num = 2 ** (n - 1).bit_length()
ide_ele = 0
seg = [ide_ele] * (2*num-1)

init(a)

res = 0
for i in range(n):
    res = max(res, gcd(query(0, i), query(i+1, n)))

print(res)

### FIXED CODE ###

from fractions import gcd

# 配列aで初期化
def init(a):
    for i in range(n):
        seg[i+num-1] = a[i]    
    for i in range(num-2, -1, -1) :
        seg[i] = gcd(seg[2*i+1], seg[2*i+2]) 


# a[k]の値をxに更新
def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k - 1) // 2
        seg[k] = gcd(seg[k*2+1], seg[k*2+2])


# [p, q)についてsegfuncを適用したものを返す
def query(p,q):
    if q <= p:
        return ide_ele
    
    p += num - 1
    q += num - 2
    res = ide_ele

    while q - p > 1:
        if p & 1 == 0:
            res = gcd(res, seg[p])
        if q & 1 == 1:
            res = gcd(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    if p == q:
        res = gcd(res, seg[p])
    else:
        res = gcd(gcd(res, seg[p]), seg[q])
    
    return res


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

ide_ele = 0
num = 2 ** (len(bin(n - 1)) - 2)
seg = [ide_ele] * 2 * num
init(a)

res = 0
for i in range(n):
    res = max(res, gcd(query(0, i), query(i+1, n)))

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

import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r,MOD):
    ans = ma.factorial(n) * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= comb(val + n-1, n-1, MOD)
    ans %= MOD
print(ans)



### FIXED CODE ###

import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= spm.comb(val + n-1, n-1, exact=1)
    ans %= MOD
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
  if a[i] in dic:
    dic[a[i]]+=1
  else:
    dic[a[i]]=1
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  if b in dic:
    if c in dic:
      dic[c]+=dic[b]
      del dic[b]
    else:
      dic[c]=dic[b]
      del dic[b]
  ans=0
  for key,value in dic.items():
    ans+=key*value
  print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
  if a[i] in dic:
    dic[a[i]]+=1
  else:
    dic[a[i]]=1
q=int(input())
ans=0
for key,value in dic.items():
  ans+=key*value
for i in range(q):
  b,c=map(int,input().split())
  if b in dic:
    if c in dic:
      dic[c]+=dic[b]
      ans+=dic[b]*(c-b)
      del dic[b]
    else:
      dic[c]=dic[b]
      ans+=dic[b]*(c-b)
      del dic[b]
  print(ans)
### BUGGY CODE ###

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

nums = [0]*(n+1)
nums[0]  =1
if 1 not in a: nums[1] = 1

for i in range(2, n+1):
  nums[i] = nums[i-1] + nums[i-2]
  if i in a: nums[i] = 0
print(nums[n]%1000000007)

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
inf = 1000000007

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0
  
for i in range(2, n+1):
  if i in a:
    continue
  dp[i] = dp[i - 1] + dp[i - 2]
  dp[i] %= inf
  
print(dp[n])
### BUGGY CODE ###

N = int(input())

s = [None] * N
l, c, r = 0, N//2, N-1

while True:
    for i in (l, c, r):
        if s[i] == None:
            print(i, flush=True)
            s[i] = input()
        if s[i] == 'Vacant':
            exit()
    if s[l] != s[c]:
        r = c
        c = (l + r) // 2
    else:
        l = c
        c = (l + r) // 2


### FIXED CODE ###

N = int(input())

s = [None] * N
l, c, r = 0, N//2, N-1

while True:
    for i in (l, c, r):
        if s[i] == None:
            print(i, flush=True)
            s[i] = input()
            if s[i] == 'Vacant':
                exit()
    if ((c-l)%2==0 and s[l]!=s[c]) or ((c-l)%2 and s[l]==s[c]):
        r = c
        c = (l + r) // 2
    else:
        l = c
        c = (l + r) // 2
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
for i in range(1000):
  flag=0
  pin=str(i).zfill(3)
  for j in range(n-2):
    if s[j]==pin[0]:
      flag=1
      break
  if flag==1:
    for k in range(j+1,n-1):
      if s[k]==pin[1]:
        flag=2
        break
  if flag==2:
    for l in range(k+1,n):
      if s[l]==pin[2]:
        cnt+=1
        break
print(cnt)

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
for i in range(1000):
  flag=0
  pin=str(i).zfill(3)
  if s.find(pin[0])==-1:
    continue
  s1=s[s.find(pin[0])+1:]
  if s1.find(pin[1])==-1:
    continue
  s2=s1[s1.find(pin[1])+1:]
  if s2.find(pin[2])==-1:
    continue
  cnt+=1
print(cnt)
### BUGGY CODE ###

import sys
N=int(input())

if 100<=N<=105:
    print(1)
    sys.exit()

min_=N//105
max_= N//100 + 1
#print(min_,max_)
for m in range(min_,max_):
    X = N - 100*m
    for i in range(0,X+1):
        for j in range(0,(X-i)//2 +1):
            for k in range(0,(X-i-2*j)//3 +1):
                for l in range(0,(X-i-2*j-3*k)//4 +1):
                    #print(m,i,j,k,l,temp)
                    temp = (X-i-2*j-3*k-4*l)
                    if (temp % 5 == 0) and (m-i-j-k-l-temp//5>=0):
                        a=m-i-j-k-l-temp//5
                        t=temp // 5
                        print(1)
                        #print(N,m,a,i,j,k,l,t,100*a+101*i+102*j+103*k+104*l+105*t)
                        sys.exit()
else:
    print(0)

### FIXED CODE ###

import sys
N=int(input())

if 100<=N<=105:
    print(1)
    sys.exit()

min_=N//105
max_= N//100 + 1
#print(min_,max_)
count=0
for m in range(min_,max_):
    X = N - 100*m
    for i in range(0,X+1):
        for j in range(0,(X-i)//2 +1):
            for k in range(0,(X-i-2*j)//3 +1):
                for l in range(0,(X-i-2*j-3*k)//4 +1):
                    count+=1
                    if count >= 5*10**7:
                        print(1)
                        sys.exit()
                    temp = (X-i-2*j-3*k-4*l)
                    if (temp % 5 == 0) and (m-i-j-k-l-temp//5>=0):
                        a=m-i-j-k-l-temp//5
                        t=temp // 5
                        print(1)
                        #print(N,m,a,i,j,k,l,t,100*a+101*i+102*j+103*k+104*l+105*t)
                        sys.exit()
else:
    print(0)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j in range(-2, 3):
            for k in range(-2, 3):
                new_y, new_x = y + j, x + k
                if 0 <= new_y < H and 0 <= new_x < W:
                    if maze[new_y][new_x] == "." and j**2 + k**2 == 1 and visited[y][x] < visited[new_y][new_x]:
                        visited[new_y][new_x] = visited[y][x]
                        queue.appendleft([new_y, new_x])
                    elif maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


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

n = int(input())
if n <= 1:
    print(0)
else:
    prime = True
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            prime = False
            break
    if prime:
        print(1)
    else:
        num = 2
        initial = 1
        track = 1
        count = 0
        while num <= n:
            if n % num == 0:
                track -= 1
                if track == 0:
                    count += 1
                    initial += 1
                    track = initial
                n = n // num
            else:
                num += 1
                initial = 1
                track = 1
        print(count)


### FIXED CODE ###

import math
from collections import defaultdict

def isPrime(num):
    prime = True
    save = num
    save2 = None
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            prime = False
            save = i
            save2 = num // i
            break
    return prime, save, save2

store = defaultdict(int)

def solve(num):
    check, num1, num2 = isPrime(num)
    if check == True:
        global store
        store[num1] += 1
    if check == False:
        solve(num1)
        solve(num2)

n = int(input())
if n <= 1:
    print(0)
else:
    count = 0
    solve(n)
    for key, v in store.items():
        for i in range(1, v+1):
            if store[key] >= i:
                store[key] -= i
                count += 1
            else:
                break
    print(count)
### BUGGY CODE ###

import numpy as np
n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
for i in range(m):
    k = np.argmax(a)
    if a[k] == 0:
        break
    a[k] = int(a[k]/2)
ans = sum(a)
print(ans)


### FIXED CODE ###

#import numpy as np
import sys
import heapq #優先度付きキュー
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
a = [int(i)*(-1) for i in input().split()] #各要素*(-1)
heapq.heapify(a)
for i in range(m):
    """
    k = np.argmax(a)
    if a[k] == 0:
        break
    a[k] = int(a[k]/2)
    """
    tmp = heapq.heappop(a) #最小値を抜き取る(最大値*(-1)を抜き取る）
    heapq.heappush(a, (-1)*(-tmp//2)) #要素を追加
ans = -sum(a)
print(ans)
### BUGGY CODE ###

N,W = map(int,input().split())
wv = []
for i in range(N):
    wv.append(list(map(int,input().split())))

dp = [[ 0 for i in range(W+1)] for j in range(N+2)]

for i in range(N):
    for w in range(1,W+1):
        if w - wv[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w] , dp[i][w - wv[i][0]] + wv[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])


### FIXED CODE ###

N,W = map(int,input().split())
wv = []
for i in range(N):
    wv.append(list(map(int,input().split())))

dp = [[ 0 for i in range(W+1)] for j in range(N+2)]

for i in range(N):
    for w in range(1,W+1):
        if w - wv[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w] , dp[i][w - wv[i][0]] + wv[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

n = int(input())
words_list = list()
cnt = []
d = {}
for i in range(n) :
    words_list.append(input())
candidates = sorted(list(set(words_list)))
for word in candidates :
    cnt.append(words_list.count(word))
mx = max(cnt)
for i in range(len(cnt)) :
    if cnt[i] == mx :
        print(candidates[i])


### FIXED CODE ###

n = int(input())
d = {}
for _ in range(n) :
    s = input()
    if s in d :
        d[s] += 1
    else :
        d[s] = 1

mx = max(d.values())
for s in sorted(k for k in d if d[k] == mx) :
    print(s)
### BUGGY CODE ###

N, *S = open(0).read().split()
S = [sorted(s) for s in S]

cnt = 0
for i, s in enumerate(S):
    for j, t in enumerate(S[i+1:]):
        if s == t:
            cnt += 1
print(cnt)

### FIXED CODE ###

N, *S = open(0).read().split()
S = [str(sorted(s)) for s in S]
D = {}
ans = 0
for s in S:
    if s in D:
        ans += D[s]
        D[s] += 1
    else:
        D[s] = 1
print(ans)