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

import numpy as np

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]

direction = [[0,1],[0,-1],[1,0],[-1,0]]
black = np.zeros((H,W))
que = []
for i in range(H):
  for j in range(W):
    if G[i][j] == '#':
      que.append([i,j])
      black[i][j] = 0
def main():
  while que:
    nh, nw = que.pop(0)
    for dh, dw in direction:
      if nh+dh<0 or nh+dh>H-1 or nw+dw<0 or nw+dw>W-1:
        continue
      if black[nh+dh][nw+dw] > 0:
        continue
      que.append([nh+dh,nw+dw])
      black[nh+dh][nw+dw] = black[nh][nw]+1
  print(int(np.max(black)))

if __name__ == "__main__":
  main()

### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

def GCM(m, n):
    r = m%n
    if r == 0: return n
    else: return GCM(n, r)
        
while 1:
    try:
        n = input()
        c = 0
        for i in range(2,n+1):
            for j in range(2,i):
                if GCM(i, j) != 1:
                    break
            else:
                c += 1
        print c
    except EOFError:
        break

### FIXED CODE ###

n = 10**6
c = 0
ps = [False]*(n+1)
for i in xrange(2, n+1):
    if i%2 != 0 or i == 2:
        ps[i] = True
for i in xrange(2, int(n**0.5+1)):
    if ps[i]:
        for j in xrange(i**2, n+1, i):
            ps[j] = False

while 1:
    try:
        n = input()
        if n == 2: print 1
        else: print len([0 for i in xrange(2, n+1) if ps[i]])
    except EOFError:
        break
### BUGGY CODE ###

import collections
n, m = map(int, input().split())
par = list(range(2 * n))

# print(par)


# union find(parには0も入れているので、par[1]=1になる)
def find(x):
    while par[x] != x:
        x = par[x]
    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    par[x1] = y1


# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 5)]

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(n):
    s[find(k)] += 1

print(max(s))


### FIXED CODE ###

import collections
n, m = map(int, input().split())
par = list(range(2 * n))

# print(par)


# union find(parには0も入れているので、par[1]=1になる)
def find(x):

    while par[x] != x:
        tmp = par[x]
        par[x] = par[par[x]]
        x = par[x]

    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    if x1 != y1:
        par[x1] = y1


# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 5)]

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(n):
    s[find(k)] += 1

print(max(s))
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
ans = 0
for i in range(a,b+1):
    if not i % c == 0 and not i % d == 0:
        ans += 1
print(ans)

### FIXED CODE ###

import math

def lcm(a, b):
    return (a*b)//math.gcd(a, b)

a, b, c, d = map(int, input().split())
e = lcm(c, d)

total = b - (a - 1)
cc = b//c - (a-1)//c
dd = b//d - (a-1)//d
ee = b//e - (a-1)//e

ans = total - cc - dd + ee
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
Rindexes = [i for i, x in enumerate(S) if x == 'R']
Gindexes = [i for i, x in enumerate(S) if x == 'G']
Bindexes = [i for i, x in enumerate(S) if x == 'B']

total = len(Rindexes) * len(Gindexes) * len(Bindexes)
count = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2*j - i
    if S[i] != S[j]:
      if S[i] != 'R' and S[j] != 'R' and k in Rindexes:
        count += 1
      elif S[i] != 'G' and S[j] != 'G' and k in Gindexes:
        count += 1
      elif S[i] != 'B' and S[j] != 'B' and k in Bindexes:
        count += 1
print(total - count)

### FIXED CODE ###

N = int(input())
S = input()
rcount = 0
gcount = 0
bcount = 0
for i in range(N):
  if S[i] == 'R':
    rcount += 1
  elif S[i] == 'G':
    gcount += 1
  elif S[i] == 'B':
    bcount += 1

total = rcount * gcount * bcount
count = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2*j - i
    if k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
      count += 1
print(total - count)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [10**9+10] * N
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2, N):
  dp[i] = 10**9+10
  for j in range(1,min(i+1,K+1)):
    tmp = dp[i-j]+abs(h[i]-h[i-j])
    dp[i] = min(dp[i], tmp)
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9

c = [INF] * N
c[0] = 0

for i in range(N):
  tmp = []
  for j in range(1, min(K, i)+1):
    c[i] = min(c[i-j] + abs(h[i] - h[i-j]), c[i])
print(c[-1])
### BUGGY CODE ###

import queue
import copy
def dfs(L,start,end):
    stack = []
    stack.append(start)

    visited = []
    path =[ [] for i in range((len(L)+1))]
    path[start].append(start)

    while stack:
        node = stack.pop()
        if node == end:
            return path[end]
        for n in L[node]:
            if n[0] not in visited:
                a = copy.deepcopy(path[node])
                a.append(n[0])
                for val in a:
                    path[n[0]].append(val)
                stack.append(n[0])
                visited.append(n[0])

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

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))


