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

n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-1,-1,-1):
    if j+v<len(dp):
      dp[j+v]=min(dp[j+v],dp[j]+w)
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
print(ans)

### FIXED CODE ###

n,W=map(int,input().split())
mv=1
s=[None]*n
for i in range(n):
  s[i]=list(map(int,input().split()))
  mv+=s[i][1]
  
INF=10**9+5
dp=[INF]*mv
dp[0]=0
for i in range(len(s)):
  w=s[i][0]
  v=s[i][1]
  for j in range(len(dp)-v-1,-1,-1):
    if dp[j]+w<dp[j+v]:
      dp[j+v]=dp[j]+w
      
ans=0
for i in range(len(dp)):
  if dp[i]<=W:
    ans=i
    
print(ans)
### BUGGY CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N,K=map(int,input().split())
k=min(K,N-1)
x=0
A=[0]*(k+1)
B=[0]*(k+1)
for i in range(k+1):
 B[i]=cmb(N-1,i)%(10**9+7)
 A[i]=cmb(N,i)%(10**9+7)
for i in range(k+1):
 x+=(A[i]*B[i])%(10**9+7)
print(x%(10**9+7))


### FIXED CODE ###

mod=10**9+7
comb1=1
comb2=1
N,K=map(int,input().split())
k=min(K,N-1)
x=0
for i in range(k):
 comb1=(comb1*(N-i)*pow(i+1,mod-2,mod))%(mod)
 comb2=(comb2*(N-1-i)*pow(i+1,mod-2,mod))%(mod)
 x+=(comb1*comb2)%(mod)
print((x+1)%(mod))
### BUGGY CODE ###

N,K,C=map(int,input().split())
S=input()
L=[]
R=[]
n=0
rc=0
lc=0
while True:
  if lc==K:
    break
  if S[n]=="o":
    L+=[n+1]
    n+=C+1
    lc+=1
  else:
    n+=1
n=N-1
while True:
  if rc==K:
    break
  if S[n]=="o":
    R=[n+1]+R
    n-=C+1
    rc+=1
  else:
    n-=1
for i in range(K):
  if R[i]==L[i]:
    print(R[i])

### FIXED CODE ###

N,K,C=map(int,input().split())
S=input()
L=[0 for i in range(K)]
R=[0 for i in range(K)]
n=0
rc=0
lc=0
while True:
  if lc==K:
    break
  if S[n]=="o":
    L[lc]=n+1
    n+=C+1
    lc+=1
  else:
    n+=1
n=N-1
while True:
  if rc==K:
    break
  if S[n]=="o":
    R[K-1-rc]=n+1
    n-=C+1
    rc+=1
  else:
    n-=1
for i in range(K):
  if R[i]==L[i]:
    print(R[i])
### BUGGY CODE ###

def solve():  # 073C - Write and Erase
    N = int(input())
    joisino_list = []

    for _ in range(N):
        a = int(input())
        if a not in joisino_list:
            joisino_list.append(a)
        else:
            joisino_list.remove(a)

    print(len(joisino_list))
    

solve()

### FIXED CODE ###


def solve():  # 073C - Write and Erase
    N = int(input())
    joisino_list = {}
    cnt = 0

    for _ in range(N):
        a = int(input())

        if a in joisino_list:
            joisino_list[a] += 1
        else:
            joisino_list[a] = 1

    for i in joisino_list.values():
        if i % 2:
            cnt += 1

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

import sys
input = sys.stdin.readline

N = int(input())

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

total = 0
for i,height_a in enumerate(heights):
    if height_a <= (N-i-2):
        for j in range(i+height_a+1,N):
            if abs(i-j) == height_a + heights[j]:
                total += 1

print(total)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())

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


cnt_height_plus_ind = {}
cnt_height_minus_ind = {}
cnt_ind_minus_height = {}
cnt_minus_height_minus_ind = {}

