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

import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n = onem()

a = l()

b = l()

t = []

for i in range(n):
    if b[i] != a[i]:
        hq.heappush(t,[-b[i],i])
hq.heapify(t)
co = 0
while t:
    k = hq.heappop(t)
    k = [-k[0],k[1]]
    if k[1] == 0:
        ppp = (k[0]-a[k[1]]) // (b[-1] + b[1])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[-1] + b[1]) + a[k[1]]
    elif k[1] == n-1:
        ppp = (k[0]-a[k[1]]) // (b[-2] + b[0])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[-2] + b[0]) + a[k[1]]
    else:
        ppp = (k[0]-a[k[1]]) // (b[k[1]+1] + b[k[1]-1])
        if ppp == 0:
            print(-1)
            exit()
        co += ppp
        k[0] = (k[0]-a[k[1]]) % (b[k[1]+1] + b[k[1]-1]) + a[k[1]]
    b[k[1]] = k[0]
    if b[k[1]] != a[k[1]] and len(t) != 0:
        hq.heappush(t,[-b[k[1]],k[1]])

print(co)

### FIXED CODE ###

import heapq as hq
mod = 10**9+7
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def onon():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,(-b[i],i))
    co = 0
    while t:
        k = hq.heappop(t)
        k = (-k[0],k[1])
        q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
        co += q
        if q == 0:
            return -1
        w = a[k[1]] + w
        b[k[1]] = w
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,(-w,k[1]))
    return co
print(onon())
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    N = int(input())

    for n in range(1, N + 1):
        res = 0
        for x in range(1, int(pow(n, 0.5)) + 1):
            for y in range(1, int(pow(n, 0.5)) + 1):
                t = n - pow(x, 2) - pow(y, 2) - x * y
                if t >= 1:
                    for z in range(1, int(pow(t, 0.5)) + 1):
                        if pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x == n:
                            res += 1
        print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())

    res = [0] * (n + 10)
    for x in range(1, int(pow(n, 0.5)) + 1):
        for y in range(1, int(pow(n, 0.5)) + 1):
            for z in range(1, int(pow(n, 0.5)) + 1):
                t = pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x
                if t <= n:
                    res[t] += 1

    for x in range(1, n + 1):
        print(res[x])


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

n = int(input())
s = []
p = []
ans = 0
for i in range(n):
    s.append(input())
    if s[i] in p:
        pass
    else:
        p.append(s[i])
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = []
p = set()
ans = 0
for i in range(n):
    s.append(input())
    if s[i] in p:
        pass
    else:
        p.add(s[i])
        ans += 1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
from itertools import accumulate

n = int(input())
arr = list(map(int, input().split()))
sa = sum(arr)
lim = sa // 2
dp = [0] * (lim + 1)
dp[0] = 1
mx = 0

for a in arr:
    # print(a, dp)
    for i in range(min(mx, lim - a), -1, -1):
        if dp[i]:
            dp[i + a] += dp[i]
    # print(a, dp)
    mx = max(mx + a, lim)

adp = list(accumulate(dp))
k = 2 ** (n - 1)

# print(adp)
# print(k)

print(sa - bisect_left(adp, k))


### FIXED CODE ###

n, arr, dp = int(input()), list(map(int, input().split())), 1
for a in arr:
    dp |= dp << a
ofs = (sum(arr) + 1) // 2
dp >>= ofs
print((dp & -dp).bit_length() + ofs - 1)
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())
 
p = sorted(list(map(int,input().split())))[-X:]
q = sorted(list(map(int,input().split())))[-Y:]
r = sorted(list(map(int,input().split())), reverse=True)
 
for i in r:
    p_min = p[0]
    q_min = q[0]
 
    if p_min > i and q_min > i:
        break
 
    p_min_diff = i - p_min
    q_min_diff = i - q_min
 
    if p_min_diff >= q_min_diff and p_min_diff > 0:
        p.remove(p_min)
        p.append(i)
    elif q_min_diff > p_min_diff and q_min_diff > 0:
        q.remove(q_min)
        q.append(i)
 
print(sum(p) + sum(q))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
 
p = sorted(list(map(int,input().split())), reverse=True)[:X]
q = sorted(list(map(int,input().split())), reverse=True)[:Y]
r = sorted(list(map(int,input().split())), reverse=True)
 
