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

def resolve():
    import sys
    readline = sys.stdin.readline
    N = int(readline())
    info = [None] * N
    for i in range(N):
        p, l = map(int, input().split())
        info[i] = [p-l, p+l]
    info.sort(key=lambda x: x[0])

    def is_obstacle(i):
        count = 0
        for j in info[i+1:]:
            if info[i][1] > j[0]:
                count += 1
        for j in info[:i]:
            if info[i][0] < j[1]:
                count += 1
        return count

    obs_list = [1] * N
    while sum(obs_list) > 0:
        obs_list = [0] * N
        m = 0
        idx = 0
        for i in range(N):
            obs_list[i] = is_obstacle(i)
            if m < obs_list[i]:
                m = obs_list[i]
                idx = i
        if sum(obs_list) == 0:
            break
        info = info[:idx] + info[idx+1:]
        N -= 1

    print(N)

resolve()

### FIXED CODE ###

def resolve():
    import sys
    from operator import itemgetter
    readline = sys.stdin.readline
    N = int(readline())
    LR = [None] * N
    for i in range(N):
        p, l = map(int, input().split())
        LR[i] = [p-l, p+l]
    LR.sort(key=itemgetter(1))

    pre_r = -(10**18)
    count = 0
    for l, r in LR:
        if pre_r <= l:
            count += 1
            pre_r = r
    print(count)

resolve()
### BUGGY CODE ###

B, W = list(map(int, input().split()))