for ind in range(N):
    height = heights[ind]

    if ind - height not in cnt_ind_minus_height:
        cnt_ind_minus_height[ind - height] = 0
    cnt_ind_minus_height[ind - height] += 1

    if ind + height not in cnt_height_plus_ind:
        cnt_height_plus_ind[ind + height] = 0
    cnt_height_plus_ind[ind + height] += 1

    if height - ind not in cnt_height_minus_ind:
        cnt_height_minus_ind[height - ind] = 0
    cnt_height_minus_ind[height - ind] += 1

    if - ind - height not in cnt_minus_height_minus_ind:
        cnt_minus_height_minus_ind[-ind-height] = 0
    cnt_minus_height_minus_ind[-ind-height] += 1
    

ans = 0
for val in cnt_height_minus_ind:
    if val in cnt_minus_height_minus_ind:
        ans += cnt_height_minus_ind[val] * cnt_minus_height_minus_ind[val]

for val in cnt_height_plus_ind:
    if val in cnt_ind_minus_height:
        ans += cnt_height_plus_ind[val] * cnt_ind_minus_height[val]

print(ans//2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math

#区間加算，1点取得
class SegTree2:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 更新[l,r)にxを加算
    def update(self,l,r,x):
        if r<=l:
            return self.ide_ele
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
         
        while r-l>1:
            if l&1 == 0:
                self.seg[l] = self.segfunc(self.seg[l],x)       
            if r&1 == 1:
                self.seg[r] = self.segfunc(self.seg[r],x)
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            self.seg[r] = self.segfunc(self.seg[r],x)
        else:
            self.seg[l] = self.segfunc(self.seg[l],x)
            self.seg[r] = self.segfunc(self.seg[r],x)
  
    # k番目の要素に加算されている合計値を計算
    def query(self,k):    
        k += self.num-1 #葉のノードのインデックス
        ret = self.seg[k]
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            ret = self.segfunc(ret, self.seg[k])
        return ret
    
            
def segfunc(x,y):
    return x|y



N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()

#%%
ans = 0
damage = 0
seg = SegTree2(N,[0]*N,lambda x,y:x+y,0)

right = 1
for i in range(N):
    d = XH[i][1] - seg.query(i)
    if d<=0:
        continue
    else:
        c = math.ceil(d/A)
        ans += c
        
        while right<N and XH[right][0]<=XH[i][0]+2*D :
            right += 1
        
        seg.update(i,right,c*A)

print(ans)
            
        
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from queue import Queue
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort()
#%%
bound = [0]*N
idx = 0
right = 0
while idx<N:
    while right < N and (XH[right][0]-XH[idx][0])<=2*D:
        right += 1
    bound[idx] = right  
    idx += 1
def kiriage(n,m):
    return (n+(m-1))//m

heru = [0]*(N+1)
ans = 0
damage = 0
for i in range(N):
    damage -= heru[i]
    
    if XH[i][1]<=damage:
        continue
    cnt = kiriage(XH[i][1]-damage,A)
    ans += cnt
    damage += cnt*A
    heru[bound[i]] += cnt*A
print(ans)
### BUGGY CODE ###

from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)
N, M = map(int, input().split())
B = set(map(lambda x: int(x)//2, input().split()))
power = 1
for b in B:
    power = lcm(power, b)

mn = min(B)

mn2 = mn
p2 = power // mn2

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn2 // p2
ans2 = M // mn2 // (p2*2)
print(ans1-ans2)


### FIXED CODE ###

from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)
N, M = map(int, input().split())
B = set(map(lambda x: int(x)//2, input().split()))
power = 1
for b in B:
    power = lcm(power, b)

mn = min(B)
p2 = power // mn

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn // p2
ans2 = M // mn // (p2 * 2)
print(ans1-ans2)
### BUGGY CODE ###

import sys

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

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0] * (N + 1)

dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,N):
    dp[i] = min(dp[j] + abs(h[i]-h[j]) for j in range(max(0,i-K),i))
print(dp[N-1])

### FIXED CODE ###

import sys

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

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0] * (N + 1)

    dp[0] = 0
    dp[1] = abs(h[1]-h[0])
    for i in range(2,N):
        dp[i] = min(dp[j] + abs(h[i]-h[j]) for j in range(max(0,i-K),i))
    print(dp[N-1])

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

s = str(input())

cnt=0

