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

from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


h,n=mp()
magic=[lmp() for i in range(n)]
dp=[float("inf")]*(h+1)
dp[0]=0
for i in range(h):
    for k in range(n):
        ni=min(i+magic[k][0],h)
        dp[ni]=min(dp[ni],dp[i]+magic[k][1])
print(dp[-1])

### FIXED CODE ###

from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


h,n=mp()
magic=[lmp() for i in range(n)]
dp=[float("inf")]*(h+1)
dp[0]=0
for i in range(h):
    for k in range(n):
        ni=min(i+magic[k][0],h)
        dp[ni]=min(dp[ni],dp[i]+magic[k][1])
print(dp[-1])
### BUGGY CODE ###

from collections import defaultdict

H, W, M = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(M)]

dh, dw = defaultdict(int), defaultdict(int)
used = set()

for h, w in l:
    dh[h] += 1
    dw[w] += 1
    used.add((h, w))

ih = sorted(dh.items(), key=lambda x:-x[1])
iw = sorted(dw.items(), key=lambda x:-x[1])

def get(x, y):
    h, counth = ih[x]
    w, countw = iw[y]
    ans = counth + countw
    if (h, w) in used:
        ans -= 1
    return ans

ans = get(0, 0)
for h in range(len(ih)):
    for w in range(len(iw)):
        b = get(h, w)
        if abs(b-ans)>1:
            break
        ans = max(ans, b)
print(ans)


### FIXED CODE ###

from collections import Counter


def solve():
    H, W, M = map(int, input().split())
    dh, dw = Counter(), Counter()
    used = set()

    for _ in range(M):
        h, w = map(int, input().split())
        dh[h] += 1
        dw[w] += 1
        used.add((h, w))

    ih = dh.most_common()
    iw = dw.most_common()

    h, counth = ih[0]
    w, countw = iw[0]

    s = counth + countw
    ans = counth + countw - ((h, w) in used)

    for h, counth in ih:
        for w, countw in iw:
            if counth+countw < s or ans == s:
                break
            b = counth + countw - ((h, w) in used)
            ans = max(ans, b)
    print(ans)


solve()
### BUGGY CODE ###

import math

n = 10**5+10

x = int(input())

nums = [1 for i in range(n)]

for i in range(2, n):
  if nums[i] == 0:
    continue
  if (i>=x):
    print(i)
    exit()
  for j in range(i+1, n):
    if j%i==0:
      nums[j] = 0


### FIXED CODE ###

import math

x = int(input())

def is_prime(n):
  for i in range(2, int(math.sqrt(n))):
    if(n%i==0):
      return False
  return True

for i in range(x, x+100):
  if is_prime(i):
    print(i)
    exit()
### BUGGY CODE ###

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

a.sort()
a_set = set(a)
for i in range(n-1):
    if a[i] == a[i + 1]:
        if a[i] in a_set:
            a_set.remove(a[i])

dp = [True for _ in range(max(a) + 1)]
ans = 0
y = -1
for x in a:
    if x == y:
        continue
    y = x

    if x in a_set:
        ans += 1 if dp[x] else 0

    while y <= max(a):
        dp[y] = False
        y += x

print(ans)


### FIXED CODE ###

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

a.sort()
a_set = set(a)
for i in range(n-1):
    if a[i] == a[i + 1]:
        if a[i] in a_set:
            a_set.remove(a[i])

ma = max(a)

dp = [True for _ in range(ma + 1)]
ans = 0
y = -1
for x in a:
    if x == y:
        continue
    y = x

    if x in a_set:
        ans += 1 if dp[x] else 0

    while y <= ma:
        dp[y] = False
        y += x

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

import itertools

N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
P = [[i for i in range(1, M+1)] for _ in range(N)]

# print(R)
for comb in itertools.product(*P):
    flag = True
    p = comb[0]
    for i in comb:
        if i < p:
            flag = False
            break
        p = i

    if not flag:
        continue

    # print(comb)

    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if comb[b-1] - comb[a-1] == c:
            temp += d
    if temp >= ans:
        ans = temp