colored_p = []
colored_q = []
 
for i in r:
    p_min = p[len(p) - 1] if len(p) > 0 else colored_p[len(colored_p) - 1]
    q_min = q[len(q) - 1] if len(q) > 0 else colored_q[len(colored_q) - 1]
 
    if p_min > i and q_min > i:
        break
 
    p_min_diff = i - p_min
    q_min_diff = i - q_min
 
    if p_min_diff >= q_min_diff and p_min_diff > 0:
        if len(p) > 0:
            p.pop()
        colored_p.append(i)
    elif q_min_diff >= p_min_diff and q_min_diff > 0:
        if len(q) > 0:
            q.pop()
        colored_q.append(i)
 
print(sum(p) + sum(q) + sum(colored_p) + sum(colored_q))
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
mn=min(h)
cnt=0
if(mn!=1):
    print("-1")
    exit()
r=len(h)
i=-1
while(True):
    i=i+1
    if i==r:
        break
    if(h[i]!=i+1):
        cnt=cnt+1
        del h[i]
        r=len(h)
        i=i-1
print(cnt)


### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
mn=min(h)
cnt=0
if(mn!=1):
    print("-1")
    exit()
i=1
for k in h:
    if(k==i):
        i=i+1
    else:
        cnt=cnt+1
print(cnt)
### BUGGY CODE ###

k, s = list(map(int, input().split()))
ans = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if (i + j + l) == s:
                ans += 1

print(ans)

### FIXED CODE ###

k, s = list(map(int, input().split()))
ans = 0
for i in range(k+1):
    for j in range(k+1):
        z = s - i -j
        if 0 <= z and z <= k:
            ans += 1

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

N = int(input())
A = list(map(int, input().split()))
A.sort()
T = [1] * N
for i in range(N):
  if T[i] == 1:
    for j in range(N):
      if i != j:
        if A[i] == A[j]:
          T[i] = 0
        if T[j] == 1 and A[j] % A[i] == 0:
          T[j] = 0
print(sum(T))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
M = max(A)
num = [0] * (M)
T = [0] * (M)
for a in A:
  num[a-1] += 1
  T[a-1] = 1
for i in range(M):
  if num[i] != 0 and T[i] == 1:
    n = 2 * (i + 1)
    while n <= M:
      T[n-1] = 0
      n += (i + 1)
ans = 0
for i in range(M):
  if T[i] == 1 and num[i] == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
P_i = list(map(int, input().split()))

total = 0


for i in range(N):
    count = 0
    for j in range(i):
        if P_i[i] <= P_i[j]:
            count += 1

    if count == i:
        total += 1

print(total)


### FIXED CODE ###

N = int(input())
P_i = list(map(int, input().split()))

total = 0

equi = P_i[0]

for i in range(N):
    if equi >= P_i[i]:
        total += 1
        equi = P_i[i]

print(total)
### BUGGY CODE ###

s = input()
k = int(input())
a = []
for i in range(len(s)+1):
    for j in range(len(s)-i+1):
        if s[j:j+i]:
            a.append(s[j:j+i])
            
a = list(set(a))
a.sort()
print(a[k-1])

### FIXED CODE ###

S = input()
K = int(input())
a = list(set(S))
a.sort()

k = []
l = 0
while l < len(a):
    for i in range(len(S)):
        if S[i] == a[l]:
            for j in range(1,6):
                if i+j <= len(S):
                    k.append(S[i:i+j])
                else:
                    break
    l += 1

k = list(set(k))
k.sort()
print(k[K-1])
### BUGGY CODE ###

from collections import defaultdict
import heapq

N = int(input())
INF = float('inf')
edges = [list(map(int, input().split())) for _ in range(N-1)]
nodes = defaultdict(list)

for e in edges:
    nodes[e[0] - 1].append((e[2], e[1] - 1))
    nodes[e[1] - 1].append((e[2], e[0] - 1))


Q, K = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(Q)]

def dijkstra(x, y):
    que = []
    heapq.heapify(que)
    dist = [INF for _ in range(N)]
    dist[x] = 0
    heapq.heappush(que, (0, x))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for e in nodes[v]:
            if dist[e[1]] > dist[v] + e[0]:
                dist[e[1]] = dist[v] + e[0]
                heapq.heappush(que, (dist[e[1]], e[1]))

    return dist[y]