for i in range(len(s)//2):
    if '10' in s:
        cnt+=2 * s.count('10')
        s=s.replace('10', '') 
    elif '01' in s:
        cnt+=2 * s.count('01')
        s=s.replace('01', '') 
print(cnt)

### FIXED CODE ###

#120 C
S =input()
print(min(S.count('0'),S.count('1'))*2)
### BUGGY CODE ###

import bisect

N,M = [int(x) for x in input().split()]

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):
    
    count = 0
    while True:
        l.sort()
        value = l[-1][0]+1
        l.sort(key=lambda v:v[1])
        l2 = [v2 for (_,v2) in l]
        index = bisect.bisect_left(l2,value)
        l = l[:index]

        count += 1
        if len(l)<1:
            break
    return count



result = do(l)
print(result)

### FIXED CODE ###

import bisect

N,M = [int(x) for x in input().split()]

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):

    count = 1

    l.sort()
    right = l[0][1]


    for i in range(len(l)):
        if l[i][0] >= right:
            right = l[i][1]
            count+=1
            continue
        if l[i][1] < right:
            right = l[i][1]
    return count

testl = [[x,x+1] for x in range(1)]

result = do(l)
print(result)
### BUGGY CODE ###

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

for i in range(n):
  c = 0
  for j in b:
    if j%(n-i)^1:
      c+=1
  if a[n-1-i] ^ c%2:
    b.append(n-i)
print(len(b))
if len(b)>0:
  print(*b)

### FIXED CODE ###

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

for i in range(n-1):
  if a[n-1-i]&1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)
### BUGGY CODE ###

N = int(input())
x = list([int(i) for i in input().split()])
cnt = 0
mn_lst = []
for i in x:
    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i <<= 1
    mn_lst.append(cnt)
print(min(mn_lst))

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
mn_lst = []
for i in x:
    cnt = 0
    while i % 2 == 0:
        cnt += 1
        i >>= 1
    mn_lst.append(cnt)
    
print(min(mn_lst))
### BUGGY CODE ###

import sys
import collections
def solve():
    sys.setrecursionlimit(100000)
    mod = 998244353

    N = int(input())
    D = list(map(int, input().split()))
    cnter = collections.Counter(D)
    cnter = sorted(cnter.items())

    ans = 1
    if cnter[0][0] != 0 or cnter[0][1] != 1 : 
        ans = 0
    elif cnter[1][0] != 1:
        ans = 0
    else:
        for i in range(2, len(cnter)):
            if cnter[i][0] != i:
                ans = 0
                break

            else:
                ans = ans * modpow(cnter[i-1][1], cnter[i][1], mod) % mod
    
    print(ans)


def modpow(a, b, mod):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % mod
            a = a * a % mod
            b = b >> 1
    return res

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import collections
def solve():
    sys.setrecursionlimit(100000)
    mod = 998244353

    N = int(input())
    D = list(map(int, input().split()))
    ans = 1
    if D[0] != 0:
        ans = 0
        print(ans)
        exit(0)
    
    cnter = collections.Counter(D)
    cnter = sorted(cnter.items())

    if cnter[0][0] != 0 or cnter[0][1] != 1 : 
        ans = 0
    elif len(cnter) == 1:
        ans = 1
    elif cnter[1][0] != 1:
        ans = 0
    else:
        for i in range(2, len(cnter)):
            if cnter[i][0] != i:
                ans = 0
                break

            else:
                ans = ans * modpow(cnter[i-1][1], cnter[i][1], mod) % mod
    
    print(ans)