L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

pp = []
for i in range(len(p)):
    pp.append([p[i][1],p[i][0],p[i][2]])
p.extend(pp)
for i in range(Q):
    v1 = dfs(L,xy[i][0],K)
    v2 = dfs(L,K,xy[i][1])
    v1.extend(v2[1:])
    cost = 0
    for j in range(len(v1)-1):
        for k in range(len(p)):
            if p[k][0] == v1[j] and p[k][1] == v1[j+1]:
                cost += p[k][2]
    print(cost)


### FIXED CODE ###

import sys
def dfs(L,start):
    stack = [start]

    path =[-1]*len(L)
    path[start] = 0
    while stack:
        node = stack.pop()
        for n in L[node]:
            if path[n[0]] < 0:
                path[n[0]] = path[node]  + n[1]
                stack.append(n[0])

    return path

#input
input = sys.stdin.readline
N = int(input())
p = []
for i in range(N-1):
    l = list(map(int,input().split()))
    p.append(l)

Q,K = map(int,input().split())
xy = []
for i in range(Q):
    xy.append(list(map(int,input().split())))

#neigher list
L = [ [] for i in range(N+1)]
for l in p:
    L[l[0]].append([l[1],l[2]])
    L[l[1]].append([l[0],l[2]])

d = dfs(L,K)

for i in range(Q):
    print(d[xy[i][0]]+ d[xy[i][1]])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
MOD = 10**9+7

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

def main():
    n = int(input().strip())
    v = list(map(int, input().strip().split()))
    a = v[0]
    lcm = v[0]
    for i in range(n):
        if i > 0:
            tmp = a
            a = gcd(a, v[i])
            c_lcm = tmp * v[i] // a
            lcm = c_lcm * lcm // gcd(c_lcm, lcm)
    ans = 0
    for i in range(n):
        ans += lcm // v[i] % MOD
    print(ans % MOD)
    # for i in range(n):
    #     ans += lcm * pow(v[i], MOD-2, MOD)
    # print(ans % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
MOD = 10**9+7

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

def main():
    n = int(input().strip())
    v = list(map(int, input().strip().split()))
    a = v[0]
    lcm = v[0]
    for i in range(n):
        if i > 0:
            tmp = a
            a = gcd(a, v[i])
            c_lcm = tmp * v[i] // a
            lcm = c_lcm * lcm // gcd(c_lcm, lcm)
    ans = 0
    # for i in range(n):
    #     ans += lcm // v[i]
    # print(ans % (10**9+7))
    for i in range(n):
        ans += lcm * pow(v[i], MOD-2, MOD)
    print(ans % MOD)


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

n = int(input())
lis = list(map(int,input().split()))
count = 0
for i,l in enumerate(lis):
    if i == 0:
        count += 1
    elif l <= min(sorted(lis[0:i])):
        count += 1
print(count)


### FIXED CODE ###

import sys
n = int(input())
lis = list(map(int,input().split()))
count = 0
mi = 0
for i,l in enumerate(lis):
    if i == 0:
        mi = l
        count += 1
    else:
        if l < mi:
            mi = l
        if mi >= l:
            count += 1
print(count)
### BUGGY CODE ###

from functools import reduce
import fractions

def lcm_base(a, b):
    return a * b / fractions.gcd(a, b)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = sorted(list(map(int, input().split())))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

n=int(input())
ls=list(map(int,input().split()))
ans=1
for i in range(n):
    ans=ans*ls[i]
if ans>10**18:
    ans=-1
print(ans)


### FIXED CODE ###

n=int(input())
ls=list(map(int,input().split()))
ans=1
for i in range(n):
    if ls[i]==0:
        print(0)
        quit()
for i in range(n):
    if ans>10**18:
        ans=-1
        break
    ans=ans*ls[i]
if ans>10**18:
    ans=-1
print(ans)
### BUGGY CODE ###

import sys
# import math
# import queue
# import copy
# import bisect#2分探索

def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())
def inputl():
    return list(map(int, input().split()))
def printl(li):
    print(*li, sep="\n")
def argsort(s):
    return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

#N = inputi()
#N, K = inputl()
#L = [int(input()) for i in range(N)]
#A = inputl()
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)


#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

K=inputi()
vals=[float('inf')]*K
visit=[]
vals[1]=0
q=[1]
flag=False
while len(q)>0:
    s=q.pop(0)
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.insert(0,s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)


### FIXED CODE ###