for q in queries:
    x, y = q[0] - 1, q[1] - 1
    print(dijkstra(x, K - 1) + dijkstra(K - 1, y))



### FIXED CODE ###

from collections import defaultdict
import heapq

N = int(input())
INF = float('inf')
edges = [list(map(int, input().split())) for _ in range(N-1)]
nodes = defaultdict(list)

for e in edges:
    nodes[e[0] - 1].append((e[2], e[1] - 1))
    nodes[e[1] - 1].append((e[2], e[0] - 1))


Q, K = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(Q)]

def dijkstra(x):
    que = []
    heapq.heapify(que)
    dist = [INF for _ in range(N)]
    dist[x] = 0
    heapq.heappush(que, (0, x))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for e in nodes[v]:
            if dist[e[1]] > dist[v] + e[0]:
                dist[e[1]] = dist[v] + e[0]
                heapq.heappush(que, (dist[e[1]], e[1]))

    return dist

distk = dijkstra(K - 1)

for q in queries:
    x, y = q[0] - 1, q[1] - 1
    print(distk[x] + distk[y])
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
# a.sort()
check = [True for _ in range(10**6 + 5)]
dic = {}
if len(a) == 1:
    print(1)
    exit()

for i in a:
    if i in dic:
        dic[i] += 1
        continue
    dic[i] = 0
    now = 2 * i
    while (10**6 + 3 > now):
        check[now] = False
        now += i

ans = 0
for i in a:
    if check[i] and dic[i] == 0:
        ans += 1
print(ans)


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
# a.sort()
check = [True for _ in range(10**6 + 5)]
dic = {}
if len(a) == 1:
    print(1)
    exit()

for i in a:
    if i in dic:
        dic[i] += 1
        continue
    dic[i] = 0
    now = 2 * i
    while (10**6 + 3 > now):
        check[now] = False
        now += i

ans = 0
for i in a:
    if check[i] and dic[i] == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
for i in range(M):
  b, c = map(int, input().split())
  for j in range(b):
    a = heapq.heappop(A)
    if a < c:
      heapq.heappush(A, c)
    else:
      heapq.heappush(A, a)
      break
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
B = []
for i in range(M):
  b, c = map(int, input().split())
  B.append([c, b])
B.sort(reverse=True)
i = 0
f = 0
for j in range(M):
  while B[j][1]:
    if A[i] < B[j][0]:
      A[i] = B[j][0]
      B[j][1] -= 1
      i += 1
      if i >= N:
        f = 1
        break
    else:
      f = 1
      break
  if f == 1:
    break
print(sum(A))
### BUGGY CODE ###

def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]


n = int(input())
s = input()
ans = set()

for i in range(0,1000):
  b = 1
  num = str(i)
  if i < 10:
    num = "00"+num
  elif i <100:
    num = "0" + num
  for j in range(n):
    if b == 0:
      break
    if s[j] == num[0]:
      for k in range(j+1,n):
        if b == 0:
          break
        if s[k] == num[1]:
          for l in range(k+1,n):
            if b == 0:
              break
            if s[l] == num[2]:
              ans.add(i)
              b = 0
print(len(ans))
                        


### FIXED CODE ###

n = int(input())
s = input()
ans = 0

for i in range(0,1000):
    num = str(i)
    if i < 10:
        num = "00"+num
    elif i <100:
        num = "0" + num
    f = 0
    for j in range(n):
        if s[j] == num[f]:
            f += 1
        if f == 3:
            break
    if f==3:
        ans +=1
print(ans)
### BUGGY CODE ###

import itertools
s = input()
k = int(input())
alphabet = sorted(list(set(list(s))))

list_sub = []
num = 1
while num <= k:
  temp = list(itertools.product(alphabet, repeat=num))
  temp = ["".join(com) for com in temp if "".join(com) in s]
  list_sub.extend(temp)
  num += 1
list_sub.sort()
print(list_sub[k-1])

### FIXED CODE ###

s = input()
k = int(input())

list_sub = []
for i in range(len(s)):
  temp = [s[i:i+j] for j in range(1, min(len(s)-i+1, k+1))]
  list_sub += temp