print(ans)


### FIXED CODE ###

import itertools

N, M, Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(Q)]

# 重複組み合わせ: nHr = n+r-1Cr を考える
ans = 0
R = [i for i in range(1, M+1)]
# print(R)

for comb in itertools.combinations_with_replacement(R, N):
    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if comb[b-1] - comb[a-1] == c:
            temp += d
    if temp >= ans:
        ans = temp

    # print("comb: {}, temp: {}, ans: {}".format(comb, temp, ans))

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

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

########

N = i_inpl()
A = l_inpl()

ans = []
tmp = 0
for i, Ai in enumerate(A[:N-1]):
    tmp += Ai *(-1)**(i)
a1 = (tmp+A[N-1])
ans.append(a1)
t_ans = []
for i in range(N-1):
    ans.append(2*A[::-1][i]-ans[i])
ans = [ans[0]] + ans[1:][::-1]
print(" ".join([ str(i) for i in ans]))

# L, R = l_inpl()
# L %= 2019
# R %= 2019

# if R<=L:
#     R+=2019

# ans = INF
# for i in range(L, R+1):
#     for j in range(i+1, R+1):
#         print(i, j)
#         ans = min(ans, i*j%2019)

# print(ans)


### FIXED CODE ###

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

########

N = i_inpl()
A = l_inpl()

ans = []
tmp = 0
for i, Ai in enumerate(A[:N-1]):
    tmp += Ai *(-1)**(i)
a1 = (tmp+A[N-1])
ans.append(a1)
t_ans = []
r_A = A[::-1]
for i in range(N-1):
    ans.append(2*r_A[i]-ans[i])
ans = [ans[0]] + ans[1:][::-1]
print(" ".join([ str(i) for i in ans]))

# L, R = l_inpl()
# L %= 2019
# R %= 2019

# if R<=L:
#     R+=2019

# ans = INF
# for i in range(L, R+1):
#     for j in range(i+1, R+1):
#         print(i, j)
#         ans = min(ans, i*j%2019)

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

n = int(input())
s_list = []
count = 0
for i in range(n):
    s = input()
    
    if not s in s_list:
        s_list.append(s)
        count += 1

print(count)

### FIXED CODE ###

n = int(input())

dic = {}

for i in range(n):
    s = input()
    dic[s] = dic.get(s, 0) + 1

print(len(dic.keys()))
### BUGGY CODE ###

N = int(input())
a =[int(n) for n in input().split()]

product = 1

for i in range(N):
    product *= a[i]

if product > 10 ** 18:
    print('-1')
else:
    print(product)

### FIXED CODE ###

N = int(input())
a =[int(n) for n in input().split()]

product = 1
if 0 in a:
    print(0)
else:
    for i in range(N):
        product *= a[i]
        if product > 10 ** 18:
            print('-1')
            break
    if product <= 10 ** 18:
        print(product)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m1 = max(a)
if len(set(a)) == 1:
	for i in range(n):
		print(m1)
else:
	m2 = sorted(set(a))[-2]
	for i in range(n):
		if a[i] < m1:
			print(m1)
		elif a[i] == m1:
			if a.count(m1) > 1:
				print(m1)
			else:
				print(m2)
		else:
			print(m2)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m1 = max(a)
c = a.count(m1)
if len(set(a)) == 1:
	for i in range(n):
		print(m1)
else:
	m2 = sorted(set(a))[-2]
	for i in range(n):
		if a[i] < m1:
			print(m1)
		elif a[i] == m1:
			if c > 1:
				print(m1)
			else:
				print(m2)
		else:
			print(m2)
### BUGGY CODE ###

import sys

