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

#!/usr/bin/env python3
import sys
import queue

def solve(H: int, W: int, A: "List[str]"):
    Q = queue.Queue()
    marked = [[False for w in range(W)] for h in range(H)]
    qlen = 0
    for h, line in enumerate(A):
        for w, c in enumerate(line):
            if c == '#':
                Q.put((h, w))
                qlen += 1
                marked[h][w] = True
    
    count = 0
    while not Q.empty():
        flag = False
        for _ in range(qlen):
            h, w = Q.get()
            qlen -= 1
            for hh, ww in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
                if hh < 0 or hh >= H or ww < 0 or ww >= W:
                    continue
                if marked[hh][ww]:
                    continue
                flag = True
                Q.put((hh, ww))
                qlen += 1
                marked[hh][ww] = True
        if flag:
            count += 1
    print(count)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

inf = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    dist = [[inf] * W for h in range(H)]
    for h in range(1, H):
        for w in range(1, W):
            if A[h][w] == '#':
                dist[h][w] = 0
            else:
                dist[h][w] = min(dist[h-1][w], dist[h][w-1]) + 1
    
    dmax = 0
    for h in range(H-1, -1, -1):
        for w in range(W-1, -1, -1):
            if A[h][w] == '#':
                dist[h][w] = 0
            elif h+1 <= H-1 and w+1 <= W-1:
                dist[h][w] = min(dist[h][w], min(dist[h+1][w], dist[h][w+1]) + 1)
            elif w+1 == W and h+1 <= H-1:
                dist[h][w] = min(dist[h][w], dist[h+1][w] + 1)
            elif h+1 == H and w+1 <= W-1:
                dist[h][w] = min(dist[h][w], dist[h][w+1] + 1)
            dmax = max(dist[h][w], dmax)
    print(dmax) 
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

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

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    S = sr()
    N = len(S)
    a = defaultdict(int)
    a[0] += 1
    t = 0
    for i in range(N):
        t += int(S[-1-i])*pow(10, i)
        a[t%2019] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        t %= 2019
        r *= 10
        r %= 2019
        a[t] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

x, k, d = map(int, input().split())
x = abs(x)
if x > k*d:
    print(x-k*d)
else:
    if x < k*d*1000000:
        for i in range(1,k+1):
            p = x-i*d
            c = k-i
            if p <= 0:
                if c%2 != 0:
                    print(abs(d+p))
                    break
                elif c%2 == 0:
                    print(abs(p))
                    break
    else:
        for i in range(1000000,k+1):
            p = x-i*d
            c = k-i
            if p <= 0:
                if c%2 != 0:
                    print(abs(d+p))
                    break
                elif c%2 == 0:
                    print(abs(p))
                    break

### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)
if x > k*d:
    print(x-k*d)
else:
    p = x//d
    c = k-p
    if p == 0 or p==1:
          for i in range(1,k+1):
            p2 = x-i*d
            c = k-i
            if p2 <= 0:
                if c%2 != 0:
                    print(abs(d+p2))
                    break
                elif c%2 == 0:
                    print(abs(p2))
                    break
    elif (c%2 == 0):
        print(abs(x-p*d))
    else:
        print(abs(d-abs(x-p*d)))
### BUGGY CODE ###

s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=[0]*s[0]
a=0
b=0
for i in range(s[0]):
  u[i]=(t[i]+1)/2
for j in range(s[0]-s[1]+1):
  for l in range(j,j+s[1]):
    a+=u[l]
  b=max(b,a)
  a=0
print(b)

### FIXED CODE ###

s=list(map(int,input().split()))
t=list(map(int,input().split()))
c=s[1]
d=0
a=sum(t[0:c])
b=0
for j in range(s[0]-s[1]+1):
  if j==0:
    b=sum(t[:c])
    continue
  else:
    a+=(t[j+c-1]-t[j-1])
    b=max(b,a)
