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

import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    P -= 1
    P.reshape((N, N))
    return N, P


@njit
def dfs(N, Q, visited, y, x, D):
    for dy, dx in D:
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            # 4隣接が除去済みマスなら、コストなしで到達可能
            if not visited[ny, nx] and Q[ny, nx, 0] > Q[y, x, 0] + Q[ny, nx, 1]:
                Q[ny, nx, 0] = Q[y, x, 0] + Q[ny, nx, 1]
                visited[ny, nx] = True
                dfs(N, Q, visited, ny, nx, D)


@njit
def np_solve(N, P, INF=10**9):
    Q = numpy.empty((N, N, 2), dtype=numpy.int32)
    
    for i in range(N):
        for j in range(N):
            Q[i, j, :] = min([i, j, N-i-1, N-j-1]) + 1, 1

    D = ((0, 1), (1, 0), (-1, 0), (0, -1))
    visited = numpy.zeros((N, N), dtype=numpy.bool_)
    ans = 0

    for p in P:
        y, x = p//N, p%N
        r = INF
        for dy, dx in D:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < N:
                r = min(r, Q[ny, nx, 0])
            else:
                r = 0
        ans += r
        Q[y, x, :] = r, 0
        visited.fill(False)
        visited[y, x] = True
        dfs(N, Q, visited, y, x, D)
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = np_solve(*inputs)
    if outputs is not None:
        print("{}".format(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))
### BUGGY CODE ###

L, R = map(int, input().split())
R = min(R, L+4038)
ans = 2018
for i in range(L, R+1):
    for j in range(i+1, R+1):
        x = i*j%2019
        ans = min(ans, x)
print(ans)


### FIXED CODE ###

L, R = map(int, input().split())
R = min(R, L+4038)
ans = 2018
for i in range(L, R+1):
    for j in range(i+1, R+1):
        x = i*j%2019
        if ans > x:
            ans = x
print(ans)
### BUGGY CODE ###

#C問題
#考え方：平方根に近いところを探す。
#平方根を切り上げた値からスタート。割り切れた時点で終了。
#TLEになった。原因として考えられるのは何か？ものすごい大きな数の時にうまくいかない？
import math
N = int(input())
sq_N = int(math.sqrt(N))
i = 0
while True:
    if N ==1:
        A = 1
        B = 1
        break;
    elif N% (sq_N+i) ==0:
        A = sq_N+i
        B = int(N/A)
        break;
    else:
        i = i+1
print(A-1+B-1)
    

### FIXED CODE ###

#C問題
#考え方：平方根に近いところを探す。
#平方根を切り上げた値からスタート。割り切れた時点で終了。
#TLEになった。原因として考えられるのは何か？ものすごい大きな数の時にうまくいかない？
#素数の時に厳しい。
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
import numpy as np


def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]

N = int(input())
lis_1 = make_divisors(N)
A = getNearestValue(lis_1,math.sqrt(N))
B = int(N/A)

print(A+B-2)
### BUGGY CODE ###

n,k = map(int,input().split())
for i in range(n):
  if n > abs(n-k):
    n = abs(n-k)
  else:
    break
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
s = n%k
t= abs(s-k)
if s<t:
  print(s)
else:
  print(t)
### BUGGY CODE ###

N, P = [int(a) for a in input().split()]
# N, P = [10, 2972439611840]
prod = P
ans = 1
if N == 1:
    ans = P
else:
    for i in range(2, P):
        if i > 2 and i % 2 == 0:
            continue
        if prod < i ** N:
            break
        count = 0
        while prod % i == 0:
            prod /= i
            count += 1
            if count % N == 0:
                ans *= i
print(str(ans))

### FIXED CODE ###

N, P = [int(a) for a in input().split()]
# N, P = [10, 2972439611840]
prod = P
ans = 1
if N == 1:
    ans = P
elif N > 40:
    ans = 1
else:
    for i in range(2, P):
        if i > 2 and i % 2 == 0:
            continue
        if prod < i ** N:
            break
        count = 0
        while prod % i == 0:
            prod /= i
            count += 1
            if count % N == 0:
                ans *= i
print(str(ans))
### BUGGY CODE ###