MOD = 10**9+7
combB1 = 0
combW1 = 0
y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2list = [1]
invmod = {}
for i in range(B+W):
    pow2list += [pow2list[-1]*2 %MOD]
    y_pi = 0 if i < B else 2*y_pi + combB1
    y_qi = 0 if i < W else 2*y_qi + combW1
    xi = pow2list[i+1]
    if xi in invmod:
        invxi = invmod[xi]
    else:
        invxi = pow(xi, MOD-2, MOD)
        invmod[xi] = invxi
    yi = (pow2list[i]-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(int(z))
    if i < B-1:
        combB1 = 0
    elif i == B-1:
        combB1 = 1
    else:
        if i-B+1 in invmod:
            invB = invmod[i-B+1]
        else:
            invB = pow(i-B+1, MOD-2, MOD)
            invmod[i-B+1] = invB
        combB1 = combB1*i*invB % MOD
    if i < W-1:
        combW1 = 0
    elif i == W-1:
        combW1 = 1
    else:
        if i-W+1 in invmod:
            invW = invmod[i-W+1]
        else:
            invW = pow(i-W+1, MOD-2, MOD)
            invmod[i-W+1] = invW
        combW1 = combW1*i*invW % MOD

### FIXED CODE ###

B, W = list(map(int, input().split()))

MOD = 10**9+7

facts = [1,1] #階乗
invs = [1,1] #整数の逆元
invfacts = [1,1] #階乗の逆元
for ind in range(1, B+W):
    i = ind+1
    facts.append(facts[-1]*i % MOD)
    invs.append( -(MOD//i)*invs[MOD%i] % MOD )
    invfacts.append( invfacts[-1]*invs[i] % MOD )

def Comb(n, r, MOD=MOD):
    if n < r:
        return 0
    return facts[n]*invfacts[n-r]*invfacts[r] % MOD

y_pi = 0 #i回目までにBを食べ尽くした確率piの分子
y_qi = 0 #i回目までにWを食べ尽くした確率qiの分子
pow2 = 1
invxi = 1
inv2 = invs[2]
for i in range(B+W):
    #y_pi = 0 if i < B else 2*y_pi + ((facts[i-1]*invfacts[i-B] % MOD)*invfacts[B-1] % MOD)
    y_pi = (2*y_pi + Comb(i-1, B-1))%MOD
    #y_qi = 0 if i < W else 2*y_qi + ((facts[i-1]*invfacts[i-W] % MOD)*invfacts[W-1] % MOD)
    y_qi = (2*y_qi + Comb(i-1, W-1))%MOD
    invxi = invxi * inv2 % MOD
    yi = (pow2-y_pi+y_qi) % MOD
    z = yi*invxi % MOD
    print(z)
    pow2 = pow2*2 %MOD
### BUGGY CODE ###

from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
A = sorted(list(set(A)))
ok = [True] * (10**6+1)

for a in A:
    temp = a+a
    while temp < 10**6+1:
        ok[temp] = False
        temp += a

c = 0
for a in A:
    if C[a] == 1 and ok[a] == True:
        c += 1
print(c)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
A = list(set(A))
ok = [True] * (10**6+1)

for a in A:
    temp = a+a
    while temp < 10**6+1:
        ok[temp] = False
        temp += a

c = 0
for a in A:
    if C[a] == 1 and ok[a] == True:
        c += 1
print(c)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(N // R + 1):
    for g in range(N // G + 1):
        n = R * r + G * g
        if N - n >= 0 and (N - n) % B == 0:
            ans += 1
print(ans)


### FIXED CODE ###

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

def print_ans(s):
    """Print substring of s, odd_th char
    >>> print_ans([1])
    1
    >>> print_ans([1,4])
    1
    >>> print_ans([0,3,4,5])
    3
    >>> print_ans([1,2,3,2,5,6])
    4
    
    """
    b = sorted(s)
    ans = 1
    for i in range(b[0],b[-1]+1):
        ans = max(b.count(i)+b.count(i+1)+b.count(i+2),ans)
    print(ans)

if __name__ == '__main__':
    N = input()
    a = list(map(int,input().split()))
    print_ans(a)



### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
a = list(map(int,input().split()))
cnt = [0]*(10**5)
for i in a:
    cnt[i] += 1
ans_max =0
for i in range(100000-2):
    #ans_max = max(ans_max,sum(cnt[i:i+3]))
        ans_max = max(ans_max,cnt[i]+cnt[i+1]+cnt[i+2])

print(ans_max)
### BUGGY CODE ###

import copy

S = input()
nN = len(S)
nAns = [ 0 for i in range(nN)]
nAnsT = [ 0 for i in range(nN)]
nAnsR = [ 0 for i in range(nN)]

for i in range(nN):
    sTmp = S[i]
    
    if sTmp =='R':
      nAnsR[i] = 1
    elif sTmp =='L':
      nAnsR[i] = -1

for i in range(nN):
  nTmp = i
  nR = 0
  nFlag = 0
  for j in range(100000):
    nR = nAnsR[nTmp]
    nTmp += nR
    
    nChk = j & 1
    if nChk == 1 and nFlag != nR:
      nAns[nTmp] += 1
      nAnsT[i]= nTmp - i
      break
    nFlag = nR
      
      
print(*nAns)



### FIXED CODE ###

import sys
import copy

S = input()
nN = len(S)
nAns = [ 0 for i in range(nN)]
nAnsT = [ 0 for i in range(nN)]
nAnsR = [ 0 for i in range(nN)]

nCnt = S.count('RL')
nRLp = [ 0 for i in range(nCnt)]

nTmpP = 0
for i in range(nCnt):
  nTmp = S.find('RL',nTmpP)
  nRLp[i] = nTmp
  nTmpP = nTmp + 1

nCntE = S.count('LR')
nLRp = [ 0 for i in range(nCntE)]
nTmpP = 0
for i in range(nCntE):
  nTmp = S.find('LR',nTmpP)
  nLRp[i] = nTmp
  nTmpP = nTmp + 1
  
# print(nRLp)
# print(nLRp)

nTmpS = 0
for i in range(nCnt):
  nTmpR = nRLp[i]
  nTmpL = nTmpR + 1
  
  if i == nCnt - 1:
    nTmpE = nN - 1
  else:
    nTmpE = nLRp[i]
    
  nSize = nTmpE-nTmpS+1
  nB1 = nSize // 2
  nB2 = nSize // 2
  nChk = nSize % 2
  if nChk == 1:
    nB1 += 1
  
  nChk = nTmpR - nTmpS
  nChk %= 2
  if nChk == 0:
    nAns[nTmpR]=nB1
    nAns[nTmpL]=nB2
  else:
    nAns[nTmpR]=nB2
    nAns[nTmpL]=nB1
  
  nTmpS = nTmpE + 1

print(*nAns)
### BUGGY CODE ###

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

l=[]
for i in range(n-k+1):
    total=1
    for j in range(0+i,k+i):
        total*=a[j]
    l.append(total)

for i in range(n-k):
    if l[i]<l[i+1]:
        print('Yes')
    else:
        print('No')   

### FIXED CODE ###

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

for i in range(n-k):
    if a[i]<a[i+k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def gcd_2(a,b):
    if a<=b:
        x_min=a
        x_max=b
    else:
        x_min=b
        x_max=a
        
    while True:
#         print(x_min,x_max)
        if x_max % x_min ==0:
            return x_min
        
        x_temp = x_max % x_min
        
        x_max = x_min
        x_min = x_temp
        
def gcd(a,b,c):
    d=gcd_2(a,b)
    ans=gcd_2(d,c)
    return ans
  
N=int(input())
sum_gcd=0
for a_1 in range(1,N+1):
    for a_2 in range(1,N+1):
        for a_3 in range(1,N+1):
            sum_gcd+=gcd(a_1,a_2,a_3)
print(sum_gcd)

### FIXED CODE ###

def gcd_2(a,b):
    if a<=b:
        x_min=a
        x_max=b
    else:
        x_min=b
        x_max=a
        
    while True:
#         print(x_min,x_max)
        if x_max % x_min ==0:
            return x_min
        
        x_temp = x_max % x_min
        
        x_max = x_min
        x_min = x_temp
        
def gcd(a,b,c):
    d=gcd_2(a,b)
    ans=gcd_2(d,c)
    return ans
  
N=int(input())
sum_gcd=0
for a_1 in range(1,N+1):
    for a_2 in range(1,N+1):
        for a_3 in range(1,N+1):
            sum_gcd+=gcd(a_1,a_2,a_3)
print(sum_gcd)
### BUGGY CODE ###

n, m = map(int, input().split())
A = [int(i) for i in input().split()]
 
L = []
for i in range(m):
    b,c = map(int, input().split())
    L.append((b,c))
    
A = sorted(A)
 
from bisect import bisect_left
import numpy as np
A = np.array(A)
for l in L:
    tmp0 = l[0]
    tmp1 = l[1]
    A_len = bisect_left(A, tmp1)
    if A_len >= tmp0:
        A = np.insert(A, A_len, [tmp1]*tmp0)[tmp0:]
    else:
        A[0:A_len] = tmp1
        
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

D = {}
for i in range(M):
    b,c = map(int, input().split())
    if c in D:
        D[c] += b
    else:
        D[c] = b
        
for a in A:
    if a in D:
        D[a] += 1
    else:
        D[a] = 1
        
D_sort = sorted(D.items(), reverse=True)
check = 0
ans = 0
for d in D_sort:
    check += d[1]
    if check <= N:
        ans += d[0] * d[1]
    else:
        ans += d[0] * (d[1] - (check - N))
        break
print(ans)
### BUGGY CODE ###

def main():
    import heapq
    hpop=heapq.heappop
    hpush=heapq.heappush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    h2 = []
    h2a=h2.append
    heapq.heapify(h)
    for i in range(n):
        hpush(h, [-b[i], i])
    cnt = 0
    while h:
        i, j = hpop(h)
        i=-i
        temp = i-a[j]
        temp2=b[j-1]+b[(j+1)%n]
        sho=temp//temp2
        if  sho==0:
            h2a([i, j])
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, [-b[j], j])
    h2.sort(key=lambda x: x[1])
    for i in range(n):
        if a[i] != h2[i][0]:
            print(-1)
            return 0
    print(cnt)


main()

### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
ans = 0
for i in range(N):
    ans += sum(A[i])
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                if B[i][k] == B[i][j]+B[j][k]:
                    ans -= B[i][k]
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])

if A == B:
    print(ans//2)
else:
    print(-1)


### FIXED CODE ###

import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
table = [[True]*N for i in range(N)]
ans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                if B[i][k] == B[i][j]+B[j][k]:
                    table[i][k] = False
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])


if A == B:
    for i in range(N):
        for j in range(N):
            if table[i][j]:
                ans += B[i][j]
    print(ans//2)
else:
    print(-1)
### BUGGY CODE ###

n, m = map(int,input().split())
lst = [0 for i in range(n)]
for i in range(m):
    l, r = map(int,input().split())
    for j in range(l - 1, r):
        lst[j] = lst[j] + 1
ans = 0
for i in range(n):
    if(lst[i] == m):
        ans = ans + 1
print(ans)


### FIXED CODE ###

n, m = map(int,input().split())
for i in range(m):
    if (i == 0):
        l, r = map(int,input().split())
    else:
        l2, r2 = map(int,input().split())
        l = max(l, l2)
        r = min(r, r2)
if (l > r):
    print(0)
else:
    print(r - l + 1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
L1 = list()
L2 = list()
ret = 0
for i in range(len(A)):
    num1 = i + 1 - A[i]
    num2 = i + 1 + A[i]
    L1.append(num1)
    L2.append(num2)    
    if num1 in L2:
        ret += 1
    if num2 in L1:
        ret += 1
ret = 0
retlist = dict()
for l in L1:
    if l not in retlist.keys():
        num = len([l2 for l2 in L2 if l2 == l]) 
        ret += num
    else:
        ret += retlist[l]
print(ret)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L1 = list()
D2 = dict()
ret = 0
for i in range(len(A)):
    num1 = i + 1 - A[i]
    num2 = i + 1 + A[i]
    L1.append(num1)
    if num2 not in D2:
        D2[num2] = 1
    else:
        D2[num2] += 1
ret = 0
retlist = dict()
for l in L1:
    if l in D2.keys():
        ret += D2[l]
print(ret)
### BUGGY CODE ###

import sys,bisect
input=sys.stdin.readline

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**9)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**9,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(100001):
        dp[i][j]=max(dp[i//2][j],(dp[i//2][j-w]+v)*(j>=w))

temp=[[0,0] for i in range(2**9)]

def solve(v,L):
    t=[]
    while v>=2**9:
        t.append(vw[v])
        v//=2
    n=len(t)
    for i in range(1,2**n):
        m=i.bit_length()
        temp[i][0]=temp[i-2**(m-1)][0]+t[m-1][0]
        temp[i][1]=temp[i-2**(m-1)][1]+t[m-1][1]
    ans=0
    for i in range(2**n):
        if L>=temp[i][1]:
            ans=max(ans,temp[i][0]+dp[v][L-temp[i][1]])
    return ans

def main():
    for i in range(int(input())):
        v,L=map(int,input().split())
        print(solve(v,L))

if __name__=="__main__":
    main()

### FIXED CODE ###

import sys,random,time,bisect
input=sys.stdin.buffer.readline

start=time.time()
N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])
### BUGGY CODE ###

num, capacity = list(map(int, input().split()))
actions = [[0 for i in range(capacity + 1)]]
for i in range(num):
    actions.append(list(map(int, input().split())))

dp = [[0 for i in range(capacity + 1)] for j in range(num + 1)]
for i in range(1, num + 1):
    for w in range(capacity + 1):
        if w - actions[i][0] >= 0:
            dp[i][w] = max( dp[i-1][w - actions[i][0]] + actions[i][1],  dp[i-1][w] )
        else:
            dp[i][w] = dp[i-1][w]
print(max( dp[num] ))

### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

import numpy as np

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

coef = np.minimum(np.arange(n, 1, -1), np.arange(1, n))
dp = np.zeros(n, dtype=np.int64)
dp[0] = 1
for c in coef:
    w = np.zeros(n, dtype=np.int64)
    w[::c] = 1
    dp = np.convolve(dp, w, mode='full')[:n] % m

print((dp * np.arange(n, 0, -1) % m).sum() % m)


### FIXED CODE ###

import numpy as np

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

coef = np.minimum(np.arange(n, 1, -1), np.arange(1, n))
dp = np.zeros(n, dtype=np.int64)
dp[0] = 1
for c in coef:
    ndp = np.zeros(n, dtype=np.int64)
    for i in range(0, n, c):
        ndp[i:] += dp[:n - i]
    dp = ndp % m

print((dp * np.arange(n, 0, -1) % m).sum() % m)
### BUGGY CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que, frag = deque(), set()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j)), frag.add((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if (i, j) in frag:  # 処理済みか否か
                continue
            if 0 <= i < h and 0 <= j < w:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j)), frag.add((i, j))
    return dist


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(max(max(ans) for ans in bfs(a)))


### FIXED CODE ###

from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    dist = [[-1] * w for _ in range(h)]  # 前処理
    que = deque()
    for i, Si in enumerate(S):
        for j, Sij in enumerate(Si):
            if Sij == '#':
                dist[i][j] = 0
                que.append((i, j))

    while len(que) > 0:
        (x, y) = que.popleft()
        near = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
        for i, j in near:  # 移動先の候補
            if 0 <= i < h and 0 <= j < w and dist[i][j] < 0:
                dist[i][j] = dist[x][y] + 1
                que.append((i, j))
    return dist[x][y]


h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(bfs(a))
### BUGGY CODE ###

N = int(input())

ans = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        if i % j == 0:
            ans += i

print(ans)

### FIXED CODE ###

import math
N = int(input())

ans = 0
for i in range(1,N+1):
    K = int(N/i)
    anstemp = i * K * (K+1) // 2
    ans += anstemp
print(ans)
### BUGGY CODE ###

# abc143_d.py
N = int(input())
L = list(map(int,input().split()))
cnt =0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i]<L[j]+L[k] and L[j]<L[i]+L[k] and L[k]<L[j]+L[i]:
                # print(i,j,k)
                cnt+=1
