Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

I = []
X = []
left_init = list(range(1,N))+[0,0]
right_init = list(range(-1,N))
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = left_init[:]
    right = right_init[:]
    for i in sorted(range(N), key=arr.__getitem__):
        l = left[i-1]
        r = right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        I.append(l*N+i); X.append(x)
        if i<N-1:
            I.append((i+1)*N+i); X.append(-x)
        if r<N-1:
            I.append(l*N+r+1); X.append(-x)
        if i<N-1 and r<N-1:
            I.append((i+1)*N+r+1); X.append(x)

del B

ticket_sum = [0]*(N*N)
for i,x in zip(I,X):
    ticket_sum[i] += x
    
# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)


Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = tuple(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)
left_init = list(range(1,N))+[0,0]
right_init = list(range(-1,N))
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = left_init[:]
    right = right_init[:]
    for i in sorted(range(N), key=arr.__getitem__):
        l = left[i-1]
        r = right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
        if i<N-1 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

del B

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)


Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)

for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(1,N))+[0,0]
    right = list(range(-1,N))
    for i in sorted(range(N), key=arr.__getitem__):
        l = left[i-1]
        r = right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
        if i<N-1 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

del B

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*(N+1)
    for i in sorted(range(N), key=lambda i: arr[i]):
        filled[i] = True
        l = i if (not filled[i-1]) else left[i-1]
        r = i if (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
        if i<N-1 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)


Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Buggy python submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*(N+1)
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (not filled[i-1]) else left[i-1]
        r = i if (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
	        if i<N-1:
                ticket_sum[(i+1)*N+r+1]+=x

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)


Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

N,M

for i in range(1,N):
    A[i] += A[i-1]

add_list = []

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*(N+1)
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (not filled[i-1]) else left[i-1]
        r = i if (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        add_list.append((l*N+i,x))
        if i<N-1:
            add_list.append(((i+1)*N+i,-x))
        if r<N-1:
            add_list.append((l*N+r+1,-x))
        if i<N-1 and r<N-1:
            add_list.append(((i+1)*N+r+1,x))

del B

ticket_sum = [0]*(N*N)
for i,x in add_list:
    ticket_sum[i] += x

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

N,M

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*(N+1)
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (not filled[i-1]) else left[i-1]
        r = i if (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
        if i<N-1 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

N,M

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*N
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (i==0) or (not filled[i-1]) else left[i-1]
        r = i if (i==N-1) or (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
        if i<N-1 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

# 2d累積和
for i in range(1,N):
    for j in range(N):
        ticket_sum[N*i+j]+=ticket_sum[N*(i-1)+j]
for i in range(N):
    for j in range(1,N):
        ticket_sum[N*i+j]+=ticket_sum[N*i+j-1]

dist = [0]*(N*N)
for i in range(N):
    for j in range(i,N):
        dist[i*N+j] = A[j]-A[i]

answer = max(x-y for x,y in zip(ticket_sum,dist))
print(answer)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)