b+=s[1]
print(b/2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N,Q = [int(i) for i in input().split()] #N個の頂点、Q回の操作
aaabbb = [[int(i) for i in input().split()] for j in range(N-1)] #木の辺
pppxxx = [[int(i) for i in input().split()] for j in range(Q)] #操作

tree = [[] for i in range(N+1)]

for a,b in aaabbb:
    tree[a].append(b)
    tree[b].append(a)

#print(tree)

counter = [0 for i in range(N+1)]

for p,x in pppxxx:
    counter[p] += x

#print(counter)

def dfs(pos,parent,add):
    counter[pos] += add
    for next_pos in tree[pos]:
        if not next_pos == parent:
            dfs(next_pos,pos,counter[pos])

dfs(1,0,0)

#print(counter)

print(" ".join([str(i) for i in counter[1:]]))

### FIXED CODE ###

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

N,Q = [int(i) for i in input().split()] #N個の頂点、Q回の操作
aaabbb = [[int(i) for i in input().split()] for j in range(N-1)] #木の辺
pppxxx = [[int(i) for i in input().split()] for j in range(Q)] #操作

tree = [[] for i in range(N+1)]

for a,b in aaabbb:
    tree[a].append(b)
    tree[b].append(a)

#print(tree)

counter = [0 for i in range(N+1)]

for p,x in pppxxx:
    counter[p] += x

#print(counter)

def dfs(pos,parent,add):
    counter[pos] += add
    for next_pos in tree[pos]:
        if not next_pos == parent:
            dfs(next_pos,pos,counter[pos])

dfs(1,0,0)

#print(counter)

print(" ".join([str(i) for i in counter[1:]]))
### BUGGY CODE ###

def sol():
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        if i<n-1:
            if s[i]==s[i+1]:
                ans=max(ans,1)
        for j in range(i+2,n):
            if s[i]==s[j] and j-i>1:
                ii=i
                jj=j
                if j<n-1:
                    while s[ii+1]==s[jj+1]:
                        ii+=1
                        jj+=1
                        if ii==j-1 or jj==n-1:
                            break
                    ans=max(ans,ii-i+1)
    return ans
print(sol())

### FIXED CODE ###

n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    d={}
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in d:
            if d[t]+m-1<i:
                flg=True
                break
        else:
            d[t]=i
    if flg:
        l=m
    else:
        r=m-1
print(l)
### BUGGY CODE ###

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

for i in range(1, N+1):
    a_sum = len([j for j in a_list if j == i])
    print(a_sum)

### FIXED CODE ###

N = int(input())
a_list = [i for i in input().split()]
result = [0 for i in range(1, N+1)]

for i in a_list:
    result[int(i)-1] += 1

for a in result:
    print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q=map(int,input().split())

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

ans=[0]*N
for i in range(Q):
  p,x=map(int,input().split())
  p-=1
  ans[p]+=x

seen=["False" for _ in range(N)]
def solve(n):
  seen[n]="True"
  for i in graph[n]:
    if seen[i]=="False":
      ans[i]+=ans[n]
      solve(i)
  return

solve(0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q,*abpx=map(int,sys.stdin.read().split())

graph=[[] for _ in range(N)]
for a,b in zip(*[iter(abpx[:2*(N-1)])]*2):
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

f=[0]*N
for p,x in zip(*[iter(abpx[2*(N-1):])]*2):
    p-=1
    f[p]+=x

ans=[0 for _ in range(N)]
visited=[False]*N
def c(i,p):
    if visited[i]:
        return 
    visited[i]=True
    w=f[i]+p
    ans[i]=w
    ch=graph[i]
    for x in ch:
        c(x,w)

c(0,0)
print(*ans)
### BUGGY CODE ###

from collections import*
n,k,*h=map(int,open(0).read().split())
dp=defaultdict(int)

for i in range(1,n+1):
    dp[i]=float("inf")
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
            dp[i+j]=min(abs(h[i]-h[i+j])+dp[i],dp[i+j])
        else:
            break
print(dp[n-1])


### FIXED CODE ###

from collections import*
n,k,*h=map(int,open(0).read().split())
dp=defaultdict(int)

for i in range(1,n+1):
    dp[i]=float("inf")
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
            dp[i+j]=min(abs(h[i]-h[i+j])+dp[i],dp[i+j])
        else:
            break
print(dp[n-1])
### BUGGY CODE ###

N = int(input())
S = input()
sint = [0]
prev = S[0]
DEBUG = False
def dbg(*something):
    if DEBUG:
        print(*something)

for s in S:
    if prev == s:
        sint[-1] = sint[-1] + 1
    else:
        prev = s
        sint.append(1)
if len(sint) % 2 == 1:
    if S[0] == '#':
        sint = [0] + sint
    else:
        sint.append(0)
elif S[0] == '#':
    sint = [0] + sint + [0]
dbg(sint)

def count2(numSB,numSW):
    dbg('len:',len(sint))
    if len(sint) < 2:
        return 0
    sint.pop(0)
    sint.pop()
    
    if len(sint) < 2:
        return 0
    b = sint.pop(0)
    w = sint.pop()
    
    numSR =  b + w + count2(numSB-b,numSW-w)
    dbg(numSB,numSW,numSR)
    # if numSB <= numSW and numSB <= numSR:
    #     return numSB
    # elif numSW <= numSB and numSW <= numSR:
    #     return numSW
    # else:
    #     return numSR
    return numSR

def count3(numSB,numSW):
    dbg('len:',len(sint))
    numSR = 0
    while len(sint) >= 4:
    # if len(sint) < 2:
    #     return 0
        sint.pop(0)
        sint.pop()
    
    # if len(sint) < 2:
    #     return 0
        b = sint.pop(0)
        w = sint.pop()
    
        numSR =  b + w + numSR

    # if numSB <= numSW and numSB <= numSR:
    #     return numSB
    # elif numSW <= numSB and numSW <= numSR:
    #     return numSW
    # else:
    #     return numSR
    return numSR

def hoge(numSW):
    fuga = [1 for i in range(N)]
    numc = numSW
    numcmin = numc
    for s in S:
        if s == '#':
            #b2w
            numc = numc + 1
        else:
            numc = numc -1
            if numc < numcmin:
                numcmin = numc
    return numcmin


numSB = 0
numSW = 0
for i,v in enumerate(sint):
    if i % 2 == 1:
        numSB = numSB + v
    else:
        numSW = numSW + v

numSR = count3(numSB,numSW)
dbg('numSW:',numSW)
dbg('numSB',numSB)
dbg('numSR',numSR)
print(hoge(numSW))
'''
22
#####.....####..###...####....#.#.#
...################################
'''


### FIXED CODE ###

_ = input()
S = input()
numc = S.count('.')
numcmin = numc
for s in S:
    if s == '#':
        numc = numc + 1
    else:
        numc = numc -1
        if numc < numcmin:
            numcmin = numc
print(numcmin)
### BUGGY CODE ###

import math

K = int(input())

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

### FIXED CODE ###

import math

K = int(input())

sum = 0
gcd = 0
for a in range(K):
  for b in range(K):
    gcd = math.gcd(a+1, b+1)
    for c in range(K):
      sum += math.gcd(gcd, c+1)
      
print(sum)
### BUGGY CODE ###

n = int(input())

l = list()
c = 0

for i in range(n):
    x = input()
    if x in l:
        c += 0
    else:
        c += 1
        l.append(x)

print(c)
        


### FIXED CODE ###

n = int(input())

l = list()
c = 0

for i in range(n):
    x = input()
    l.append(x)

l = set(l)
print(len(l))
### BUGGY CODE ###

def main():
    n,s = map(int,input().split())
    A = list(map(int,input().split()))
    dp = [[[] for j in range(s+1)] for i in range(n+1)]

    mod = 998244353

    ans = 0

    dp[0][0] = [1]

    for i in range(n):
        for j in range(s):
            if j == 0:
                if A[i] <= s:
                    dp[i+1][A[i]].append(i)
            elif dp[i][j]:
                dp[i+1][j] += dp[i][j]
                if A[i]+j <= s:
                    dp[i+1][j+A[i]] = dp[i][j]
        if dp[i+1][s]:
            for num in dp[i+1][s]:
                ans += ((num+1)*(n-i))%mod
                ans %= mod
            dp[i+1][s] = []

    print(ans%mod)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
n,s = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
ans = 0
dp = np.zeros(s+1,np.int64)
for i in A:
    dp[0] += 1
    dp[i:] += dp[:-i].copy()
    dp %= mod
    ans += dp[-1]
print(ans%mod)
### BUGGY CODE ###

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

while max(a) - min(a) > 0:
    a.sort()
    a[-1] = a[-1]%a[0]
    if a[-1] == 0:
        del a[-1]

print(min(a))

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    g = a[0]

    for i in range(1, n):
        g = fractions.gcd(g, a[i])
    
    print(g)

main()
### BUGGY CODE ###

from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic={}
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
   x=Fraction(A,B)
   if x in dic:
    dic[x]+=1
   else:
    dic[x]=1
ans=1
for k in dic:
 if  -1/k in dic:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=pow(2,dic[k],mod)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)


### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret

# 全探索だと
# 3^N通りになってTLEだこれ

# 制限がなければ、iごとにmaxを取っておわりO(N)

# iの時の最善の状態が[i,j](jは行動)のとき、i+1最善の状態は[i+1,k](k!=j)となる
# これはDPで実装できそう！


import numpy as np

N = read_a_int()
ABC = np.array(read_matrix(N))
# A, B, C = read_col(N, 3)

dp = np.full((N, 3), -float('inf'))
# 0->a,1->b,2->c

dp[0, :] = ABC[0]

for i in range(N - 1):
    dp[i + 1, 0] = dp[i, 1:].max()+ABC[i+1, 0]
    dp[i + 1, 1] = dp[i, (0, 2)].max() + ABC[i+1, 1]
    dp[i + 1, 2] = dp[i, :2].max()+ABC[i+1, 2]

# print(dp)
print(int(dp[N-1].max()))

### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret

# 全探索だと
# 3^N通りになってTLEだこれ

# 制限がなければ、iごとにmaxを取っておわりO(N)

# iの時の最善の状態が[i,j](jは行動)のとき、i+1最善の状態は[i+1,k](k!=j)となる
# これはDPで実装できそう！


# import numpy as np

N = read_a_int()
# ABC = np.array(read_matrix(N))
# # A, B, C = read_col(N, 3)

# dp = np.full((N, 3), -float('inf'))
# # 0->a,1->b,2->c

# dp[0, :] = ABC[0]

# for i in range(N - 1):
#     dp[i + 1, 0] = dp[i, 1:].max()+ABC[i+1, 0]
#     dp[i + 1, 1] = dp[i, (0, 2)].max() + ABC[i+1, 1]
#     dp[i + 1, 2] = dp[i, :2].max()+ABC[i+1, 2]

# # print(dp)
# print(int(dp[N-1].max()))

# TLEしたのでpypy3仕様にかきなおし

ABC = read_matrix(N)

# dp = np.full((N, 3), -float('inf'))
dp = [[-float('inf') for _ in range(3)] for _ in range(N)]
# 0->a,1->b,2->c

for i in range(3):
    dp[0][i] = ABC[0][i]

for i in range(N - 1):

    for j in range(3):
        iterlist = [0, 1, 2]
        iterlist.remove(j)
        dp[i+1][j] = max([dp[i][k] + ABC[i+1][j] for k in iterlist])

# print(dp)
print(int(max(dp[-1])))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def func():
    N = int(input())
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
            else:
                dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())