def main():
    n = int(input())
    limit = pow(10,18)
    readStr = input()
    flds = readStr.split(" ")
    res = 1
    for i in range(n):
        if flds[i] == 0:
            res = 0
            break
        res *= int(flds[i])

    if res > limit:
        res = -1
    print(res)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def main():
  N = int(input())
  P = sys.stdin.readline().rstrip().split()
  if '0' in P:
    print(0)
    return
  ans = 1
  for a in P:
    ans *= int(a)
    if ans > 1000000000000000000:
      print(-1)
      return
  print(ans)

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

import sys
input = sys.stdin.readline
n = int(input())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
# a = [list(map(int, input().split())) ]
ans = 0
flag = True
while True:
    tmp = 0
    for j in range(n):
        if not a[j]:
            tmp += 1
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
    if tmp == n:
        print(ans)
        break
    for j in range(n):
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
    if flag:
        print(-1)
        break
    else:
        ans += 1


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j].pop(0)
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
### BUGGY CODE ###

from numpy import abs
from copy import deepcopy
import numpy as np
N = int(input())
A = list(map(int,input().split()))
dist = []

for i in range(N):
  A_cancelled = deepcopy(A)
  A_cancelled.pop(i)
  
  A_cancelled.append(0)
  A_cancelled.insert(0,0)
  
  from_arr = np.array(A_cancelled[:-1])
  to_arr = np.array(A_cancelled[1:])
  
  dist.append(sum(abs(from_arr - to_arr)))
  
for i in dist:
  print(i)

### FIXED CODE ###

N=int(input())
A=[0]+list(map(int,input().split()))+[0]
cost=sum(abs(A[i+1]-A[i]) for i in range(N+1))
for i in range(1,N+1):
    print(cost-abs(A[i+1]-A[i])-abs(A[i]-A[i-1])+abs(A[i+1]-A[i-1]))
### BUGGY CODE ###

s = input()
n = len(s)
i = 0
while i < n-1:
    if s[i] == "S" and s[i+1] == "T":
        s = s[:i] + s[i+2:]
        i = 0
        n -= 2
    else:
        i += 1

print(n)


### FIXED CODE ###

s = input()
y = [0]
z = []
for t in s:
    if t == "S":
        y.append(t)
    elif y[-1] == "S":
        del y[-1]
    else:
        z.append(t)

print(len(y) + len(z) - 1)
### BUGGY CODE ###

n = int(input())
 
def bellman_ford(s):
	d = [float('inf')]*n # 各頂点への最小コスト
	d[s] = 0 # 自身への距離は0
	for i in range(n):
		update = False # 更新が行われたか
		for x, y, z in g:
			if d[y] > d[x] + z:
				d[y] = d[x] + z
				update = True
		if not update:
 			break
		# 負閉路が存在
		if i == n-1:
			return -1
	return d

g = []
for _ in range(n-1):
	a,b,c = map(int,input().split())
	g.append([a-1,b-1,c])
	g.append([b-1,a-1,c])

q,k = map(int,input().split())
for i in range(q):
	x,y = map(int,input().split())
	print(bellman_ford(x-1)[k-1] + bellman_ford(k-1)[y-1])

### FIXED CODE ###

import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])
### BUGGY CODE ###

import sys
from heapq import *
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, 1, x))
        key.append((r, -1, x))

    key.sort()
    judge = []
    now = set()
    already = dict()
    
    index = 0
    ans = -1
    for i in range(q):
        d = int(input())
        for i in range(index, 2*n):
            s, j, x = key[i]
            if s > d:
                index = i
                break
            if j == 1:
                heappush(judge, x)
                now = now.union({x})
            else:
                now.discard(x)
                if x in already:
                    already[x] += 1
                else:
                    already[x] = 1
                    
                    
        while judge:
            if judge[0] in already and already[judge[0]] > 0:
                already[judge[0]] -= 1
                heappop(judge)
            else:
                break
        if judge:
            ans = judge[0]
        else:
            ans = -1      
            
        print(ans)

    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from heapq import *
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, 1, x))
        key.append((r, -1, x))
    
    for i in range(q):
        d = int(input())
        key.append((d, 2))

    key.sort()
    judge = []
    already = dict()
    
    for i in range(2*n+q):
        k = key[i]
        if k[1] == -1:
            if k[2] in already:
                already[k[2]] += 1
            else:
                already[k[2]] = 1
        elif k[1] == 1:
            heappush(judge, k[2])
        else:
            while judge:
                if judge[0] in already and already[judge[0]] > 0:
                    already[judge[0]] -= 1
                    heappop(judge)
                else:
                    break
            if judge:
                print(judge[0])
            else:
                print(-1)
    

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

