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

# h*wのマスにかかれているそれぞれの数字の位置は関係ないしどうでもいい
# それぞれの数がどれだけあるかに興味がある
# iから1に至る最小値を全探索 間に合うのか？ まあいけるやろ
h, w = map(int, input().split())
table = []
for _ in range(10):
    table.append(list(map(int, input().split())))

wall = {}
for _ in range(h):
    x = list(map(int, input().split()))
    for v in x:
        if v not in wall:
            wall[v] = 1
        else:
            wall[v] += 1


def rec(idx, cost, used):
    if idx == 1:
        return cost
    ret = 10 ** 10
    for i in range(10):
        if i in used:
            continue
        next_used = used[:]
        next_used.append(i)
        ret = min(ret, rec(i, cost + table[idx][i], next_used))
    return ret


arr = [0 for _ in range(10)]
for i in range(10):
    if i == 1:
        continue
    arr[i] = rec(i, 0, [i])

ans = 0
for k, v in wall.items():
    if k != -1 and k != 1:
        ans += arr[k] * v
print(ans)


### FIXED CODE ###

# h*wのマスにかかれているそれぞれの数字の位置は関係ないしどうでもいい
# それぞれの数がどれだけあるかに興味がある
# iから1に至る最小値を全探索 間に合うのか？ まあいけるやろ
h, w = map(int, input().split())
table = []
for _ in range(10):
    table.append(list(map(int, input().split())))

wall = {}
for _ in range(h):
    x = list(map(int, input().split()))
    for v in x:
        if v not in wall:
            wall[v] = 1
        else:
            wall[v] += 1


def rec(idx, cost, used):
    if idx == 1:
        return cost
    ret = 10 ** 10
    for i in range(10):
        if i in used:
            continue
        next_used = used[:]
        next_used.append(i)
        ret = min(ret, rec(i, cost + table[idx][i], next_used))
    return ret


arr = [0 for _ in range(10)]
for i in range(10):
    if i == 1:
        continue
    arr[i] = rec(i, 0, [i])

ans = 0
for k, v in wall.items():
    if k != -1 and k != 1:
        ans += arr[k] * v
print(ans)
### BUGGY CODE ###

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