def modpow(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

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

# B - Easy Linear Programming

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

# check
result_score = 0
while K > 0:
        for score, i in [(1, A), (0, B), (-1, C)]:
                if K <= 0:
                        break
                while K > 0 and i > 0:
                        result_score += score
                        i -= 1
                        K -= 1

print(result_score)

### FIXED CODE ###

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

# check
result_score = 0
for score, i in [(1, A), (0, B), (-1, C)]:
        if K <= 0:
               continue

        if K >= i:
            result_score += score * i
            K -= i
        else:
            result_score += score * K
            K = 0

print(result_score)
### BUGGY CODE ###

human_num = int(input())

nyu = list(map(int, input().split(" ")))

for i in range(human_num):
    print(nyu.count(i + 1))

### FIXED CODE ###

human_num = int(input())
jousi_num = [0 for i in range(human_num)]

nyu = list(map(int, input().split(" ")))

for k in nyu:
    jousi_num[k - 1] += 1

for ri in jousi_num:
    print(ri)
### BUGGY CODE ###

import math
from functools import reduce

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

K = int(input())
#K = 2
sum = 0

for a in range (1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      sum += gcd(a, b, c)

print(sum)


### FIXED CODE ###

from math import gcd

K = int(input())
#K = 200
sum = 0

for a in range (1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      sum += gcd(gcd(a, b), c)

print(sum)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
col = [-1]*n
dist = [float('inf')]*n
dist[0] = 0
visited = [0]*n
for _ in range(n-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]

def dfs(u):
  if sum(visited) == n:
    return 
  for v, w in graph[u]:
    if dist[v] == float('inf'):
      dist[v] = dist[u] + w 
      dfs(v)

  return 

dfs(0)
for i in range(n):
  if dist[i] % 2 == 0:
    print(1)
  else:
    print(0)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
    adlist[v-1] += [[u-1, w%2]]
  return adlist 

def dfs(v, c):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] != 0:
      continue
    if color[next_v] == 0 and w % 2 != 0:
      dfs(next_v, -c)
    elif color[next_v] == 0 and w % 2 == 0:
      dfs(next_v, c)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  dfs(0, 1)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


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

import numpy as np
from itertools import product

n = int(input())
s = np.array([int(input()) for _ in range(n)])

ans = 0
for i in product((0, 1), repeat=n):
    x = sum(np.array(i) * s)
    if x % 10 != 0:
        ans = max(ans, x)
print(ans)

### FIXED CODE ###

s = [int(input()) for _ in range(int(input()))]

if sum(s) % 10 != 0:
    print(sum(s))
else:
    s.sort()
    for i, x in enumerate(s):
        if x % 10 != 0:
            print(sum(s) - x)
            break
    else:
        print(0)
### BUGGY CODE ###

a, b = map(int, input().split())
c = [int(input())for _ in range(b)]
d = [0] * (a+1)
d[0] = 1 if 0 not in c else 0
d[1] = 1 if 1 not in c else 0
for i in range(2, a+1):
    if i not in c:
        d[i] = (d[i-1] + d[i-2]) % 1000000007
    else:
        d[i] = 0
print(d[len(d)-1])


### FIXED CODE ###

a, b = map(int, input().split())
d = [True] * (a+1)
for i in range(b):
    d[int(input())] = False
e = [0] * (a+1)
for i in range(0, a+1):
    if i < 2:
        if d[i]:
            e[i] = 1
        else:
            e[i] = 0
    elif not d[i] and not d[i-1]:
        print(0)
        exit()
    elif d[i]:
        e[i] = (e[i-2] + e[i-1]) % 1000000007
print(e[len(e)-1])
### BUGGY CODE ###

import heapq

def dijkstra(ad_lst, n, s, t):
    costs = [float('inf') for i in range(n+1)]
    costs[s] = 0
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            if costs[u] + c < costs[v]:
                alt = costs[u] + c
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

n,m,s,t, = map(int, input().split())

route_y = {i: [] for i in range(n+1)}
route_s = {i: [] for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u].append([v,a])
    route_y[v].append([u,a])
    route_s[u].append([v,b])
    route_s[v].append([u,b])

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
cost_ys = [cost_y[i]+cost_s[i] for i in range(n+1)]

inf = float('inf')
result = [inf for _ in range(n+1)]
min_cost = result[-1]
for i in range(n, 0, -1):
    if min_cost > cost_ys[i]:
        min_cost = cost_ys[i]
    result[i] = min_cost
yen = 10**15
for i in range(1, n+1):
    print(yen - result[i])


### FIXED CODE ###

import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c

    return costs

n,m,s,t, = map(int, input().split())

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]
### BUGGY CODE ###

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

inmap = [input() for _ in range(H)]

q = queue.Queue(10)
q.put((0,0,1))

cood = [(1,0),(-1,0),(0,1),(0,-1)]

res = 0

visited = set([(0,0)])

while not q.empty():
    x,y,cnt=q.get(False)
    # print(x,y)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            # print(visited)
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

black = 0
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            black += 1

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)