# -*- coding: utf-8 -*-
n,k=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
p=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
max = 0
final = []
#最大のリストを選定
for i in range(0,n-k+1):
    ck = sum(p[i:i+k])
    if ck > max:
        max = ck

#計算
print((max+k)/2.0)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,k=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
p=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
#最大のリストを選定
before_pi = p[0]
before_sum = sum(p[0:k])+ 0.0
suml = [sum(p[0:k])]
for i in range(1,n-k+1):
    before_sum = before_sum - before_pi+p[i+k-1]
    suml.append(before_sum)
    before_pi = p[i]

#計算
print((max(suml)+k)/2.0)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = [i for i in input()]
questions = [[i-1 for i in map(int,input().split())] for j in range(Q)]
for i in range(len(S)-1):
  if S[i]=='A' and S[i+1]=='C':
    S[i]='a'
    
for q in questions:
  part_S = S[q[0]:q[1]+1]
  ans = part_S.count('a')
  if part_S[-1]=='a':
    ans -= 1
  print(ans)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
questions = [[i for i in map(int,input().split())] for j in range(Q)]
t = [0]*(N+1)
for i in range(N):
  t[i+1] = t[i] + (1 if S[i:i+2]=='AC' else 0)  

for q in questions:
  print(t[q[1]-1] - t[q[0]-1])
### BUGGY CODE ###

import numpy as np
n,W=map(int,input().split())
w,v=[],[]
for i in range(n):
    wi,vi=map(int,input().split())
    w.append(wi)
    v.append(vi)

dp=np.zeros((n+1, W+1), dtype=np.int64)

for i in range(n):
    for j in range(W+1):
        if w[i]>j:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j], dp[i][j-w[i]]+v[i])
#print(dp)
print(dp[n][W])

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for _ in range(N)])

dp = np.zeros(W+1, dtype=np.int64)

for w, v in wv:
    dp[w:] = np.maximum(dp[w:], dp[:W-w+1]+v)

ans = dp[W]
print(ans)
### BUGGY CODE ###

def get_lcs_table(s1, s2):
    l1, l2 = len(s1)+1, len(s2)+1
    dp = [[0]*l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            dp[i][j] = 0 if i==0 or j==0 else dp[i-1][j-1]+1 if s1[i-1]==s2[j-1] else max(dp[i][j-1], dp[i-1][j])
    return dp


def restore_lcs(s1, s2, dp):
    x, y = len(s1), len(s2)
    l = []
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            l.append(s1[x])
    return "".join(l[::-1])


if __name__ == "__main__":
    s = input()
    t = input()
    dp = get_lcs_table(s, t)
    print(restore_lcs(s, t, dp))


### FIXED CODE ###

def get_lcs_table(s1, s2):
    l1, l2 = len(s1)+1, len(s2)+1
    dp = [[0]*l2 for _ in range(l1)]
    for i in range(l1):
        for j in range(l2):
            dp[i][j] = 0 if i==0 or j==0 else dp[i-1][j-1]+1 if s1[i-1]==s2[j-1] else max(dp[i][j-1], dp[i-1][j])
    return dp


def restore_lcs(s1, s2, dp):
    x, y = len(s1), len(s2)
    l = []
    while x and y:
        if dp[x][y] == dp[x-1][y]:
            x -= 1
        elif dp[x][y] == dp[x][y-1]:
            y -= 1
        else:
            x -= 1
            y -= 1
            l.append(s1[x])
    return "".join(l[::-1])


if __name__ == "__main__":
    s = input()
    t = input()
    dp = get_lcs_table(s, t)
    print(restore_lcs(s, t, dp))
### BUGGY CODE ###

import numpy as np

H, W = [int(item) for item in input().split()]

grid = np.array([[item for item in input()] for _ in range(H)])
dp = np.zeros((H, W), dtype='int32')

dp[0,0] = 1

for i in range(H):
    for j in range(W):
        if grid[i, j] == '.' and i > 0 and j > 0:
            dp[i, j] = (dp[i-1, j] + dp[i, j-1]) % (10**9 +7)
        elif grid[i, j] == '.' and i == 0 and j > 0:
            dp[i, j] = dp[i, j - 1] 
        elif grid[i, j] == '.' and j == 0 and i > 0:
            dp[i, j] = dp[i-1, j]

# print(dp)
print(dp[H-1,W-1])

### FIXED CODE ###

H, W = [int(item) for item in input().split()]
grid = [[item for item in input()] for _ in range(H)]

dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
max_num = 10**9 +7

def main():
    dp[0][1] = 1

    for i in range(H):
        for j in range(W):
            if grid[i][j] != '#':
                dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j]) % max_num
            

    # print(dp)
    print(dp[H][W])

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