N = int(input())
N = str(N)[::-1]
before = 0
ans = 0
ansB = 0
for i, c in enumerate(N):
    n = int(c)+before
    ansB += int(c)
    if 0 <= n < 5:
        before = 0
        ans += n
    elif n == 5:
        if i+1 == len(N):
            before = 0
            ans += n
            continue
        if int(N[i+1]) < 5:
            before = 0
            ans += n
        else:
            ans += 10-n
            before = 1
    else:
        ans += 10-n
        before = 1
print(ans + before)



### FIXED CODE ###

import sys

input = sys.stdin.readline
N = list(map(int, input().strip()))[::-1]
ans = 0
before = 0
L = len(N)
for i, c in enumerate(N):
    n = c + before
    if 0 <= n < 5:
        before = 0
        ans += n
    elif n == 5:
        if i+1 == L:
            before = 0
            ans += n
            continue
        if N[i+1] < 5:
            before = 0
            ans += n
        else:
            ans += 10-n
            before = 1
    else:
        ans += 10-n
        before = 1
print(ans + before)
### BUGGY CODE ###

#%%

#%%
n = int(input())

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

l = factorize(n)


import itertools
c = list(itertools.product(range(2), repeat=len(l)))
#print(c)

flag = False
k = 10**15
for i in range(len(c)):
    a = 1
    b = 1
    for j in range(len(c[i])):
        if c[i][j] == 0:
            a *= l[j]
        else:
            b *= l[j]
    k = min(k, a+b)
    

print(k-2)


### FIXED CODE ###

#%%
n = int(input())
a = 10**15


x = int(n**0.5)
x += 1
for i in range(x, 1, -1):
    if n%i == 0:
        a = i
        b = n//i
        break
#print(a, b)

if a == 10**15:
    print(n-1)
else:
    print(a+b-2)
### BUGGY CODE ###

n=int(input())
i=0
b=[]
q=n
ans=""

while 1:
  r=q%(-2)
 
  if r==0:
    b.append(0)
    q=int(q/(-2))
  else:
    b.append(1)
    q=int(q/(-2)+0.5)
    if q==0:
      break
  i=i+1

b.reverse()
for j in range(i+1):
  ans=ans+str(b[j])
  
print(ans)


### FIXED CODE ###

n=int(input())
i=0
b=[]
q=n
ans=""

while 1:
  r=q%(-2)
  if q==0:
    b.append(0)
    break
 
  if r==0:
    b.append(0)
    q=int(q/(-2))
  else:
    b.append(1)
    q=int(q/(-2)+0.5)
    if q==0:
      break
  i=i+1

b.reverse()
for j in range(i+1):
  ans=ans+str(b[j])
  
print(ans)
### BUGGY CODE ###

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

while(all(i%2==0 for i in a)):
  list=[i/2 for i in a]
  cut+=1
print(cut)

### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
cnt = 0
while all(i%2==0 for i in a):
    a = [i/2 for i in a]
    cnt += 1
print(cnt)
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
BC=[]
for _ in range(m):
    b,c=map(int,input().split())
    BC.append((b,c))
BC=sorted(BC, reverse=True, key=lambda x: x[1])

for i in range(m):
    b,c=BC[i]
    ind=bisect.bisect_left(A, c)
    if ind>0:
        x,y=min(ind, b), max(ind, b)
        A=A[x:y]+[c]*x+A[y:]
    else:
        break
print(sum(A))

### FIXED CODE ###

import numpy as np
n,m=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
A=np.array(A, dtype=np.int64)
BC=[]
for _ in range(m):
    b,c=map(int,input().split())
    BC.append((b,c))
BC=sorted(BC,reverse=True, key=lambda x:x[1])
D=[]
cnt=0
for i in range(m):
    b,c=BC[i]
    cnt+=b
    D+=[c]*b
    if cnt>=n:
        break
if cnt>=n:
    D=D[:n]
else:
    D+=[0]*(n-cnt)
D=np.array(D, dtype=np.int64)

A=np.maximum(A,D)
print(np.sum(A))
### BUGGY CODE ###

K = int(input())
total = 0


def ab_gcd(a: int, b: int):
    small = min(a, b)
    large = max(a, b)
    r = large % small
    if r != 0:
        return ab_gcd(r, small)
    else:
        return small


