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

import sys
from itertools import product

import numpy as np

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = np.zeros(shape=(H, W), dtype=np.uint8)
    for i in range(H):
        S[i] = list(map(int, input().rstrip()))

    ans = float("inf")
    for comb in product(range(2), repeat=H-1):
        n_cut = sum(comb)
        M = 1 + n_cut

        # horizontal chocolates
        h_chocos = np.zeros(shape=(M, W), dtype=np.uint16)
        h = 0  # upper index
        m = 0
        for i, c in enumerate(comb):
            if c == 1:
                h_chocos[m] = np.sum(S[h:i+1, :], axis=0)
                h = i + 1
                m += 1
        h_chocos[m] = np.sum(S[h:, :], axis=0)

        total = np.zeros(shape=M, dtype=np.uint16)
        for w in range(W):
            total += h_chocos[:, w]
            if not np.all(total <= K):
                n_cut += 1
                total = h_chocos[:, w]
        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


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

# -*- coding: utf-8 -*-

def abc158d(s_init, n, query):
    ans = s_init
    for i in range(n):
        tgt = query[i]
        if tgt[0] == "1":
            ans = ans[::-1]
        elif tgt[0] == "2":
            if tgt[1] == "1":
                ans = tgt[2] + ans
            elif tgt[1] == "2":
                ans = ans + tgt[2]
            else:
                print("invalid query!!:" + str(tgt[0]) + str(tgt[1]))
        else:
            print("invalid query!!:" + str(tgt[0]))

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    s_init = input()
    n = int(input())
    query = []
    for i in range(n):
        query.append(input().split(" "))
    
    accomplishment = abc158d(s_init, n, query)
    
    # output
    print(accomplishment)
# else:
    # do nothing


### FIXED CODE ###

# -*- coding: utf-8 -*-

def abc158d(s_init, n, query):
    head = ""
    tail = ""
    reverse = 0
    for i in range(n):
        tgt = query[i]
        if tgt[0] == "1":
            reverse = (reverse + 1) % 2
        elif tgt[0] == "2":
            if tgt[1] == "1":
                if reverse == 0:
                    head += tgt[2]
                else:
                    tail += tgt[2]
            elif tgt[1] == "2":
                if reverse == 0:
                    tail += tgt[2]
                else:
                    head += tgt[2]
            else:
                print("invalid query!!:" + str(tgt[0]) + str(tgt[1]))
        else:
            print("invalid query!!:" + str(tgt[0]))
    if reverse == 0:
        return head[::-1] + s_init + tail
    else:
        return tail[::-1] + s_init[::-1] + head

###
# main
if(__name__ == '__main__'):
    # input
    s_init = input()
    n = int(input())
    query = []
    for i in range(n):
        query.append(input().split(" "))
    
    accomplishment = abc158d(s_init, n, query)
    
    # output
    print(accomplishment)
# else:
    # do nothing
### BUGGY CODE ###

import collections
import math
from functools import lru_cache

@lru_cache(maxsize = 64)
def C(n, r):
    if n-r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
d = {}
sm = 0
for k,v in c.most_common():
    d.update({k:v})
    sm += C(v,2)

for a in A:
    print (sm - C(d.get(a),2) + C(d.get(a)-1,2) )


### FIXED CODE ###

import collections
import math

def C(n):
    if n-2 < 0:
        return 0
    return n * (n-1) // 2
N = int(input())
A = list(map(int,input().split()))
c = collections.Counter(A)
#d = {}
d = [-1]*200010
Cf = [C(i) for i in range(200010)]
sm = 0
for k,v in c.most_common():

    d[k] = v
    sm += C(v)

for a in A:
    print (sm - Cf[d[a]] + Cf[d[a]-1])
### BUGGY CODE ###

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

from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])

ans=0
for i in range(n):
    ans+=lcm//a[i]

print(ans%(10**9+7))


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
 
ans=0
for i in range(n):
    ans+=lcm//a[i]
 
print(ans%(10**9+7))
### BUGGY CODE ###

s = input()
q = int(input())

rev = 0
for _ in range(q):
    query = list(input().split())
    if query[0] == "1":
        rev = 1 if rev == 0 else 0
    else:
        if query[1] == "1":
            if rev == 0:
                s = query[2] + s
            else:
                s = s + query[2]
        else:
            if rev == 0:
                s = s + query[2]
            else:
                s = query[2] + s
if rev == 1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

rev = False
for _ in range(q):
    query = list(input().split())
    t = query[0]
    if t == "1":
        rev = not rev
    else:
        f = int(query[1])
        c = query[2]
        if rev:
            f = 3 - f
        if f == 1:
            s.appendleft(c)
        else:
            s.append(c)