from collections import deque

class UnionFind:
    def __init__(self, n):
        self.rank = [0]*n
        self.parent = [i for i in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            self.rank[y] += 1

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



n = int(input())
s = [input() for _ in range(n)]


uf = UnionFind(n)

INF = 1001001001
ans = 0

for min_i in range(n):
    dist = [INF] * n
    dist[min_i] = 0
    q = deque([(min_i, 0, -1)])

    while q:
        v, d, p = q.popleft()
        box = []
        for nv in range(n):
            if s[v][nv] == '1':
                if nv == p:
                    continue
                if uf.same(v, nv):
                    print(-1)
                    exit()
                if d + 1 < dist[nv]:
                    dist[nv] = d + 1
                    q.append((nv, d + 1, v))
                    box.append(nv)
        for i in range(len(box) - 1):
            uf.merge(box[i], box[i + 1])
    ans = max(ans, max(dist) + 1)

print(ans)


### FIXED CODE ###

from collections import deque

class UnionFind:
    def __init__(self, n):
        self.rank = [0]*n
        self.parent = [i for i in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            self.rank[y] += 1

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



n = int(input())
s = [input() for _ in range(n)]

min_i = 0
min_count = n + 1
for i in range(n):
    count = 0
    for j in range(n):
        if s[i][j]:
            count += 1
    if count < min_count:
        min_count = count
        min_i = i

uf = UnionFind(n)

INF = 1001001001
ans = 0

for min_i in range(n):
    dist = [INF] * n
    dist[min_i] = 0
    q = deque([(min_i, 0, -1)])

    while q:
        v, d, p = q.popleft()
        box = []
        for nv in range(n):
            if s[v][nv] == '1':
                if nv == p:
                    continue
                if uf.same(v, nv):
                    print(-1)
                    exit()
                if d + 1 < dist[nv]:
                    dist[nv] = d + 1
                    q.append((nv, d + 1, v))
                    box.append(nv)
        for i in range(len(box) - 1):
            uf.merge(box[i], box[i + 1])
    ans = max(ans, max(dist) + 1)

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

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=0
for i in range(n-k+1):
  b=0
  for j in range(i,i+k):
    b+=p[j]
  if b >c:
    c =b
print((c+k)/2)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
q=[0]
for i in range(0,n-k):
  q.append(q[-1]+p[i+k]-p[i])
b=q.index(max(q))
s=0
for i in range(b,b+k):
  s+=p[i]
print((s+k)/2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 1
for i in range(n):
    s *= a[i]

if s > 1e18:
    print("-1")
else:
    print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 1
if 0 in a:
    print("0")
else:
    for i in range(n):
        s *= a[i]
        if s > 1e18:
            print("-1")
            break
    else:
        print(s)