for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            gcd1 = ab_gcd(i, j)
            gcd2 = ab_gcd(j, k)
            gcd3 = ab_gcd(gcd1, gcd2)
            if i == j == k:
                total += gcd3
            elif i == j and j != k:
                total += gcd3 * 3
            elif i != j and j == k:
                total += gcd3 * 3
            else:
                total += gcd3 * 6

print(total)


### FIXED CODE ###

import math
from functools import reduce

K = int(input())
total = 0


def gcd_list(*numbers):
    return reduce(math.gcd, numbers)


for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            s = [i, j, k]
            if i == j == k:
                total += gcd_list(*s)
            elif i == j and j != k:
                total += gcd_list(*s) * 3
            elif i != j and j == k:
                total += gcd_list(*s) * 3
            else:
                total += gcd_list(*s) * 6

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

S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

for i in range(len(S)):
    lists[int(S[i:]) % 2019] += 1

for i in range(2019):
    if lists[i] >= 2:
        ans += (lists[i] * (lists[i] - 1)) // 2

print(ans)


### FIXED CODE ###

S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

num = 0
for i in range(len(S) - 1, -1, -1):
    num += pow(10, len(S) - 1 - i, 2019) * int(S[i])
    lists[num % 2019] += 1

for i in range(2019):
    if lists[i] >= 2:
        ans += (lists[i] * (lists[i] - 1)) // 2

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

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n+1) for i in range(n+1)]
A = []
for i in range(n):
    A.append([a[i], i])
A.sort(reverse=True)
for i in range(1, n+1):
    for j in range(i+1):
        if j == 0:
            dp[j][i-j] = dp[j][i-j-1] + A[i-1][0] * abs(n-i-A[i-1][1])
        elif j == i:
            dp[j][i-j] = dp[j-1][i-j] + A[i-1][0] * abs(A[i-1][1]-i+1)
        else:
            dp[j][i-j] = max(dp[j][i-j-1] + A[i-1][0] * abs(n-i+j-A[i-1][1]), dp[j-1][i-j] + A[i-1][0] * abs(A[i-1][1]-j+1))
ans = 0
for i in range(n+1):
    ans = max(ans, dp[i][n-i])
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n+1) for i in range(n+1)]
A = []
for i in range(n):
    A.append([a[i], i])
A.sort(reverse=True)
for i in range(1, n+1):
    for j in range(i+1):
        if j == 0:
            dp[j][i-j] = dp[j][i-j-1] + A[i-1][0] * abs(n-i-A[i-1][1])
        elif j == i:
            dp[j][i-j] = dp[j-1][i-j] + A[i-1][0] * abs(A[i-1][1]-i+1)
        else:
            dp[j][i-j] = max(dp[j][i-j-1] + A[i-1][0] * abs(n-i+j-A[i-1][1]), dp[j-1][i-j] + A[i-1][0] * abs(A[i-1][1]-j+1))
ans = 0
for i in range(n+1):
    ans = max(ans, dp[i][n-i])
print(ans)
### BUGGY CODE ###

H, W, M = map(int, input().split())

Hc = [0 for i in range(H)]
Wc = [0 for i in range(W)]
HW = [[0 for i in range(W)] for i in range(H)]

for m in range(M):
  h, w = map(int, input().split())
  Hc[h - 1] += 1
  Wc[w - 1] += 1
  HW[h - 1][w - 1] = 1
Hcmax = max(Hc)
Hcmax_idx = [i for i, x in enumerate(Hc) if x == Hcmax] 
Wcmax = max(Wc)
Wcmax_idx = [i for i, x in enumerate(Wc) if x == Wcmax] 

ans = 0
for i in Hcmax_idx:
  for j in Wcmax_idx:
    if HW[i][j] == 1:
      t = Hcmax + Wcmax - 1
    else:
      t = Hcmax + Wcmax
    ans = max(ans, t)
print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())

Hc = [0 for i in range(H)]
Wc = [0 for i in range(W)]
B = []

for m in range(M):
  h, w = map(int, input().split())
  Hc[h - 1] += 1
  Wc[w - 1] += 1
  B.append((h - 1, w - 1))
Hcmax = max(Hc)
Hcmax_idx = [i for i, x in enumerate(Hc) if x == Hcmax] 
Wcmax = max(Wc)
Wcmax_idx = [i for i, x in enumerate(Wc) if x == Wcmax] 