if rev:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)
    hurui = [1] * len(A)
    prev = 0
    for i, a in enumerate(A):
        if a == prev:
            hurui[i-1] = 0
            hurui[i] = 0
            prev = a
            continue
        if i == len(A)-1:
            prev = a
            continue
        if hurui[i] == 0:
            prev = a
            continue
        for j, b in enumerate(A[i+1:]):
            if hurui[i+1+j]==0:
                prev = a
                continue
            if b % a == 0:
                hurui[i+1+j] = 0
            prev = a
    print(sum(hurui))



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    ma = A[-1]
    hurui = [0] * (ma + 10)
    for a in A:
        if hurui[a] == 0:
            hurui[a] = 1
        else:
            hurui[a] = 10

    for a in A:
        if hurui[a] == 0:
            continue

        for i in range(a*2, ma+10, a):
            hurui[i] = 0

    print(hurui.count(1))



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

n, m = (int(i) for i in input().split())
py = [[int(i) for i in input().split()] for j in range(m)]
pre = {}
for i in range(m):
    cur_p = py[i][0]
    curlist = pre.get(cur_p,[])
    curlist.append([py[i][1],i])
    curlist.sort()
    pre[cur_p] = curlist

city_nums = []
for i in range(m):
    p = py[i][0]
    x = 0
    p_list = pre[p]
    for j in range(len(p_list)):
        if p_list[j][1] == i:
            x = j+1
    ans = "{:0>6d}".format(p)+"{:0>6d}".format(x)
    city_nums.append(ans)
    
for c_n in city_nums:
    print(c_n)

### FIXED CODE ###

n, m = (int(i) for i in input().split())
py = [[int(i) for i in input().split()] for j in range(m)]
pre = {}
for i in range(m):
    cur_p = py[i][0]
    cur_p_cities = pre.get(cur_p,[])
    cur_p_cities.append(i)
    pre[cur_p] = cur_p_cities

for i in pre.keys():
    pre[i].sort(key=lambda x:py[x][1])
    city_order = tuple(range(1,len(pre[i])+1))
    pre[i] = dict(zip(pre[i],city_order))

city_nums = []
for i in range(m):
    p = py[i][0]
    x = pre[py[i][0]][i]
    ans = "{:0>6d}".format(p)+"{:0>6d}".format(x)
    city_nums.append(ans)
    
for c_n in city_nums:
    print(c_n)
### BUGGY CODE ###

import itertools
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
b=[]
for i in a:
	ma=i[0] + i[1]
	mi=i[0] - i[1]
	c=[mi,ma]
	b.append(c)


while True:
	count=[]
	for i in range(n):
		count.append(0)
	p=0
	d=list(itertools.combinations(range(n), 2))
	for i in d:
		p+=1
		if b[i[0]][0]<b[i[1]][0]<b[i[0]][1] or b[i[0]][0]<b[i[1]][1]<b[i[0]][1]:
			count[i[0]]+=1
			count[i[1]]+=1
	del b[count.index(max(count))]
	n-=1
	if sum(count)==0:
		break
print(len(count))

### FIXED CODE ###

N=int(input())
xl=[]
for i in range(N):
  x,l=map(int,input().split())
  xl.append([x-l,x+l])

XL=sorted(xl,key=lambda x:x[1])

w=1
robot=XL[0]
for i in XL:
  if robot[1] <= i[0]:
    w+=1
    robot=i
print(w)
### BUGGY CODE ###

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

check = True
zero = False

for i in a:
    ans = ans*i

    if i==0:
        zero = True

    if ans>1000000000000000000:
        check = False




if zero:
    print(0)
else:
    if check:
        print(ans)
    else:
        print(-1)

### FIXED CODE ###

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

check = True
zero = False

for i in range(0,n):
    if a[i]==0:
        zero = True
        break;




for i in range(0,n):
    ans = ans*a[i]

    if ans>1000000000000000000:
        check = False
        break;




if zero:
    print(0)
else:
    if check:
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split(' ')))
count_dict = {}
for A in A_list:
  strA = str(A)
  if strA in count_dict.keys():
    count_dict[strA] += 1
  else:
    count_dict[strA] = 1
#print(count_dict)

sum_ = 0
for count in count_dict.values():
  sum_ += (count**2 - count) // 2

for A in A_list:
  num = count_dict[str(A)]
  ans = sum_ - (num**2-num)//2 + (num**2-3*num+2)//2
  print(ans)

### FIXED CODE ###

import collections

N = int(input())
A_list = list(map(int, input().split(' ')))
count_dict = collections.Counter(A_list)

sum_ = 0
for count in count_dict.values():
  sum_ += (count**2 - count) // 2