print(cnt)


### FIXED CODE ###

# abc143_d.py
def can_make(i, j, k):
    if L[i] < L[j] + L[k] and L[j] < L[k] + L[i] and L[k] < L[j] + L[i]:
        return True
    return False


def find(i, j, L):
    left = j
    right = N
    mid = (right + left)//2
    flg = False
    while right - left > 1:
        mid = (right + left)//2
        # print("left,mid,right", left, mid, right)
        if can_make(i, j, mid):
            # print("can make")
            left = mid
            flg = True
        else:
            right = mid
    # print("j,mid", j, mid)
    # print(flg)
    if flg:
        return left-j
    else:
        return 0


N = int(input())
L = list(map(int, input().split()))
cnt = 0
L = sorted(L, reverse=True)
for i in range(N):
    for j in range(i+1, N):
        # print(L)
        # print("i,j", i, j, L[i], L[j])
        cnt += find(i, j, L)
print(cnt)
### BUGGY CODE ###

from collections import deque

S = input()
Q = int(input())

S = deque(S)

for _ in range(Q):
    query = input()
    if query[0] == '1':
        S.reverse()
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            S.appendleft(C)
        elif F == '2':
            S.append(C)
            
result = ''.join(S)
print(result)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

S = deque(S)
reverse = False

for _ in range(Q):
    query = input()
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            if reverse:
                S.append(C)
            else:
                S.appendleft(C)
        elif F == '2':
            if reverse:
                S.appendleft(C)
            else:
                S.append(C)
            