list_sub = list(set(list_sub))
list_sub.sort()

print(list_sub[k-1])
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(K):
    if len(set(A)) == 1 and A[0] == N:
        break
    work = [0] * (N + 1)
    for i in range(N):
        a = A[i]
        idx0 = max(0, i - a)
        idx1 = min(N, i + a + 1)
        work[idx0] += 1
        work[idx1] -= 1
    now = 0
    for i in range(N):
        now += work[i]
        A[i] = now
print(*A)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(K):
    if len(set(A)) == 1 and A[0] == N:
        break
    work = [0] * (N + 1)
    for i in range(N):
        a = A[i]
        idx0 = max(0, i - a)
        idx1 = min(N, i + a + 1)
        work[idx0] += 1
        work[idx1] -= 1
    now = 0
    for i in range(N):
        now += work[i]
        A[i] = now
print(*A)
### BUGGY CODE ###

N = int(input())
K = int(input())

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for i3 in range(1,10):
                for j1 in range(len(str(N))-2):
                    for j2 in range(len(str(N))-2-j1):
                        for j3 in range(len(str(N))-2-j1-j2):
                            if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                                res += 1

print(res)


### FIXED CODE ###

N = int(input())
K = int(input())

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for j1 in range(len(str(N))-2-1):
        for j2 in range(len(str(N))-2-1-j1):
            for j3 in range(len(str(N))-2-1-j1-j2):
                res += 1
    res = res * (9**3)
    
    for j1 in range(len(str(N))-2):
        for j2 in range(len(str(N))-2-j1):
            j3 = len(str(N))-2-j1-j2-1
            for i1 in range(1,10):
                for i2 in range(1,10):
                    for i3 in range(9,0,-1):
                        if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                            res += i3
                            break

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

N=int(input())
A=[int(input()) for _ in range(N)]
B=[]
for i in range(N):
    B=A.copy()
    B.pop(i)
    print(max(B))

### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
B=sorted(A)[:N-1]
m=max(A)
n=A.index(max(A))
for i in range(N):
    if  i!=n:
        print(m)
    else:
        print(max(B))
### BUGGY CODE ###

n = int(input())
dat = list(map(int, input().split()))
buf = [0] * (n+1)
buf.append(0)
cur = 0
for i in range(0, n):
    cur += dat[i]
    buf[i+1] = cur
 
 
res = 0
for i in range(0, n+1):
    for j in range(i + 1, n+1):
        if buf[i] == buf[j]:
            res += 1
print(res)

### FIXED CODE ###

# k = 1 - nまでの k の和
def sigma1(n):
    return n * (n + 1) // 2

n = int(input())
dat = list(map(int, input().split()))
buf = [0] * (n+1)
cur = 0
import collections
pos = collections.defaultdict(list)

for i in range(0, n):
    cur += dat[i]
    pos[cur].append(i)
    buf[i+1] = cur

buf.sort()
#print(buf)
import collections
res = 0
c = collections.Counter(buf)
for k in c.keys():
    cnt = c[k]
    if cnt < 2:
        pass
    else:
        res += sigma1(cnt - 1)
print(res)
### BUGGY CODE ###

import bisect
a, b, q = map(int, input().split())
s, t = [0]*(a+2), [0]*(b+2)
for i in range(a):
    s[i+1] = int(input())
for i in range(b):
    t[i+1] = int(input())

s[0] = -float("inf")
s[-1] = float("inf")
t[0] = -float("inf")
t[-1] = float("inf")
#print(s)
#print(t)
for _ in range(q):
    start = int(input())
    x = bisect.bisect_right(s, start)
    y = bisect.bisect_right(t, start)
    ans = float("inf")
    for i in [s[x], s[x-1]]:
        for j in [t[y], t[y-1]]:
            res = min(abs(i-start) + abs(j-i), abs(j-start) + abs(i-j))
            ans = min(ans, res)
    print(ans)

### FIXED CODE ###

import bisect
a, b, q = map(int, input().split())
inf = 10**18
s = [-inf] + [int(input()) for _ in range(a)] + [inf]
t = [-inf] + [int(input()) for _ in range(b)] + [inf]
#print(s)
#print(t)
for _ in range(q):
    start = int(input())
    x = bisect.bisect_right(s, start)
    y = bisect.bisect_right(t, start)
    ans = inf
    for i in [s[x], s[x-1]]:
        for j in [t[y], t[y-1]]:
            res = min(abs(i-start) + abs(j-i), abs(j-start) + abs(i-j))
            ans = min(ans, res)
    print(ans)
