Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(1,n),n-1):
    list=[0]+[i]
    if all(p[list[j]][list[j+1]]==True for j in range(n)):
        ans+=1
print(ans)   

Fixed submission:
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not p[i[j]][i[j+1]]:
                break
print(ans)

Buggy python submission (verdict: Runtime Error):
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True

for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not p[i[j]][i[j+1]]:
                break
print(ans)

Fixed submission:
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not p[i[j]][i[j+1]]:
                break
print(ans)

Buggy python submission (verdict: Runtime Error):
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True

for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not p[i[j]][i[j+1]]:
                break
print(ans)

Fixed submission:
import itertools
n,m=map(int,input().split())
p=[[False]*n for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    p[a][b]=True
    p[b][a]=True
ans=0
for i in itertools.permutations(range(n),n):
    if i[0]==0:
        for j in range(n):
            if j==n-1:
                ans+=1
                break
            if not p[i[j]][i[j+1]]:
                break
print(ans)
Buggy python submission (verdict: Runtime Error):
n,k,x,y=map(int,input().split() for i in range(4)]
if n>k:
    print(x*k+y*(n-k))
else:
    print(x*k)


Fixed submission:
n=int(input())
k=int(input())
x=int(input())
y=int(input())
if n>k:
    print(x*k+y*(n-k))
else:
    print(x*n)
Buggy python submission (verdict: Runtime Error):
N,L=map(int,input().split())
S=[input() for i in range(N)]
print(''.join(S.sort()))


Fixed submission:
N,L=map(int,input().split())
S=list(input() for i in range(N))
S_sort=sorted(S)
print(''.join(S_sort))

Buggy python submission (verdict: Runtime Error):
N,L=map(int,input().split())
S=[input() for i in range(N)]
print(''.join(S.sort))

Fixed submission:
N,L=map(int,input().split())
S=list(input() for i in range(N))
S_sort=sorted(S)
print(''.join(S_sort))
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = list(map(int, input().split()))
ope = [list(map(int, input().split())) for _ in range(m)]
ope = sorted(ope, key=lambda x: x[1], reverse=True)
for i in range(m):
    for j in range(ope[i][0]):
        if min(a) < ope[i][1]:
            a[a.index(min(a))] = ope[i][1]
        else:
            break
print(sum(a))


Fixed submission:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ope = [list(map(int, input().split())) for _ in range(m)]
ope = sorted(ope, key=lambda x: x[1], reverse=True)
j = 0
for i in range(n):
    if a[i] < ope[j][1]:
        a[i] = ope[j][1]
        ope[j][0] -= 1
        if ope[j][0] == 0:
            j += 1
            if j == len(ope):
                break
    else:
        break
print(sum(a))

Buggy python submission (verdict: Runtime Error):
11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000

Fixed submission:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ope = [list(map(int, input().split())) for _ in range(m)]
ope = sorted(ope, key=lambda x: x[1], reverse=True)
j = 0
for i in range(n):
    if a[i] < ope[j][1]:
        a[i] = ope[j][1]
        ope[j][0] -= 1
        if ope[j][0] == 0:
            j += 1
            if j == len(ope):
                break
    else:
        break
print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n = map(int, input().split())
ans = 0
for i in range((n+1)//r+1):
    for j in range((n+1)//g+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)


Fixed submission:
r,g,b,n = map(int, input().split())
ans = 0
for i in range(n+1):
    for j in range(n+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n = map(int, input().split())
ans = 0
for i in range(n+1):
    for j in range(n+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)


Fixed submission:
r,g,b,n = map(int, input().split())
ans = 0
for i in range(n+1):
    for j in range(n+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
r,g,b,n = map(int, input().split())
ans = 0
for i in range(3001):
    for j in range(3001):
        k = n - (i*r + j*g)
        if k >= 0 and k%b == 0:
            ans += 1
print(ans)


Fixed submission:
r,g,b,n = map(int, input().split())
ans = 0
for i in range(n+1):
    for j in range(n+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import fractions
import copy
n = int(input())
a = list(map(int, input().split()))
a_r = copy.copy(a)
a_r.reverse()
cumsum_gcd = [0]
cumsum_gcd_r = [0]
for i in range(n-1):
    cumsum_gcd.append(fractions.gcd(cumsum_gcd[i], a[i]))
    cumsum_gcd_r.append(fractions.gcd(cumsum_gcd_r[i], a_r[i]))
cumsum_gcd_r.reverse()
print(cumsum_gcd, cumsum_gcd_r)
ans = []
for i in range(n):
    ans.append(fractions.gcd(cumsum_gcd[i], cumsum_gcd_r[i]))
print(max(ans)


Fixed submission:
import fractions
import copy
n = int(input())
a = list(map(int, input().split()))
a_r = copy.copy(a)
a_r.reverse()
cumsum_gcd = [0]
cumsum_gcd_r = [0]
for i in range(n-1):
    cumsum_gcd.append(fractions.gcd(cumsum_gcd[i], a[i]))
    cumsum_gcd_r.append(fractions.gcd(cumsum_gcd_r[i], a_r[i]))
cumsum_gcd_r.reverse()
ans = []
for i in range(n):
    ans.append(fractions.gcd(cumsum_gcd[i], cumsum_gcd_r[i]))
print(max(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
ac_l = []
ans = []
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_l.append(i)
for i in range(q):
    l, r = map(int, input().split())
    print(len([j for j in ac_l if j>=l-1 and j+1<=r-1]))


Fixed submission:
n, q = map(int, input().split())
s = input()
ac_count = [0]
ac_num = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_num += 1
    ac_count.append(ac_num)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_count[r-1] - ac_count[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
ac_l = []
ans = []
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_l.append(i)
for i in range(q):
    l, r = map(int, input().split())
    ans.append(len([j for j in ac_l if j>=l-1 and j+1<=r-1]))
for i in range(len(ans)):
    print(ans[i])


Fixed submission:
n, q = map(int, input().split())
s = input()
ac_count = [0]
ac_num = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_num += 1
    ac_count.append(ac_num)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_count[r-1] - ac_count[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
output = []
for _ in range(q):
    l, r = map(int, input().split())
    sub_s = s[l-1:r]
    ans = sub_s.count("AC")
    output.append(ans)
for i in range(q):
    print(output[i])


Fixed submission:
n, q = map(int, input().split())
s = input()
ac_count = [0]
ac_num = 0
for i in range(n-1):
    if s[i] + s[i+1] == "AC":
        ac_num += 1
    ac_count.append(ac_num)
for i in range(q):
    l, r = map(int, input().split())
    print(ac_count[r-1] - ac_count[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
taka = 0
aoki = 0
while (1):
    max_list = []
    max_list = [i for i, x in enumerate(a) if x == max(a)]
    max_val = 0
    max_index = 0
    for i in max_list:
        if(b[i] > max_val):
            max_index = i
    taka += a[max_index]
    b.pop(max_index)
    a.pop(max_index)
    if(len(a) == 0):
        print(taka - aoki)
        exit()
    max_list = []
    max_list = [i for i, x in enumerate(b) if x == max(b)]
    max_val = 0
    max_index = 0
    for i in max_list:
        if(b[i] > max_val):
            max_index = i
    aoki += b[max_index]
    a.pop(max_index)
    b.pop(max_index)
    if(len(a) == 0):
        print(taka - aoki)
        exit()

Fixed submission:
n = int(input())
a_b = []
b_sum = 0
for i in range(n):
    ai, bi = map(int, input().split())
    a_b.append(ai+bi)
    b_sum += bi
a_b.sort(reverse=True)
ans = 0
for i in range(len(a_b)):
    if i%2==0:
        ans += a_b[i]
print(ans-b_sum)
Buggy python submission (verdict: Runtime Error):
n = int(input())
p = [input() for i in range(n)]
max_value = p.index(max(p))
p[max_value] = int(p[max_value]) / 2
sum = 0
for i in range(len(p)):
    sum += int(p[i])
print(sum)


Fixed submission:
ChrismasDay = 25
text = "Christmas"
D = int(input())
D = 25 - D
for i in range(D):
    text = text + " Eve"
print(text)
Buggy python submission (verdict: Runtime Error):
N = input()
p = [int(input()) for i in range(N)]
print(sum(p) - max(p) // 2)

Fixed submission:
N = int(input())
p = [int(input()) for i in range(N)]
print(sum(p) - max(p) // 2)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
p = []
y = []
out = []
for _ in range(m):
    pi, yi = map(int, input().split())
    p.append(pi)
    y.append(yi)
    out.append(-1)

for i in range(n):
    index_list = []
    for j in range(len(p)):
        if p[j] == i+1:
            index_list.append([y[j], y.index(y[j])])
    index_list.sort()
    for k in range(len(index_list)):
        out[index_list[k][1]] = str(i+1).zfill(6) + str(k+1).zfill(6)

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


Fixed submission:
n, m = map(int, input().split())
d = [list() for i in range(n+1)] 
out = []
for i in range(m):
    pi, yi = map(int, input().split())
    d[pi].append([yi, i])
    out.append(-1)

for i in range(len(d)):
    d[i].sort()

for i in range(1, n+1):
    for j in range(len(d[i])):
        out[d[i][j][1]] = str(i).zfill(6) + str(j+1).zfill(6)

for i in range(len(out)):
    print(out[i])
Buggy python submission (verdict: Runtime Error):
import math
n, x = map(int,input().split())
xi = list(map(int,input().split()))

for i, n in enumerate(xi):
    xi[i] = abs(xi[i]-x)

if len(xi)==1:
    print(xi[0])
    exit()
    
xi.sort()
print(math.gcd(xi[0], xi[1]))


Fixed submission:
from fractions import gcd
n, x = map(int,input().split())
xi = list(map(int,input().split()))

for i, n in enumerate(xi):
    xi[i] = abs(xi[i]-x)
ans = xi[0]
for i in range(len(xi)):
    ans = gcd(ans, xi[i])
print(ans)

Buggy python submission (verdict: Runtime Error):
n, x = map(int,input().split())
xi = list(map(int,input().split()))

for i, n in enumerate(xi):
    xi[i] = abs(xi[i]-x)

while 1:
    out = min(xi)
    for i, n in enumerate(xi):
        if n%out!=0:
            for j in range(2,out+1):
                if out%j==0:
                    out = out / j
            continue
    print(int(out))
    exit()


Fixed submission:
from fractions import gcd
n, x = map(int,input().split())
xi = list(map(int,input().split()))

for i, n in enumerate(xi):
    xi[i] = abs(xi[i]-x)
ans = xi[0]
for i in range(len(xi)):
    ans = gcd(ans, xi[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
east_side = list(input())
west_side = []
ans = []
for i in range(len(east_side)):
    WE_sum = east_side.count("E") + west_side.count("W")
    ans.append(WE_sum)
    west_side.append(east_side[0])
    east_side.pop(0)
print(min(ans))


Fixed submission:
n = int(input())
s = input()
rev_counter = []
rev_num = s.count("E")
if s[0] == "E":
    rev_num -= 1
rev_counter.append(rev_num)
for i in range(1, n):
    if s[i] == "E" and s[i-1] == "E":
        rev_num -= 1
    elif s[i] == "W" and s[i-1] == "W":
         rev_num += 1
    rev_counter.append(rev_num)
print(min(rev_counter))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
east_side = list(input())
west_side = []
ans = 300000
for i in range(len(east_side)):
    WE_sum = east_side.count("E") + west_side.count("W")
    if(WE_sum < ans):
        ans = WE_sum
    west_side.append(east_side[0])
    east_side.pop(0)
print(ans)


Fixed submission:
n = int(input())
s = input()
rev_counter = []
rev_num = s.count("E")
if s[0] == "E":
    rev_num -= 1
rev_counter.append(rev_num)
for i in range(1, n):
    if s[i] == "E" and s[i-1] == "E":
        rev_num -= 1
    elif s[i] == "W" and s[i-1] == "W":
         rev_num += 1
    rev_counter.append(rev_num)
print(min(rev_counter))
Buggy python submission (verdict: Runtime Error):
A=int(input())
B=int(input())
T=int(input())
reward=0
time=0

for t in range(T):
    time += 1
    if time%A == 0:
        reward = reward + B
        
print(reward)

Fixed submission:
A, B, T = map(int, input().split())
reward=0
time=0

for t in range(T):
    time += 1
    if time%A == 0:
        reward = reward + B
        
print(reward)

Buggy python submission (verdict: Runtime Error):
aaa

Fixed submission:
A, B, T = map(int, input().split())
reward=0
time=0

for t in range(T):
    time += 1
    if time%A == 0:
        reward = reward + B
        
print(reward)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
cnt = 0
for i in range(1,len(s)):
    if s[i-1] == s[i]:
        new = (int(s[i])+1)%2
        s_li = list(s)
        s_li[i] = str(new)
        s = ''.join(s_li)
        cnt += 1
        
print(cnt)
    

Fixed submission:
s = input()
cnt = 0
for i in range(1,len(s)):
    if s[i-1] == s[i]:
        new = (int(s[i])+1)%2
        """
        s_li = list(s)
        s_li[i] = str(new)
        s = ''.join(s_li)
        """
        s = s[:i] + str(new) + s[i+1:]
        cnt += 1
        
print(cnt)
Buggy python submission (verdict: Runtime Error):
import numpy as np

N, M, C = map(int, input().split())
B = list(map(int, input().split())) 
A = np.zeros((N,M))

A[0:] = list(map(int, input().split())) 
A[1:] = list(map(int, input().split())) 

cnt = 0
z = 0
for A_line in A:
    for i,a in enumerate(A_line):
        z = z + a*B[i]
    if z+C >0:
        cnt += 1
    z = 0

print(cnt)

Fixed submission:
import numpy as np

N, M, C = map(int, input().split())
B = list(map(int, input().split())) 
A = np.zeros((N,M))



for i,_ in enumerate(A):
    A[i:] = list(map(int, input().split())) 

cnt = 0
z = 0
for A_line in A:
    for i,a in enumerate(A_line):
        z = z + a*B[i]
    if z+C >0:
        cnt += 1
    z = 0

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

cards = []
for i in range(M):
    Li, Ri = s_input()
    L.extend([Li])
    R.extend([Ri])
    cards.extend(list(range(Li, Ri+1)))

cards = set(cards)

ng_cards = set()
for card in cards:
    for i in range(M):
        if card < L[i] or card > R[i]:
            ng_cards.add(card)
            break

print(len(cards - ng_cards))




Fixed submission:
def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

for i in range(M):
    Li, Ri = s_input()
    L.extend([Li])
    R.extend([Ri])

L_max = max(L)
R_min = min(R)

num = R_min - L_max

if num >= 0:
    print(num + 1)
else:
    print(0)

Buggy python submission (verdict: Time Limit Exceeded):
def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

cards = []
for i in range(M):
    Li, Ri = s_input()
    L.append(Li)
    R.append(Ri)
    cards.append(list(range(Li, Ri+1)))

cards = set(sum(cards, []))

ng_cards = set()
for card in cards:
    for i in range(M):
        if card < L[i] or card > R[i]:
            ng_cards.add(card)
            break

print(len(list(cards - ng_cards)))




Fixed submission:
def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

for i in range(M):
    Li, Ri = s_input()
    L.extend([Li])
    R.extend([Ri])

L_max = max(L)
R_min = min(R)

num = R_min - L_max

if num >= 0:
    print(num + 1)
else:
    print(0)

Buggy python submission (verdict: Time Limit Exceeded):
def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

for i in range(M):
    Li, Ri = s_input()
    L.append(Li)
    R.append(Ri)

cards = set()
for i in range(len(L)):
    cards |= set(range(L[i], R[i]+1))

ng_cards = set()
for card in cards:
    for i in range(len(L)):
        if card < L[i] or card > R[i]:
            ng_cards.add(card)
            break

print(len(list(cards - ng_cards)))




Fixed submission:
def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

for i in range(M):
    Li, Ri = s_input()
    L.extend([Li])
    R.extend([Ri])

L_max = max(L)
R_min = min(R)

num = R_min - L_max

if num >= 0:
    print(num + 1)
else:
    print(0)
Buggy python submission (verdict: Time Limit Exceeded):
import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了：sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    S = input()

    while 1:
        if S == '':
            print('YES')
            sys.exit()
        elif re.search('dreamer$', S):
            S = S[:-7]
            # print('a', S)
        elif re.search('eraser$', S):
            S = S[:-6]
            # print('b', S)
        elif re.search('dream$', S):
            S = S[:-5]
            # print('c', S)
        elif re.search('erase$', S):
            S = S[:-5]
            # print('d', S)
        else:
            print('NO')
            sys.exit()

    print('YES')

if __name__ == "__main__":
    main()

Fixed submission:
import re  # 正規表現, findall('正規表現', 文字列), search('正規表現', 文字列)
import sys # プログラム終了：sys.exit()
# sys.setrecursionlimit(10**6) # 再帰呼び出しの上限を上げる

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))
# 文字列のまま受け取りたいときはinput()

def main():
    S = input()

    while 1:
        if S == '':
            print('YES')
            sys.exit()
        elif end_match('dreamer', S):
            S = S[:-7]
            # print('a', S)
        elif end_match('eraser', S):
            S = S[:-6]
            # print('b', S)
        elif end_match('dream', S):
            S = S[:-5]
            # print('c', S)
        elif end_match('erase', S):
            S = S[:-5]
            # print('d', S)
        else:
            print('NO')
            sys.exit()

def end_match(query, S):
    length = len(query)
    end = S[-length:]
    # print(query, end)
    if end == query:
        return True
    else:
        return False

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
H, W = map(int, input().split())
S = np.zeros((H,W))
for i in range(H):
    Si = np.array([ 0 if s == '.' else 1 for s in input()])
    S[i] = Si

column_max_spaces = np.zeros(H)
for i in range(H):
    max_count = 0
    _count = 0
    for j in range(W):
        if S[i,j] == 0:
            _count += 1
        else:
            if _count > max_count:
                max_count = _count
            _count = 0
    else:
        if _count > max_count:
            max_count = _count
    column_max_spaces[i] = max_count

row_max_spaces = np.zeros(W)
for j in range(W):
    max_count = 0
    _count = 0
    for i in range(H):
        if S[i,j] == 0:
            _count += 1
        else:
            if _count > max_count:
                max_count = _count
            _count = 0
    else:
        if _count > max_count:
            max_count = _count
    row_max_spaces[j] = max_count

print(int(np.max(column_max_spaces) + np.max(row_max_spaces) - 1))

Fixed submission:
import numpy as np
H, W = map(int, input().split())
S = np.zeros((H,W))
for i in range(H):
    Si = np.array([int(s == '.') for s in input()])
    S[i] = Si
    
top = S.copy()
bottom = S.copy()
left = S.copy()
right = S.copy()

for i in range(1, H):
    top[i] = (top[i-1] + 1) * S[i]
    bottom[-i-1] = (bottom[-i] + 1) * S[-i-1]

for j in range(1, W):
    left[:,j] = (left[:,j-1] + 1) * S[:,j]
    right[:,-j-1] = (right[:,-j] + 1) * S[:,-j-1]

print(np.max((top + bottom + left + right - 3).astype(np.int)))