### FIXED CODE ###

import sys
input = sys.stdin.readline

def func():
    N = int(input())
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
                continue
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())
### BUGGY CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x = tuple(permutations(seq, D))
def main():
    #print(x)
    ans = float("inf")
    for cand in x:
        cnt = 0
        G=G2
        for ind in cand:
            probpoint = (ind + 1) * 100
            if G<=0:
                break
            if G <= probpoint * (probs[ind][0] - 1):
                cnt = cnt + ceil(G / probpoint)
                G=G-probpoint*ceil(G / probpoint)
            else:
                cnt=cnt+probs[ind][0]
                G=G-(probpoint * probs[ind][0]+probs[ind][1])
        ans=min(ans,cnt)
    print(ans)

if __name__=='__main__':
    main()



### FIXED CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x=[]
for i in range(0,D+1):
    l=combinations(seq,i)
    for j in l:
        x.append(j)
x=tuple(x)
#print(x)
infty=100000
#print(x)
ans = infty
for cand in x:
    cnt = 0
    G=G2
    l=[0]*D
    for ind in cand:
        probpoint = (ind + 1) * 100
        G=G-(probpoint * probs[ind][0]+probs[ind][1])
        cnt = cnt + probs[ind][0]
        l[ind]=1
    #print(l,G,cnt)
    for i in range(D-1,-1,-1):
        if G<=0:
            break
        elif l[i]==0:
            probpoint = (i + 1) * 100
            num=ceil(G/probpoint)
            if num<probs[i][0]:
                G=G-num*probpoint
                cnt=cnt+num
            #print(cnt)
            break
    if G<=0:
        ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