### FIXED CODE ###

import queue
H,W=map(int, input().split())
inmap = [input() for _ in range(H)]

q = queue.Queue(2500)
q.put((0,0,1))
cood = [(1,0),(-1,0),(0,1),(0,-1)]
res = 0

visited = set((0,0))

while not q.empty():
    x,y,cnt=q.get(False)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

black = 0
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            black += 1

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)
### BUGGY CODE ###

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

A.sort(reverse=True)

l=1
r=200000+1

while l+1<r:
    mid=(l+r)//2


    cnt=0
    C=0
    S=0

    for la in A:
        for ra in A:
            if la+ra>mid:
                S+=(la+ra)
                cnt+=1
                C+=1
            else:break
    if cnt<M:
       
        r=mid
    else:
        l=mid

AN=r
ans=S+(M-C)*AN
print(ans)




### FIXED CODE ###

from bisect import bisect_left

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

A.sort()

l=1
r=200000+1

def chk(x):
    c=0
    for la in A:
        y=bisect_left(A,x-la)
        c+=N-y
    if c>=M:
        return True
    else:
        return False



while l+1<r:
    mid=(l+r)//2
    if chk(mid):
        l=mid
    else:
        r=mid

AN=l

S=[0]*(N+1)

for i in range(N):
    S[i+1]=S[i]+A[i]

ans1=0
c=0
for la in A:
    ll = -1
    rr = N
    while ll + 1 < rr:
        mi = (ll + rr) // 2
        if A[mi] > AN - la:
            rr = mi
        else:
            ll = mi
    c+=N-rr
    ans1=ans1+la*(N-rr)+S[N]-S[rr]

ans=ans1+(M-c)*AN
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
L = list(map(int, input().split()))

C = collections.Counter(L)
for i in range(N):
    del_target = L[i]
#     print("deltarget:{}".format(del_target))
    ans = 0
    for i in C.items():
        if i[0]== del_target:
            n = i[1]-1
#             print(int((n*(n-1)/2)))
            ans += int((n*(n-1)/2))
        else:
#             print(int((i[1]*(i[1]-1))/2))
            ans += int((i[1]*(i[1]-1))/2)
    print(ans)

### FIXED CODE ###

import collections
N = int(input())
L = list(map(int, input().split()))

C = collections.Counter(L)
ans = 0
for i in C.items():
    ans += int((i[1]*(i[1]-1))/2)
        
for i in range(N):
    del_target = L[i]
    print(ans - (C[del_target]-1))
### BUGGY CODE ###

import numpy as np
import sys
f = sys.stdin
n = int(f.readline())
h = list(map(int, f.readline().split()))
h = np.array(h)
dp = np.zeros(n, int)
dp[1] = abs(h[1] - h[0])
for i in range(n - 1):
    np.minimum(
        dp[1:-1] + np.abs(h[2:] - h[1:-1]), dp[:-2] + np.abs(h[2:] - h[:-2]), out=dp[2:]
    )
print(dp[-1])


### FIXED CODE ###

import sys
f = sys.stdin
n = int(f.readline())
h = list(map(int, f.readline().split()))
dp = [0]*n
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[-1])
### BUGGY CODE ###

#coding:utf-8
import math
import itertools
from functools import reduce

def gcd(*num):
    return reduce(math.gcd, num)


if __name__ == "__main__":

    k = int(input())
    ans = 0

    num = list(range(1, k+1))
    comb = list(itertools.product(num, repeat=3))


    for i in range(len(comb)):
        ans += gcd(comb[i][0], comb[i][1], comb[i][2])

    print(ans)


### FIXED CODE ###

#coding:utf-8
from math import gcd

def main():
    k = int(input())
    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(gcd(a, b), c)

    print(ans)

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

# coding: utf-8

n, m = map(int, input().split())
s = list(map(int, input().split()))

for i in range(m):
  index = s.index(max(s))
  s[index] = s[index] // 2

sum = sum(s)
print(sum)

### FIXED CODE ###

# coding: utf-8
import heapq

n, m = map(int, input().split())
s = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(s)

for i in range(m):
  maxi = heapq.heappop(s)
  heapq.heappush(s, -(-maxi // 2))

print(-sum(s))