import fractions
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def lcm_base(x, y):
    return ((x * y) // fractions.gcd(x, y))


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


min_AB = lcm(*A)

ans = 0
for a in A:
    ans += min_AB // a

print(ans % mod)


### FIXED CODE ###

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

import fractions
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7


def lcm_base(x, y):
    return ((x * y) // fractions.gcd(x, y))


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


min_AB = lcm(*A)

ans = 0
for a in A:
    ans += min_AB // a

print(ans % mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(1,n+1):
    ans.append(a.index(i)+1)
print (*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
t = []
for i in range(1,n+1):
    t.append((a[i-1],i))
t = sorted(t)
arr = []
for k in range(n):
    arr.append(t[k][1])
print(*arr)
### BUGGY CODE ###

N = int(input())
V = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
m = 0
for p in range(2**N):
  value = 0
  for i in range(N):
    if ((p>>i) & 1):
      value = value + V[i] - C[i]
  if value > m:
    m = value
print(m)

### FIXED CODE ###

N = int(input())
V = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
m = 0
for i in range(N):
  if (V[i]-C[i]) > 0:
    m = m + V[i]-C[i]
print(m)
### BUGGY CODE ###

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
for i in range(h):
    road = input()
    road_map.append(road)

queue = [[ch-1,cw-1,0]]
used_map = [[-1]*w for _ in range(h)]

while queue != []:
    dot = queue.pop()
    if dot[0] < 0 or dot[1] < 0 or dot[0] >= h or dot[1] >= w:
        continue
    if used_map[dot[0]][dot[1]] > -1 and used_map[dot[0]][dot[1]] <= dot[2]:
        continue
    if road_map[dot[0]][dot[1]] == "#":
        continue
    used_map[dot[0]][dot[1]] = dot[2]

    queue.append([dot[0],dot[1]-1,dot[2]])
    queue.append([dot[0],dot[1]+1,dot[2]])
    queue.append([dot[0]+1,dot[1],dot[2]])
    queue.append([dot[0]+1,dot[1],dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            queue.append([dot[0]+x,dot[1]+y,dot[2]+1])
    
print(used_map[dh-1][dw-1])

### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

n = int(input())
mod = (10 ** 9) + 7

def calc(l, ans):
    if len(l) == n:
        for al in ["AGC", "GAC", "ACG", "AGGC", "ATGC", "ACGC", "AGTC", "AGAC", "AGGC"]:
            if al in l:
                return ans
        return ans + 1
    for alphabet in "AGCT":
        ll = l + alphabet
        for al in ["AGC", "GAC", "ACG", "AGGC", "ATGC", "ACGC", "AGTC", "AGAC", "AGGC"]:
            if al in l:
                return ans
        ans = calc(ll, ans)
    return ans

print(calc("", 0) % mod)

### FIXED CODE ###

import copy

def ok(len_4):    
    for i in range(3):
        alpha = list(copy.deepcopy(len_4))
        alpha[i], alpha[i + 1] = alpha[i + 1], alpha[i]
        if "AGC" in "".join(alpha):
            return False
    if "AGC"in len_4:
        return False
    return True


def check(len_3, n):
    if n == N:
        return 1
    if len_3 in memo[n]:
        return memo[n][len_3]
    ret = 0
    for alpha in "AGCT":
        t = len_3 + alpha
        if ok(t):
            temp = check(t[1:], n + 1)
            memo[n + 1][t[1:]] = temp % mod
            ret += temp % mod
    return ret % mod


mod = (10 ** 9) + 7
N = int(input())
memo = [{} for _ in range(N + 1)]
ans = check("TTT", 0)
print(ans)
### BUGGY CODE ###

import sys
results = {}
def fact(n):
    if n in results:
        return results[n]
    ret = [1]
    if n%2==0:
        ret.append(2)
        results[n]=ret
        return ret
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:
            ret.append(i)
            results[n]=ret
            return ret
    results[n]=ret
    return ret
prime_results = {}
def isPrime(n):
    if n in prime_results:
        return prime_results[n]
    if n<=1:
        return False
    if n==2:
        return True
    if fact(n)==[1]:
        prime_results[n]=True
        return True
    else:
        prime_results[n]=False
        return False
lines = sys.stdin.readlines()
for line in lines:
    inp = int(line)
    s=0
    for i in range(2,inp+1):
        if isPrime(i):
            s+=1
    print (s)

### FIXED CODE ###

import sys

def primeTable(n):
    list = [True for _ in range(n+1)]
    i = 2
    while i * i <= n:
        if list[i]:
            j = i+i
            while j<= n:
                list[j] = False
                j += i
        i += 1

    table = [i for i in range(n+1) if list[i] and i >= 2]
    return table

lines = sys.stdin.readlines()
primeList = primeTable(999999)

for line in lines:
    inp = int(line)
    primes = list(filter(lambda n:n>=2 and n<=inp, primeList))
    num = len(primes)
    print (num)
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
sortedX = sorted(X)

for x in X:
    if sortedX.index(x) <= N//2 -1:
        print(sortedX[N//2])
    else:
        print(sortedX[N//2 -1])

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
sortedX = sorted(X)

for x in X:
    if sortedX[N//2 -1] >= x:
        print(sortedX[N//2])
    else:
        print(sortedX[N//2 -1])
### BUGGY CODE ###

N=int(input())
h_list=[int(x) for x in input().split()]

flag=True

for j in range(1,len(h_list)):
    for i in range(len(h_list)-j):
        tmp=h_list[i:i+1+j]
        if tmp[0]-tmp[j]>=2:
            flag=False
            break
    
if flag:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N=int(input())
h_list=[int(x) for x in input().split()]

flag=True

m=h_list[0]
for j in range(len(h_list)-1):
    if m<h_list[j]:
        m=h_list[j]
    if m-h_list[j+1]>=2:
        flag=False
        break        
    
if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

ans = []
for i in range(1,n+1):
    tmp = a.index(i)
    ans.append(tmp+1)
    
ans = [str(x) for x in ans]
print(" ".join(ans))
    

### FIXED CODE ###

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

ans = [0 for _ in range(n)]

for i in range(n):
    ans[a[i] - 1] = i + 1
print(*ans)
### BUGGY CODE ###

N = int(input())

sum = 0

while N:
  a = N%10
  sum += a
  N = N//10

if sum%9==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

def digitSum(n):
    s = str(n)
    array = list(map(int, s))
    return sum(array)

N = int(input())

sum = digitSum(N)

if sum%9==0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
P = [int(x) for x in input().split()]

count = 0
l = []
for i in range(len(P)):
	l.append(P[i])
	if min(l) == P[i]:
		count += 1

print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
P = [int(x) for x in input().split()]

l = []
for x in P:
	if not l or l[-1] > x:
		l.append(x)
	else:
		l.append(l[-1])

print(len(set(l)))
### BUGGY CODE ###

N = input()
S = list(input())

turns_num_list = list()

for i in range(len(S)):

  left = S[: i].count("W")
  right = S[i+1: ].count("E")

  turns_num_list.append(left+right)

print(min(turns_num_list))


### FIXED CODE ###

N = input()
S = list(input())

length = len(S)
min_num = 300000
left = 0
right = S.count("E")

for i in range(length):

  if i > 0:
    left += int(S[i - 1] == "W")

  if i < length:
    right -= int(S[i] == "E")

  if left + right < min_num:
    min_num = left + right

print(min_num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from heapq import *
def min_cost_flow_dijkstra(E, s, t, f):
    NN = 2 * N + 6
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    h = [0] * NN
    res = 0
    while f > 0:
        dist = [1<<100] * NN
        dist[s] = 0
        q = []
        heappush(q, (0, s))
        while q:
            di, v = q.pop()
            if dist[v] < di: continue
            for i, (b, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[b] > dist[v] + c + h[v] - h[b]:
                    dist[b] = dist[v] + c + h[v] - h[b]
                    prevv[b] = v
                    preve[b] = i
                    heappush(q, (dist[b], b))
        
        
        if dist[t] == 1<<100:
            return -1
        for v in range(NN):
            h[v] += dist[v]
        
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * h[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
N = int(input())
su = 0
INF = 1 << 31
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + INF))
    E.append((i, 2*N+1, cnt, x - y + INF))
    E.append((i, 2*N+2, cnt, - x + y + INF))
    E.append((i, 2*N+3, cnt, - x - y + INF))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + INF))
    E.append((2*N+1, i+N, cnt, - x + y + INF))
    E.append((2*N+2, i+N, cnt, x - y + INF))
    E.append((2*N+3, i+N, cnt, x + y + INF))

print(su * INF * 2 - min_cost_flow_dijkstra(E, 2*N+4, 2*N+5, su))

### FIXED CODE ###

from networkx import*
N = int(input())
G = MultiDiGraph()
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(i, demand = -c)
    G.add_weighted_edges_from([(i, -1, x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -2, x - y)], capacity = c)
    G.add_weighted_edges_from([(i, -3, -x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -4, -x - y)], capacity = c)
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(N + i, demand = c)
    G.add_weighted_edges_from([(-1, N + i, -x - y)], capacity = c)
    G.add_weighted_edges_from([(-2, N + i, -x + y)], capacity = c)
    G.add_weighted_edges_from([(-3, N + i, x - y)], capacity = c)
    G.add_weighted_edges_from([(-4, N + i, x + y)], capacity = c)

print(-min_cost_flow_cost(G))
### BUGGY CODE ###

N, Q = map(int, input().split())
data = input()
for i in range(Q):
  l, r = map(int, input().split())
  print(data[l-1:r].count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
data = input()
result = [0] * N
for i in range(N-1):
  if data[i] == "A" and data[i+1] == "C":
    result[i+1] = result[i] + 1
  else:
    result[i+1] = result[i]

for i in range(Q):
  l, r = map(int, input().split())
  print(result[r-1]-result[l-1])
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
A=[0]*N
B=[]
count=0
for i in range(N//2,N):
    if a[i]==1:
        A[i]=1
        B.append(i+1)
for i in range(N//2)[::-1]:
    asum=0 
    x=i+1
    for j in range(i,N,x):
        asum=asum+A[j]
    if asum%2!=a[i]:
        A[i]=1
        B.insert(0,i+1)
count=sum(A)
print(count)
if count!=0:
    print(*B)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
A=[0]*N
B=[]
for i in range(N//2,N):
    if a[i]==1:
        A[i]=1
        B.append(i+1)
for i in range(N//2)[::-1]:
    asum=0 
    x=i+1
    for j in range(i,N,x):
        asum=asum+A[j]
    if asum%2!=a[i]:
        A[i]=1
        B.append(i+1)
count=sum(A)
print(count)
if count!=0:
    print(*B)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
c=0
for i in range(len(A)-1):
  m=max(A[0:i+1])
  if m>A[i+1]:
    d=m-A[i+1]
    c+=d
print(c)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
c=0
m=A[0]
for i in range(len(A)-1):
  if m<A[i+1]:
    m=A[i+1]
  if m>A[i+1]:
    d=m-A[i+1]
    c+=d
print(c)
### BUGGY CODE ###

N=int(input())
equal=0
ans=0
s=[list(input()) for _ in range(N)]
s10 = [i for i in range(10)]
i=0
t=['x' for i in range(N)]
for i in range(N):
    s10 = [x for x in range(10)]
    ti = [['xx',0] for x in range(10)]
    for j in range(10):
        if j in s10:
            ti[j][0]=s[i][j]
            ti[j][1]=1
            for k in range(j+1,10):
                if s[i][j]==s[i][k]:
                    ti[j][1]=ti[j][1]+1
                    s10.remove(k)
                else:
                    pass

        else:
            pass
        j=j+1
    ti = [[ti[a][0],ti[a][1]] for a in range(10) if not ti[a][1]==0]
    t[i] =ti
    i+=1
for i in range(N):
    for j in range(i+1,N):
        equal=0
        if len(t[i])==len(t[j]):
            for k1 in range(len(t[i])):
                for k2 in range(len(t[i])):
                    if t[i][k1]==t[j][k2]:
                        equal+=1
        if equal==len(t[i]):
            ans+=1
print(ans)

### FIXED CODE ###

from operator import mul
from functools import reduce
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N=int(input())
t=tuple([''.join(sorted(list(input()))) for _ in range(N)])
Dic = {}
ans = 0
for i in range(N):
    if t[i] in Dic:
        Dic[t[i]]+=1
    else:
        Dic[t[i]]=1
for k in tuple(Dic.keys()):
    if Dic[k]==1:
        pass
    else:
        ans+=cmb(Dic[k], 2)
print(int(ans))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input()[:-1])
    a = [list(map(int, input().split())) for _ in range(n)]
    j = [0] * n
    all_g = n * (n - 1) // 2
    g = 0
    d = 0
    while 1:
        d += 1
        finish = set()
        for i in range(n):
            if i in finish: continue
            if j[i] == n-1: continue
            ii = a[i][j[i]] - 1
            if a[ii][j[ii]] - 1 == i:
                g += 1
                finish.add(ii)
                finish.add(i)
        if g == all_g:
            print(d)
            break
        if not finish:
            print(-1)
            break
        for ii in finish:
            j[ii]+=1

main()


### FIXED CODE ###

# YouTube1

def main():
    n = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(n)]
    #    print(a)
    gam = []  # １日のgames
    # 初期化
    for i in range(n):
        ii = a[i][-1]
        if ii < i: continue
        if a[ii][-1] == i:
            gam.append([i, ii])
    days = 0
    fin = [False] * n
    fin_cnt = 0
    #    print(gam)
    while 1:
        days += 1
        pla = []  # 今日試合があったplayers
        for i, ii in gam:
            a[i].pop()
            a[ii].pop()
            pla.append(i)
            pla.append(ii)
        gam = []
        dec = set()
        for i in pla:
            if fin[i]: continue
            if not a[i]:
                fin[i] = True
                fin_cnt += 1
                if fin_cnt == n:
                    print(days)
                    exit()
                continue
            if i in dec: continue
            ii = a[i][-1]
            if a[ii][-1] == i:
                gam.append([i, ii])
                dec.add(ii)
        if not gam:
            print(-1)
            exit()

main()
### BUGGY CODE ###

n = int(input())
a_int = list(map(int, input().split()))
squ = 0
num = 10 ** 9 + 7
for i in range(0, n-1):
    for j in range(i+1, n):
        squ += (a_int[i] % num) * a_int[j]
ans = squ % num
print(ans)

### FIXED CODE ###

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

squ = 0
num = 10 ** 9 + 7

a_sum = 0
for i_sum in range(1, n):
    a_sum += a_int[i_sum]

for i in range(0, n-1):
    squ += a_int[i] * a_sum
    a_sum -= a_int[i+1]

ans = squ % num
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    S = input()
    T = input()
    m = len(S)
    n = len(T)
    dp = [[-INF] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = 0
    prev = [[None] * (n + 1) for _ in range(m + 1)]
    prev[0][0] = (-1, -1, '')

    for i in range(m):
        dp[i + 1][0] = 0
        prev[i + 1][0] = (i, 0, '')
    for j in range(n):
        dp[0][j + 1] = 0
        prev[0][j + 1] = (0, j, '')

    for i in range(m):
        for j in range(n):
            if dp[i + 1][j + 1] < dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i][j + 1]
                prev[i + 1][j + 1] = (i, j + 1, '')
            if dp[i + 1][j + 1] < dp[i + 1][j]:
                dp[i + 1][j + 1] = dp[i + 1][j]
                prev[i + 1][j + 1] = (i + 1, j , '')
            if S[i] == T[j] and dp[i + 1][j + 1] < dp[i][j] + 1:
                dp[i + 1][j + 1] = dp[i][j] + 1
                prev[i + 1][j + 1] = (i, j, S[i])

    i, j = m, n
    res = []
    while (i, j) != (0, 0):
        i, j, c = prev[i][j]
        res.append(c)

    print(''.join(res[::-1]))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    S = input()
    T = input()
    m = len(S)
    n = len(T)
    dp = [[-INF] * (n + 1) for _ in range(m + 1)]
    prev = [[(-1, -1)] * (n + 1) for _ in range(m + 1)]

    for i in range(m):
        dp[i][0] = 0
    for j in range(n):
        dp[0][j] = 0

    for i in range(m):
        for j in range(n):
            if S[i] == T[j]:
                if dp[i + 1][j + 1] < dp[i][j] + 1:
                    dp[i + 1][j + 1] = dp[i][j] + 1
                    prev[i + 1][j + 1] = (i, j)
            else:
                if dp[i + 1][j + 1] < dp[i + 1][j]:
                    dp[i + 1][j + 1] = dp[i + 1][j]
                    prev[i + 1][j + 1] = (i + 1, j)
                if dp[i + 1][j + 1] < dp[i][j + 1]:
                    dp[i + 1][j + 1] = dp[i][j + 1]
                    prev[i + 1][j + 1] = (i, j + 1)

    i, j = m, n
    res = []
    cnt = 0
    while 1:
        pi, pj = prev[i][j]
        if (pi, pj) == (-1, -1):
            break
        if i - pi == 1 and j - pj == 1:
            res.append(S[pi])
        i, j = pi, pj

    print(''.join(reversed(res)))
resolve()
### BUGGY CODE ###

n, m = map(int, input().split())

a, b = [0] * n, [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

ans = 0
while m > 0:
    minl = float("inf")
    for i in range(n):
        if minl > a[i] and b[i] != 0:
            minl = a[i]
    for i in range(n):
        if minl == a[i]:
            ans += min(a[i] * m, a[i] * b[i])
            m = max(m - b[i], 0)
            b[i] = 0
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
k=[list(map(int,list(input().split()))) for i in range(n)]


ans = 0
k.sort()
for i in range(n):
    ml = min(k[i][1],m)
    ans += k[i][0] * ml
    m -= k[i][1]
    if m <= 0:
        break
print(ans)
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
def median(L):
    #L = sorted(L)
    n = len(L)
    m = int(n/2)
    if n % 2 == 0:
        return (L[m - 1] + L[m]) / 2
    else:
        return L[(n - 1) // 2]
x_sort = sorted(x)
for i in range(n):
    b = x_sort.copy()
    b.remove(x[i])
    print(median(b))

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
def median(L):
    L = sorted(L)
    n = len(L)
    m = int(n/2)
    if n % 2 == 0:
        return (L[m - 1] + L[m]) / 2
    else:
        return L[(n - 1) // 2]
x_median = median(x)
l = median(sorted(x)[:-1])
r = median(sorted(x)[1:])
for i in range(n):
    if x[i] > x_median:
        print(l)
    else:
        print(r)
### BUGGY CODE ###

import sys
input  = sys.stdin.readline
 
N,K = map(int,input().split())
hn = list(map(int,input().split()))
rtn = [10**12]*N
K = min(N,K)
if N==K:
  print(abs(hn[0]-hn[N-1]))
else:
  rtn[0]=0
  for i in range(1,N,1):
    sj=min(i,K)
    rtn[i]=min([rtn[i-j]+abs(hn[i]-hn[i-j]) for j in range(sj,0,-1)])
  print(rtn[N-1])

### FIXED CODE ###

n,k=map(int,input().split())
H=list(map(int,input().split()))
 
dp=[float('inf') for _ in range(n)]
dp[0]=0
for i,hi in enumerate(H[1:],1):
  s=max(0,i-k)
  dp[i]=min([aj + abs(hi-hj) for hj,aj in zip(H[s:i],dp[s:i])])
print(dp[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
if 1 in a:
    a.remove(1)
ans = 1

for i in range(len(a)):
    ans *= a[i]
if ans <= 10 ** 18:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if 1 in a:
    a.remove(1)
ans = 1

if 0 in a:
    print(0)
else:
    for i in range(len(a)):
        if ans <= 10 ** 18:
            ans *= a[i]
    if ans <= 10 ** 18:
        print(ans)
    else:
        print(-1)