for A in A_list:
  print(sum_ - count_dict[A] + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    A.sort(key=lambda x: x[0])
#    print(A)
    dp = [[float("inf")]*N for _ in range(M+1)]
    dp[0][0] = 0
    for i, (s, t, c) in enumerate(A):
        for j in range(N+1):
            if j-1 < s or j-1 >= t:
                dp[i+1][j-1] = dp[i][j-1]
                if j-1 >= t and dp[i+1][j-1] == float("inf"):
                    break
            else:
                dp[i+1][j-1] = min(dp[i][j-1], dp[i][s-1] + c)
    ans = dp[M][N-1]
#    for x in dp:
#        print(x)
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, E):
    inf = float('inf')
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    heapq.heapify(q)
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, E)

    ans = A[N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


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

N,A,B=list(map(int,input().split()))
l=[]
for i in range(N):
    for j in range(A):
        l.append('r')
        if len(l) >= N:
            print(l.count(('r')))
            exit()
    for k in range(B):
        l.append('b')
        if len(l) >= N:
            print(l.count(('r')))
            exit()

print(l.count(('r')))



### FIXED CODE ###

N,A,B=list(map(int,input().split()))
a=N//(A+B)
b=N%(A+B)
if A == 0:
    print(0)
    exit()

if b > A:
    print(a*A+A)
    exit()

print(a*A+b)
### BUGGY CODE ###

#C - Sum of gcd of Tuples (Easy)
K = int(input())
DP =[]
ans = 0
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)


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


for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            a = gcd_list([i, j, k])
            DP.append(a)

for l in range(len(DP)):
    ans += DP[l]
print(ans)

### FIXED CODE ###

#C - Sum of gcd of Tuples (Easy)
K = int(input())
DP =[]
ans = 0
import math
# from functools import reduce
# def gcd(*numbers):
#     return reduce(math.gcd, numbers)


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

for i in range(1, K + 1):
    for j in range(1, K + 1):
        a = math.gcd(i,j)
        for k in range(1,K+1):
            b = math.gcd(a,k)
            ans += b

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

from collections import Counter

n = int(input())

def primes(x):
   is_prime = [True] * (x+1)
   is_prime[0] = False
   is_prime[1] = False
   for i in range(2, int(x**0.5)+1):
      if not is_prime[i]:
         continue
      for j in range(i*2, x+1, i):
         is_prime[j] = False
   return [i for i in range(x+1) if is_prime[i]]

pl = primes(int(n**0.5)+1)

def factorization(x):
   arr = []
   tmp = x
   while x > 1:
      for i in pl:
         if x % i == 0:
            x /= i
            arr.append(i)
            break
      if x == tmp and len(arr) == 0:
         return [x]
   return arr

ans = 0
for k, v in Counter(factorization(n)).items():
   i = 0
   while v > i:
      i += 1
      v -= i
      ans += 1
print(ans)


### FIXED CODE ###

n = int(input())

from collections import Counter

factors = []
i = 2
while n > 1:
   if n < i * i:
      factors.append(n)
      break
   while n % i == 0:
      factors.append(i)
      n //= i
   i += 1

ans = 0
for cnt in Counter(factors).values():
   i = 1
   while cnt >= i:
      cnt -= i
      i += 1
      ans += 1
print(ans)
### BUGGY CODE ###

x = int(input())
item_num = x // 100

def brute(t):
    for i in range(t+1):
        for j in range(t+1-i):
            for k in range(t+1-i-j):
                for l in range(t+1-i-j-k):
                    for m in range(t+1-i-j-k-l):
                            n = t - i - j -k - l - m
                            total = i + j + k + l + m + n
                            if total == t and (100 * i + 101 * j + 102 * k +  103 * l + 104 * m + 105 * n ) == x:
                                return 1
    return 0

print(brute(item_num))


### FIXED CODE ###

x = int(input())

num = x // 100



dp = ["?"] * (x+1)
dp[0] = "1"

for i in range(1,x+1):
    if i <= 99:
        dp[i] = "0"
    elif i in (100,101,102,103,104,105):
        dp[i] = "1"
    else:
        if "1" in(dp[i-100],dp[i-101],dp[i-102],dp[i-103],dp[i-104],dp[i-105]):
            dp[i] = "1"
        else:
            dp[i] = "0"

            
print(dp[x])
### BUGGY CODE ###

mod = 1000000000+7

def product(N, As):
  result = 0
  for i in range(N):
    left = As[i]
    rights = As[i+1:]
    result += sum(list(map(lambda x: x*left, rights)))
  return result % mod


if __name__ == "__main__":
  N = list(map(int, input().split()))
  As = list(map(int, input().split()))
  print(product(N[0], As))

### FIXED CODE ###

mod = 1000000000+7

def product(N, As):
  result = 0
  summer = sum(As)
  for i in range(N-1):
    left = As[i]
    summer = summer - left
    result += left * summer
    
  return result % mod


if __name__ == "__main__":
  N = list(map(int, input().split()))
  As = list(map(int, input().split()))
  print(product(N[0], As))