ans = Hcmax + Wcmax - 1
B = set(B)
f = False
for i in Hcmax_idx:
  if f:
    break
  for j in Wcmax_idx:
    if (i, j) not in B:
      ans = Hcmax + Wcmax
      f = True
      break
print(ans)
### BUGGY CODE ###

def word_break(s, words):
    ok = [True]
    for i in range(1, len(s)+1):
        ok += any(ok[j] and s[j:i] in words for j in range(i)),
    return ok[-1]


s = input()
words = ["eraser", "erase", "dreamer", "dream"]
print("YES" if word_break(s, words) else "NO")

### FIXED CODE ###

s = input()

while s:
    if s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "erase":
        s = s[5:]
    elif s[:5] == "dream":
        if s[5:8] == "era":
            s = s[5:]
        elif s[5:7] == "er":
            s = s[7:]
        else:
            s = s[5:]
    else:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

N,M,K = map(int, input().split())
A = map(int, input().split())
B = map(int, input().split())

sa = {0: 0}
for i, val in enumerate(A):
  sa[i+1] = sa[i] + val

sb = {0: 0}
for i, val in enumerate(B):
  sb[i+1] = sb[i] + val

max_num = 0

for i in range(N+1):
  if(sa[i]>K):
    break
  for j in range(M+1):
    if(sb[M-j]<=K-sa[i]):
      break
  max_num = max(max_num,i+M-j)

      
      
print(max_num)

### FIXED CODE ###

N,M,K = map(int, input().split())
A = map(int, input().split())
B = map(int, input().split())

sa = [0]
for i, val in enumerate(A):
  sa.append(sa[i] + val)

sb = [0]
for i, val in enumerate(B):
  sb.append(sb[i] + val)

max_num = 0
ind_max = M
for i in range(N+1):
  if(sa[i]>K):
    break
  c = 0
  for k in range(ind_max+1):
    if(sb[ind_max-k]<=K-sa[i]):
      break
    c += 1
  ind_max -= c
  max_num = max(max_num,i+ind_max)

      
      
print(max_num)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
cnt = 0
if A[0]>1:
    cnt += A[0]-1
    A[0]=1
cur = 1
for i in range(1,N):
    if A[i]<=cur:continue
    if A[i]==cur+1:
        cur += 1
        continue
    a = A[i]
    while True:
        if a-(cur+1)>cur+1:
            a -= (cur+1)
            cnt += 1
        elif a-(cur+1)<=cur+1:
            a -= (a-1)
            cnt += 1
            break
print(cnt)    


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
cnt = 0
if A[0]>1:
    cnt += A[0]-1
    A[0]=1
cur = 1
for i in range(1,N):
    if A[i]<=cur:continue
    if A[i]==cur+1:
        cur += 1
        continue
    a = A[i]
    n = (a-cur-2)//(cur+1)
    cnt += (n+1)
print(cnt)
### BUGGY CODE ###

n,m=list(map(int, input().split()))
a=list(map(int,input().split()))
for _ in range(m):
  a.sort()
  a[n-1] //= 2
print(sum(a))

### FIXED CODE ###

n,m=list(map(int, input().split()))
a=list(map(int, input().split()))
a.sort(reverse=True)
while m>0:
  a[0] //= 2
  m = m - 1
  for i in range(n-1):
    if a[0] < a[i+1] and m > 0:
      a[i+1] //= 2
      m = m - 1
    else:
      a.sort(reverse=True)
      break
print(sum(a))
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
N, K, L = map(int, input().split())
road = UnionFind(N)
train = UnionFind(N)
ans = []
for i in range(K):
    p, q = map(int, input().split())
    road.union(p-1, q-1)
for i in range(L):
    r, s = map(int, input().split())
    train.union(r-1, s-1)
for i in range(N):
    ans.append(len(set(road.members(i)) & set(train.members(i))))
print(*ans)

### FIXED CODE ###

import collections
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
N, K, L = map(int, input().split())
road = UnionFind(N)
train = UnionFind(N)
pair = []
ans = []
for i in range(K):
    p, q = map(int, input().split())
    road.union(p-1, q-1)
for i in range(L):
    r, s = map(int, input().split())
    train.union(r-1, s-1)
for i in range(N):
    pair.append((road.find(i), train.find(i)))
c = collections.Counter(pair)
for i in range(N):
    ans.append(c[(road.find(i), train.find(i))])