import pprint

H, W = list(map(int, input().split()))
A = []
for h in range(H):
    A.append([s for s in input()])
x, y = 0, 0
goal_x, goal_y = W - 1, H - 1
while not (x == goal_x and y == goal_y):
    for diff_x, diff_y in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        tmp_x = x + diff_x
        tmp_y = y + diff_y
        if tmp_x < 0 or tmp_x >= W or tmp_y < 0 or tmp_y >= H:
            continue
        if A[tmp_y][tmp_x] == "#":
            if diff_x == -1 or diff_y == -1:
                print("Impossible")
                exit()
            A[y][x] = "."
            x += diff_x
            y += diff_y
            # print(y, x)
            # pprint.pprint(A)
            break

A[goal_y][goal_x] = "."
# pprint.pprint(A)

for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            print("Impossible")
            exit()
print("Possible")


### FIXED CODE ###

import pprint

H, W = list(map(int, input().split()))
A = []
for h in range(H):
    A.append([s for s in input()])
x, y = 0, 0
goal_x, goal_y = W - 1, H - 1
count = 0
while not (x == goal_x and y == goal_y):
    for diff_x, diff_y in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        tmp_x = x + diff_x
        tmp_y = y + diff_y
        if tmp_x < 0 or tmp_x >= W or tmp_y < 0 or tmp_y >= H:
            continue
        if A[tmp_y][tmp_x] == "#":
            if diff_x == -1 or diff_y == -1:
                print("Impossible")
                exit()
            A[y][x] = "."
            x += diff_x
            y += diff_y
            # print(y, x)
            # pprint.pprint(A)
            break
    count += 1
    if (W + H - 2) < count:
        print("Impossible")
        exit()

A[goal_y][goal_x] = "."
# pprint.pprint(A)

for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            print("Impossible")
            exit()
print("Possible")
### BUGGY CODE ###

x,y = (int(i) for i in input().split())
if x== y:
  print(-1)
  exit()
for i in range(1,10**18//x):
  ans = x*i
  if ans%y != 0:
    print(ans)
    exit()
print(-1)

### FIXED CODE ###

x,y = (int(i) for i in input().split())
if x%y == 0 or y == 1:
  print(-1)
  exit()
else:
  print(x*(y-1))
### BUGGY CODE ###

goods, ticket = map(int, input().split())
list = list(map(int, input().split()))
sum = 0
for i in range(ticket):
  list.sort(reverse=True)
  list[0] //= 2
for j in list:
  sum += j
print(sum)

### FIXED CODE ###

import heapq

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

for i in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))