### BUGGY CODE ###

N = int(input())
n = round(N**0.5)
answer = 0
for num in range(n,N+1):
  if N%num==0:
    a = num
    b = int(N/num)
    answer = a+b-2
    break
print(answer)

### FIXED CODE ###

N = int(input())
n = round(N**0.5)
a = 0
b = 0
for i in range(n):
    if N%(n-i)==0:
        a = n-i
        b = int(N/a)
        break
print(a+b-2)
### BUGGY CODE ###

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

n=int(input())
s=input()
l=[0]*1000
for _ in range(n):
    i=s[_]
    for j in range(1000):
        k=str(j).zfill(3)
        if k[0]==i:
            if l[j]==2:
                l[j]=3
        if k[1]==i:
            if l[j]==1:
                l[j]=2
        if k[2]==i:
            if l[j]==0:
                l[j]=1
ans=0
for i in l:
    if i==3:
        ans+=1
print(ans)

### FIXED CODE ###

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

n=int(input())
s=input()
l=[0]*1000
for _ in range(n):
    i=s[_]
    for j in range(1000):
        k=str(j).zfill(3)
        if k[0]==i:
            if l[j]==2:
                l[j]=3
        if k[1]==i:
            if l[j]==1:
                l[j]=2
        if k[2]==i:
            if l[j]==0:
                l[j]=1
ans=0
for i in l:
    if i==3:
        ans+=1
print(ans)
### BUGGY CODE ###

L, R = map(int, input().split())
mod = 2018
i = L
for i in range(L, R):
    for j in range(i+1, R+1):
        num = (i*j) % 2019
        mod = min(mod, num)
        if mod == 0:
            break
print(mod)

### FIXED CODE ###

L, R = map(int, input().split())
mod = 2018
i = L
if R-L >= 2019:
    mod = 0
else:
    for i in range(L, R):
        for j in range(i+1, R+1):
            num = (i*j) % 2019
            mod = min(mod, num)
            if mod == 0:
                break
print(mod)
### BUGGY CODE ###

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

side = []
for i in range(W):
    side.append({"cost":int(input()),"num":i,"dir":0})
for i in range(H):
    side.append({"cost":int(input()),"num":i,"dir":1})
side = sorted(side,key = lambda x:x["cost"])

node =[[{"v":j,"men":[j]} for j in range(i*(W+1),(i+1)*(W+1))]for i in range(H+1)]
ans = 0
for s in side:
    cost,num,di = s["cost"],s["num"],s["dir"]
    if di == 0 :
        for i in range(H+1):
            if node[i][num]["v"] != node[i][num+1]["v"]: # 親が違ったら
                # print(i,num,0)
                ans += cost
                v1 = node[i][num]["v"]
                v2 = node[i][num+1]["v"]
                
                for j in node[v2//(W+1)][v2%(W+1)]["men"]: # v2とつながった要素の親を書き換え
                    node[j//(W+1)][j%(W+1)]["v"] = v1
                node[v1//(W+1)][v1%(W+1)]["men"] += node[v2//(W+1)][v2%(W+1)]["men"]
    else:
        for i in range(W+1):
            if node[num][i]["v"] != node[num+1][i]["v"]: # 親が違ったら
                # print(num,i,1)
                ans += cost
                v1 = node[num][i]["v"]
                v2 = node[num+1][i]["v"]
                
                for j in node[v2//(W+1)][v2%(W+1)]["men"]: # v2とつながった要素の親を書き換え
                    node[j//(W+1)][j%(W+1)]["v"] = v1
                node[v1//(W+1)][v1%(W+1)]["men"] += node[v2//(W+1)][v2%(W+1)]["men"]
print(ans)



### FIXED CODE ###

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

side = [{"cost":int(input()), "di":0}for i in range(W)] + [{"cost":int(input()), "di":1}for i in range(H)]
side = sorted(side, key=lambda x:x["cost"])
ans = 0
ty = [H+1,W+1]
for s in side:
    cost, di = s["cost"], s["di"]
    ans += ty[di] * cost
    ty[(di+1)%2] -= 1
print(ans)
### BUGGY CODE ###

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

dp = [float('inf')] * N
dp[0] = 0
for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j > N - 1:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])

### FIXED CODE ###

n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]
cost = [0] * n
cost[1] = abs(h[1] - h[0])
for i in range(1, n):
  cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
print(cost[n - 1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 31 21:01:36 2020

@author: 81807
"""


n = int(input())
a = list(map(int, input().split()))
q = 1
for i in a:
    q *= i
if q > 10**18:
    print(-1)
else:
    print(q)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
n = int(input())
a = list(map(int, input().split()))
a.sort()
q = 1
f = 0
for i in a:
    q *= i
    if q > 10**18:
        f = 1
        break
if f == 1:
    print(-1)
else:
    print(q)