### BUGGY CODE ###

S = input()
count = 0

for i in range(len(S)):
  for j in range(i+1, len(S)):
    if int(S[i:j+1]) % 2019 == 0:
      count += 1

print(count)

### FIXED CODE ###

from collections import defaultdict

S = list(input())
S = [int(i) for i in S]
D = defaultdict(int)
mod = 2019

N = len(S)
Mlis = [0]*N
Mlis[-1] = S[-1] % mod

for i in range(N-2, -1, -1):
  Mlis[i] = (Mlis[i+1] + pow(10, N-1-i, mod) * S[i]) % mod

for i in Mlis:
  D[i] += 1

ans = D[0] + sum([i*(i-1)//2 for i in D.values()])

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

import sys
sys.setrecursionlimit(200000)


s = input()
num = len(s)
ans = 0

def count(pos, befor, co):
  global ans
  if pos >= num:
    if ans < co:
      ans = co
    return True
  
  for p in range(1, 3):
    if ans > co + len(s[pos+p:]) + 1:
      break
    if s[pos:pos+p] != befor:
      a = count(pos + p, s[pos:pos+p], co+1)
      
        

  return True

ans = 0

a = count(0, "", 0)
print(ans)


### FIXED CODE ###

s = input()
num = len(s)
ans = 0
pos = 0
 
while True:
  c = s[pos]
  count = 0
  for i in range(num - pos):
    if s[pos + i] == c:
      count += 1
    else:
      ans += (count//3)*2  
      if i < num:
        if count % 3 == 1:
          ans += 1
        elif count % 3 == 2:
          ans += 2
          pos += 1
          pos += count
          count = 0
          
      break
  pos += count
  
  if pos >= num:
    ans += (count // 3) * 2 
    if count % 3 != 0:
      ans += 1
 
    break
 
 
print(ans)
### BUGGY CODE ###

import bisect
import array

n, m = map(int, input().split())
a = map(int, input().split())
a = array.array("L", sorted(list(a)))
for _ in range(m):  # O(m*n)
    max_num = a.pop()  # O(1)
    index = bisect.insort(a, max_num // 2)  # O(log n)
print(sum(a))

### FIXED CODE ###

class heap():
    def __init__(self, maxcom=True):
        if maxcom:
            self.compare = lambda x, y: x > y
        else:
            self.compare = lambda x, y: x < y

    def heappush(self, x, heap):
        heap.append(x)
        length = len(heap)
        pointer = length
        while True:
            if pointer == 1:
                break
            if self.compare(heap[pointer - 1], heap[(pointer >> 1) - 1]):
                heap[pointer - 1], heap[(pointer >> 1) - 1] = heap[(pointer >> 1) - 1], heap[pointer - 1]
                pointer = pointer >> 1
            else:
                break

    def heapreplace(self, function, heap):
        heap[0] = function(heap[0])
        pointer = 1
        length = len(heap)
        while True:
            if (pointer << 1) > length:
                break
            elif (pointer << 1) + 1 > length :
                if self.compare(heap[(pointer << 1) - 1], heap[pointer - 1]):
                    heap[(pointer << 1) - 1], heap[pointer - 1] = heap[pointer - 1], heap[(pointer << 1) - 1]
                else:
                    break
            else:
                if self.compare(heap[(pointer << 1) - 1], heap[pointer << 1]):
                    next_pointer = pointer << 1
                else:
                    next_pointer = (pointer << 1) + 1
                if self.compare(heap[next_pointer - 1], heap[pointer - 1]):
                    heap[next_pointer - 1], heap[pointer - 1] = heap[pointer - 1], heap[next_pointer - 1]
                    pointer=next_pointer
                else:
                    break


n, m = map(int, input().split())
a = map(int, input().split())
heapq = []
heapc=heap(True)
for i in a:
    heapc.heappush(i,heapq)
for _ in range(m):
    heapc.heapreplace(lambda x:x>>1,heapq)
print(sum(heapq))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d *= 10

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d = (d * 10) % 2019

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)