result = ''.join(S)
if reverse:
    result = result[::-1]
print(result)
### BUGGY CODE ###

import numpy as np  # noqa

m = 998244353
N, K = map(int, input().split())

jumps = []
for i in range(K):
    l, r = map(int, input().split())
    jumps.append([l, r])

jumps = np.array(jumps)

dp = np.zeros(N + 1)
dp[1] = 1
for i in range(2, N + 1):
    for j in jumps:
        mn = max(0, i - j[1])
        mx = max(mn, i - j[0])
        dp[i] = (dp[i] + np.sum(dp[mn:mx + 1])) % m


print(int(dp[N]))


### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353


@njit((i8, i8[:]), cache=True)
def main(N, LR):
    L, R = LR[::2], LR[1::2]
    K = len(L)
    F = np.zeros(N + 10, np.int64)
    F[0] = 1
    for n in range(1, N + 10):
        F[n] += F[n - 1]
        for k in range(K):
            l, r = L[k], R[k] + 1
            if n - l >= 0:
                F[n] += F[n - l]
            if n - r >= 0:
                F[n] -= F[n - r]
        F[n] %= MOD
    ans = F[N - 1] - F[N - 2]
    return ans % MOD


N, K = map(int, readline().split())
LR = np.array(read().split(), np.int64)