import sys
# import math
# import queue
# import copy
# import bisect#2分探索
from collections import deque


def input():
    return sys.stdin.readline()[:-1]
def inputi():
    return int(input())

K=inputi()
vals=[10**5+1]*K
visit=[]
vals[1]=0
q = deque([1])
flag=False
while len(q)>0:
    s=q.popleft()
    vs=vals[s]
    if s==0:
        print(vs+1) 
        flag=True
        break
    #visit.append(s)
    s0=(10*s)%K

    if vs<vals[s0]:
        vals[s0]=vs
        q.appendleft(s0)
    s1=(s+1)%K

    if vs+1<vals[s1]:
        vals[s1]=vs+1
        q.append(s1)
    #print(q,s,s0,s1,vals)

#if flag==False:
#    print(vals[0]+1)
### BUGGY CODE ###

N_K = list(map(int, input().split()))
 
count = 0
 
for a in range(1, N_K[0]+1):
  for b in range(1, N_K[0]+1):
    if a % b >= N_K[1]:
      count += 1
    
print(count)


### FIXED CODE ###

N, K = list(map(int, input().split()))
ans = 0

for b in range(1, N+1):
	p = N // b
	r = N % b
	
	ans += p * max(0, b-K)
	ans += max(0, r-K+1)
	
print(ans-N*(not K))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    print(s[l-1:r].count("AC"))


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
cnt=[0]*n
for i in range(n):
    cnt[i]=cnt[i-1]
    if s[i-1:i+1]=="AC":
        cnt[i]+=1
for i in range(q):
    l,r=map(int,input().split())
    print(cnt[r-1]-cnt[l-1])
### BUGGY CODE ###

nk = list(map(int,input().split()))
ls = list(map(int,input().split()))

d = dict()

for i in ls:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
       
adj = 0
key_num = len(d.keys()) 

while(1):
    if key_num <= nk[1]:
        print(adj)
        break
    min_idx = min(d.items(), key=lambda x:x[1])[0]
    min_num = min(d.items(), key=lambda x:x[1])[1]
    del d[min_idx]
    adj += min_num
    key_num -= 1

### FIXED CODE ###

nk = list(map(int,input().split()))
ls = list(map(int,input().split()))

d = dict()

for i in ls:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
       
l = list(d.values())
l.sort(reverse = True)

num = sum(l[nk[1]:])

print(num)
### BUGGY CODE ###

n,c = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n)]
ans = 0
left = [[0,0]]
right = [[0,0]]
for i in range(n):
    left.append([lis[i][0],left[-1][1]+lis[i][1]])
    right.append([c-lis[-(i+1)][0],right[-1][1]+lis[-(i+1)][1]])
for i in range(n+1):
    for j in range(n-i+1):
          # print(left[i],right[j],left[i][1]+right[j][1]-left[i][0]*2-right[j][0],left[i][1]+right[j][1]-left[i][0]-right[j][0]*2)
        ans = max(ans,left[i][1]+right[j][1]-left[i][0]*2-right[j][0])
        ans = max(ans,left[i][1]+right[j][1]-left[i][0]-right[j][0]*2)
print(ans)

### FIXED CODE ###

n,c = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n)]
ans = 0
num = 0
nu = 0
cou = 0
co = 0
go = 0
left = []
right = []
for i in range(n):
    num += lis[i][1]
    go = lis[i][0]
    ans = max(ans,num-go)
    if cou < num-go:
        cou = num-go
        left.append([go,num])
    else:
        try:left.append(left[-1])
        except:left.append([0,0])

for i in reversed(range(n)):
    nu += lis[i][1]
    go = c-lis[i][0]
    ans = max(ans,nu-go)
    if co < nu-go:
        co = nu-go
        right.append([go,nu])
    else:
        try:right.append(right[-1])
        except:right.append([0,0])
gone = 0
gon = 0
for i in range(n-1):
    gone += lis[i][1]
    ans = max(ans,gone + right[n-i-2][1] - lis[i][0] * 2 - right[n-i-2][0])
    gon += lis[-(i+1)][1]
    ans = max(ans,gon + left[n-i-2][1] - (c-lis[-(i+1)][0]) * 2 - left[n-i-2][0])
print(ans)
### BUGGY CODE ###

n,*a=map(int,open(0).read().split());s=a;c=0
while s:c+=sum(s);a=a[1:];*s,=map(min,zip(s,a))
print(c)

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

N = int(input())
S = [input() for _ in range(N)]
check = [True]*N
item = ""
cnt = 0
for i in range(N):
  if check[i] != False:
    item = S[i]
    cnt += 1
    for j in range(i+1,N):
      if S[j] == item:
        check[j] = False
print(cnt)