print(*ans)
### BUGGY CODE ###

H, W, K = map(int, input().split())

S = [input() for _ in range(H)]

def calc(L):
    M = len(L)
    cnt = [0] * M
    ret = 0

    for w in range(W):
        for i, (t, b) in enumerate(zip(L, L[1:])):
            for j in range(t, b):
                if S[j][w] == '1':
                    cnt[i] += 1
        if max(cnt) > K:
            cnt = [0] * M
            for i, (t, b) in enumerate(zip(L, L[1:])):
                for j in range(t, b):
                    if S[j][w] == '1':
                        cnt[i] += 1
            ret += 1

    return ret

ans = H * W
for mask in range(1 << (H - 1)):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]
    ans = min(ans, len(L) - 2 + calc(L))
print(ans)



### FIXED CODE ###

H, W, K = map(int, input().split())

S = [list(map(int, input())) for _ in range(H)]
accS = [[0] * (W + 1) for _ in range(H + 1)]

for h in range(H):
    for w in range(W):
        accS[h + 1][w + 1] = accS[h + 1][w] + accS[h][w + 1] - accS[h][w] + S[h][w]

def isOk(L, left, right):
    for top, bot in zip(L, L[1:]):
        if accS[bot][right] - accS[bot][left] - accS[top][right] + accS[top][left] > K:
            return False
    return True

ans = 10**18

for mask in range(1 << H):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]

    cnt = len(L) - 2
    left = 0
    while left < W:
        if not isOk(L, left, left + 1):
            cnt = 10**18
            break

        right = left + 1
        while right < W and isOk(L, left, right + 1):
            right += 1

        cnt += 1
        left = right

    ans = min(ans, cnt - 1)

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

R, C, K = map(int, input().split())
dp = [[[0 for j in range(C+1)] for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]

for i in range(K):
    r, c, v = map(int, input().split())
    D[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])

        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]

ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)

### FIXED CODE ###

R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])

        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]

ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)
### BUGGY CODE ###

n,p= map(int,input().split())
res=1
if n==1:
    res=p
else:
    for i in range(2,int(p**(1/n))+2):
        if i**n>p:
            break
        if p%(i**n)==0:
            res=i
print(res)

### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
### BUGGY CODE ###

s=input()
n=len(s)
dp=[13*[0]for _ in range(n)]
if s[0]=="?":dp[0]=10*[1]+[0]*3
else:dp[0][int(s[0])]+=1
for i in range(1,n):
  if s[i]!="?":
    for j in range(13):
      dp[i][(j*10+int(s[i]))%13]=dp[i-1][j]
  else:
    for j in range(13):
      for k in range(10):
        dp[i][(j*10+k)%13]+=dp[i-1][j]
  for j in range(13):dp[i][j]%=10**9+7
print(dp[-1][5])

### FIXED CODE ###

s=input()
n=len(s)
dp=[13*[0]for _ in range(n)]
if s[0]=="?":dp[0]=10*[1]+[0]*3
else:dp[0][int(s[0])]+=1
for i in range(1,n):
  if s[i]!="?":
    for j in range(13):
      dp[i][(j*10+int(s[i]))%13]=dp[i-1][j]
  else:
    for j in range(13):
      for k in range(10):
        dp[i][(j*10+k)%13]+=dp[i-1][j]
  for j in range(13):dp[i][j]%=10**9+7
print(dp[-1][5])
### BUGGY CODE ###

a=int(input())
b=list(map(int,input().split()))
ans=0
for i in range(a):
  for j in range(a):
    if b[i]%b[j]==0 and not i==j:
      ans+=1
      break
print(a-ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))
### BUGGY CODE ###

n=int(input(''))
s=input('')
s=s.split(' ')
p=1
f=0
for a in range(n):
    s[a]=int(s[a])
    p=p*s[a]

if p>10**18:
    f=1

if f==1:
    print(-1)
else:
    print(p)

### FIXED CODE ###

n=int(input(''))
s=input('')
s=s.split(' ')
p=1
f=0
t=0

for a in range(n):
    s[a]=int(s[a])

for b in s:
    if b==0:
        t=1

if t==1:
    print(0)
else:
    for a in range(n):
        p=p*s[a]

        if p>10**18:
            f=1
            break


    if f==1:
        print(-1)
    else:
        print(p)