print(main(N, LR))
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
set_a = set(a)
ans = 0

for ai in set_a:
    ans += a.count(ai) - ai if a.count(ai) >= ai else a.count(ai)

print(ans)

### FIXED CODE ###

from collections import Counter

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

cnt = Counter(a)
ans = 0

for ai, num in cnt.items():
  if num >= ai:
  	ans += num - ai  
  else:
    ans += num

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

N,K = list(map(lambda x:int(x),input().split()))
P = list(map(lambda x:int(x),input().split()))
s = [0]*(len(P)-K+1)
for i in range(len(P)-K+1):
	s[i] = sum(P[i:i+K])
ans  = max(s)/2. + K/2.
print(ans)

### FIXED CODE ###

N,K = list(map(lambda x:int(x),input().split()))
P = list(map(lambda x:int(x),input().split()))
s = [0]*(len(P)-K+1)
for i in range(len(P)-K+1):
    if i==0:
	    s[i] = sum(P[i:i+K])
    else:
        s[i] = s[i-1]-P[i-1]+P[i+K-1]
    
ans  = max(s)/2. + K/2.
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
A = sorted(A,reverse=True)
temp = 0
for i in range(M):
    A[0] =A[0]//2
    if len(A)>=2:
        if A[0] < A[1]:
            A = sorted(A,reverse=True)
print(sum(A))


### FIXED CODE ###

#from operator import itemgetter
#from collections import Counter
import heapq
#N = int(input())
N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
#A = [int(input()) for i in range(N)]

heapq.heapify(A)

for i in range(M):
    max = heapq.heappop(A)
    heapq.heappush(A, max*(-1)//2*(-1))
print(-sum(A))