### FIXED CODE ###

N = int(input())
A = set([])
count = 0
for _ in range(N):
  item = input()
  if (item in A) == False:
    count = count + 1
    A.add(item)
print(count)
### BUGGY CODE ###

N,Q = (int(i) for i in input().split()) 
S = input()
ans = 0
ans_list = []

for i in range(Q):
	l, r = (int(i) for i in input().split())
	S_list = list(S[l-1 : r])
	for g in range(len(S_list)-1):
		if S_list[g] == "A" and S_list[g+1] == "C":
			ans += 1
	ans_list.append(ans)
	ans = 0

for i in range(len(ans_list)):
	print(ans_list[i])

### FIXED CODE ###

n,q=map(int,input().split())
s=input()

accumlate=[0]
now=0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        now+=1
    accumlate.append(now)

ans_list=[]
for g in range(q):
    l,r=map(int,input().split())
    ans_list.append(accumlate[r-1]-accumlate[l-1])

for m in range(q):
    print(ans_list[m])
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[N-L:N])
ans.append(mini)
for i in range(N-L-1,-1,-1) :
    if A[i] <= mini :
        mini = A[i]
    elif A[i+L] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
ans.reverse()
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

count=0
mainasu=0
num=int(input())
An=[int(i) for i in input().split()]
An_co=An
for i in An[0:num]:
    mainasu+=1
    An_co.pop(0)
    for w in An_co:
        
        if i==w:
            count=1
            break
    
if 0==count:
    print("YES")
    
else :
    print("NO")

### FIXED CODE ###

def duplication(lis):
    return len(lis) == len(set(lis)) 

num=int(input())
An=[int(i) for i in input().split()]


if duplication(An) == True:
    print("YES")
    
else :
    print("NO")
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
res = 0
Ab = [True] * N
cnt = 0
for i in range(N):
    if not Ab[i]:
        continue
    for j in range(i+1,N):
        if Ab[j] == False:
            continue
        if A[i] == A[j]:
            Ab[i] = False
        if A[j] % A[i] == 0:
            Ab[j] = False
print(Ab.count(True))



### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)
### BUGGY CODE ###

N=int(input())
S=list(map(int,input().split()))
S.sort(reverse=True)
p = [S.pop(0)]
r = S

for i in range(N):
    np = []
    for p_ in p:
        for k in range(len(r)):
            if r[k] < p_:
                np.append(r.pop(k))
                break
    p += np
    p.sort(reverse=True)

print("Yes" if len(r)==0 else "No")

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split()))
S.sort()
p = [S.pop(-1)]
r = S

for i in range(N):
    nr = []
    for p_ in p[::-1]:
        while r:
            r_ = r.pop()
            if r_ < p_:
                p.append(r_)
                break
            nr.append(r_)
    p.sort()
    r+=nr[::-1]

print("Yes" if len(r)==0 else "No")
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.' and (not (_p) in d):
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

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

dp=[[0 for i in range(W+1)] for j in range(N+1)] # dpリストを作る。dpの要素の数字は価値を表す。

for i in range(N): # １つ１つの商品について
    for w in range(W+1):
        if w>=list1[i][0]:# 重さ的に選ぶことができる
            dp[i+1][w]=max(dp[i][w],dp[i][w-list1[i][0]]+list1[i][1])
        else: # 重さ的に選べないので一個前のiのときのがそのまま
            dp[i+1][w]=dp[i][w]
print(dp[-1][-1])

### FIXED CODE ###

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

dp=[float('inf')]*100001 # dpリストを作る。
# dp[i]は、価値の総和がiになる時の質量の総和の最小。
dp[0]=0

for i in range(N): # １つ１つの商品について
    for j in range(100000,list1[i][1]-1,-1):
        dp[j]=min(dp[j],dp[j-list1[i][1]]+list1[i][0])

for i in range(100000,-1,-1):
    if dp[i]<=W:
        print(i)
        break
### BUGGY CODE ###

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

ans = 0
can = 1
for a in A:
    if can < a:
        print(-1)
        exit(0)
    else:
        can -= a
        can *= 2
can //= 2
can += A[-1]
real = A[-1]
for i in range(n-1,-1,-1):
    ans += real
    real = min(real,can//2)
    real += A[i]
    can //= 2
    can += A[i]
print(ans + 1)


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
Can = [0]*n
ans = 0
can = 1
for i,a in enumerate(A):
    if can < a:
        print(-1)
        exit(0)
    elif i < n:
        can -= a
        can *= 2
        Can[i] = can
real = A[-1]
for i in range(n-1,-1,-1):
    ans += real
    real = min(real,Can[i]//2)
    real += A[i]
print(ans + 1)