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

n = int(input())

for k in range(n):
    a = input()
    b = input()
    len_a, len_b = len(a), len(b)
    table = [[0] * (len_b +1) for i in range(len_a + 1)]
    
    for i in range(len_a):
        a_i = a[i]
        for j in range(len_b):
            if a_i == b[j]:
                table[i+1][j+1] = table[i][j] + 1
            else:
                table[i+1][j+1] = max(table[i][j+1],table[i+1][j])
    print(table[len_a][len_b])

### FIXED CODE ###

def Ics(X, Y):
    m = len(X)
    n = len(Y)
    c1 = [0] * (n + 1)
    for i in range(m):
        d = X[i]
        c2 = c1[:]
        for j in range(n):
            if (d == Y[j]):
                c1[j + 1] = c2[j] + 1
            elif (c1[j + 1] < c1[j]):
                c1[j + 1] = c1[j]
    return (c1[-1])
 
q = int(input().rstrip())
t = []
for i in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep = "\n")
### BUGGY CODE ###

n, x0, y0 = list(map(int, input().split()))

cards = [y0] + list(map(int, input().split()))
# yの手持ちはゲームに関与するため、リストに加えてしまう

xs = [[-1] * (n+1) for i in range(n+1)]
ys = [[-1] * (n+1) for i in range(n+1)] 
#xs[i][j] = xの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i<j)の最善スコア
#ys[i][j] = yの手番で、xがcards[j]を持ちyがcards[i]を持っているとき(i<j)の最善スコア

for i in range(n+1):
	xs[i][-1] = abs(cards[-1] - cards[i])
	ys[i][-1] = abs(cards[-1] - cards[i])

for j in range(n-1, -1, -1):

	# x[i][j] = max (y[j][j+1] , y[j][j+2] , ……, y[j][n] )
	for i in range(0, j):
		xs[i][j] = max(ys[j][j+1:n+1])

	for i in range(0, j):
		ys[i][j] = min(xs[j][j+1:n+1])

# print(max(xs[0][0], abs(cards[-1] - x0)) )

# print(xs)
# print(ys)
print(max(ys[0][1:]))	


### FIXED CODE ###

n, x0, y0 = list(map(int, input().split()))

cards = [y0] + list(map(int, input().split()))
# yの手持ちはゲームに関与するため、リストに加えてしまう

xs = [[-1] * (n+1) for i in range(n+1)]
ys = [[-1] * (n+1) for i in range(n+1)] 
#xs[i][j] = xの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i<j)の最善スコア
#ys[i][j] = yの手番で、xがcards[j]を持ちyがcards[i]を持っているとき(i<j)の最善スコア

for i in range(n+1):
	xs[i][-1] = abs(cards[-1] - cards[i])
	ys[i][-1] = abs(cards[-1] - cards[i])

for j in range(n-1, -1, -1):

	# x[i][j] = max (y[j][j+1] , y[j][j+2] , ……, y[j][n] )
	xs_temp = max(ys[j][j+1:n+1])
	ys_temp = min(xs[j][j+1:n+1])
	for i in range(0, j):
		xs[i][j] = xs_temp
		ys[i][j] = ys_temp

# print(xs)
# print(ys)
print(max(ys[0][1:]))
### BUGGY CODE ###

n = int(input())
cs = [[0] * (n + 1) for _ in range(n + 1)]
es = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    cs[a][b] = cs[b][a] = c
    es[a].append(b)
    es[b].append(a)
ds = [0] * (n + 1)


def bfs(cur, prev):
    ds[cur] = ds[prev] + cs[prev][cur]
    for e in es[cur]:
        if e != prev:
            bfs(e, cur)


q, k = map(int, input().split())
bfs(k, k)

for _ in range(q):
    x, y = map(int, input().split())
    print(ds[x] + ds[y])

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n = int(input())
ls = [list(map(int, input().split())) for _ in range(n - 1)]

es = [[] for _ in range(n + 1)]
for a, b, c in ls:
    es[a].append((b, c))
    es[b].append((a, c))
ds = [0] * (n + 1)


def dfs(cur, prev, c):
    ds[cur] = ds[prev] + c
    for e, c in es[cur]:
        if e != prev:
            dfs(e, cur, c)


q, k = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(q)]

dfs(k, k, 0)
for x, y in qs:
    print(ds[x] + ds[y])
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
r_max = N // R + 1
g_max = N // G + 1
ans = 0
for r in range(r_max):
    r_num = R * r
    for g in range(g_max):
        g_num = G * g
        b_num = N - r_num - g_num
        if b_num >= 0:
            if b_num % B == 0:
                ans += 1
                # print(r_num,g_num,b_num)
print(ans)


### FIXED CODE ###

R,G,B,N = map(int,input().split())
r_max = N // R + 1
g_max = N // G + 1
ans = 0
for r in range(r_max):
    r_num = R * r
    for g in range(g_max):
        g_num = G * g
        b_num = N - r_num - g_num
        if b_num >= 0:
            if b_num % B == 0:
                ans += 1
                # print(r_num,g_num,b_num)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M = map(int, input().split())
cards = [1] * N
for _ in range(M):
    l,r = map(int, input().split())
    for i in range(l-1):
        cards[i] = 0
    for i in range(r,N):
        cards[i] = 0
print(sum(cards))

### FIXED CODE ###

N,M = map(int, input().split())
l = 0
r = N
for m in range(M):
    L,R = map(int, input().split())
    if L > l:
        l = L
    if R < r:
        r = R
print(max(r-l+1,0))
### BUGGY CODE ###

import numpy as np

n=int(input())
a=np.array(list(map(int, input().split())))
q=int(input())
a_sum= np.sum(a)

for i in range(q):
  b,c=map(int, input().split())
  count=np.count_nonzero(a==b)
  a[a==b]=c
  a_sum += count*(c-b)
  print(a_sum)

### FIXED CODE ###

import collections

N=int(input())
A=list(map(int,input().split()))
X=collections.Counter(A)
Q=int(input())

ans=sum(A)
for i in range(Q):
  B,C=map(int,input().split())
  ans+=(C-B)*X[B]
  print(ans)
  X[C]+=X[B]
  X[B]=0
### BUGGY CODE ###

n = int(input())
s = input()

count = 0
for i in range(0,n-3):
  ii = s[i]
  for j in range(i+1, n-1):
    jj = s[j]
    for k in range(j+1,n):
      kk=s[k]
      if j-i != k-j:
        if ii != jj and jj != kk and kk!=ii:
          count = count + 1
print(count)


### FIXED CODE ###

n = int(input())
s = input()

count = 0
r=0
g=0
b=0
for i in range(0,n):
  if s[i] == 'R':
    r = r + 1
  if s[i]=='G':
    g = g+1
  if s[i]=='B':
    b = b+1
    
for i in range(0,n):
  ii = s[i]
  for j in range(i+1, n):
    jj = s[j]
    if ii==jj:
      continue
    if (2*j-i)<=(n-1):
      if ii!=s[2*j-i] and jj!=s[2*j-i]:
        count = count + 1
print(r*g*b-count)
### BUGGY CODE ###

import math

N = int(input())
S = input()

def Word(i, a, b):
    if S[i] != S[i + a] and S[i] != S[i + a + b] and S[i + a] != S[i + a + b]:
        return True
    else:
        return False

ans = 0
for i in range(0, N):
    for a in range(1, N - 1): #a=j-i
        for b in range(1, a): #b=k-j
            if a + b + i >= N:
                break
            if Word(i, a, b):
                ans += 1
            if Word(i, b, a):
                ans += 1

print(ans)

### FIXED CODE ###

import math

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

def Word(i, a, b):
    if S[i] != S[i + a] and S[i] != S[i + a + b] and S[i + a] != S[i + a + b]:
        return True
    else:
        return False

R = S.count("R")
G = S.count("G")
B = S.count("B")

ans = R * G * B
for i in range(0, N - 1):
    for a in range(1, math.ceil(N / 2)):
        if i + a * 2 >= N:
            break
        if S[i] != S[i + a] and S[i] != S[i + a * 2] and S[i + a] != S[i + a * 2]:
            ans -= 1

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

import collections
N = int(input())
A = list(map(str, input().split()))
for i in range(N):
    print(A.count(str(i+1)))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
L = collections.Counter(A)
for i in range(N):
    print(L[i+1])
### BUGGY CODE ###

n, c = map(int, input().split())
xv = [[int(x) for x in input().split()] for _ in range(n)]
n += 1
oa = [0] * n
ob = [0] * n
xv.insert(0, [0, 0])
maxcal = 0
for i in range(1,n):
    oa[i] = oa[i-1] + xv[i][1]
ob[n-1] = xv[i][1]
for i in reversed(range(0,n-1)):
    ob[i] = xv[i][1] + ob[i+1]
for i in range(n):
    for j in range(n):
        cal = oa[i]
        d = 0
        if i != j:
            cal += ob[j]
            d = xv[i][0] * 2 + (c - xv[j][0])
            d2 = xv[i][0] + (c - xv[j][0]) * 2
            d = min(d, d2)
        else:
            d = xv[i][0]
        if d < c:
            maxcal = max(maxcal, cal - d)
print(maxcal)


### FIXED CODE ###

n, c = map(int, input().split())
xv = [[int(x) for x in input().split()] for _ in range(n)]
xv.insert(0, [0, 0])
n += 1
oa = [0] * (n + 1)
ob = [0] * (n + 1)
maxr = [0] * (n + 1)
maxl = [0] * (n + 1)
for i in range(1, n):
    oa[i] = oa[i - 1] + xv[i][1]
    maxr[i] = max(maxr[i - 1], oa[i] - xv[i][0])
ob[n - 1] = xv[i][1]
for i in range(n - 1, -1, -1):
    ob[i] = xv[i][1] + ob[i + 1]
    maxl[i] = max(maxl[i + 1], ob[i] - (c - xv[i][0]))
cal1 = max(maxr[n-1], maxl[0])
cal2 = 0
cal3 = 0
for i in range(n):
    cal2 = max(cal2, oa[i] - 2 * xv[i][0] + maxl[i+1])
    cal3 = max(cal3, ob[i] - 2 * (c - xv[i][0]) + maxr[i-1])
print(max(cal1, cal2, cal3))
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
res = 0

for i in range(N):
    count = 0
    for j in range(i, N):
        if j == N-1:
            break
        elif H[j] >= H[j+1]:
            count += 1
        else:
            break
    if count > res:
        res = count

print(res)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
total = 0
max_total = 0

for i in range(N-1):
    if H[i] >= H[i+1]:
        total += 1
        max_total = max(total, max_total)
    else:
        total = 0

print(max_total)
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [0]*N
        for diff, i in a1:
            for j in reversed(range(min(i,ls))):
                if vis[j]: continue
                vis[j] = 1
                val += diff
                break

        for diff, i in a2:
            for j in range(max(i, ls), N):
                if vis[j]: continue
                vis[j] = 1
                val += diff
                break

        ans.append(val)

    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
sys.setrecursionlimit(1000000000)

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*(N+1)
        def root(x):
            if vis[x] == None: return x

            vis[x] = root(vis[x])
            return vis[x]
        def root(x):
            a = []
            while True:
                y = vis[x]
                if y == None:
                    break
                a.append(x)
                x = y
            for i in a:
                vis[i] = x
            return x

        for diff, i in a1:
            j = min(i, ls) - 1
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k < 0: continue
            val += diff
            vis[k] = k - 1


        for diff, i in a2:
            j, v2 = max(i, ls), [[-1]]
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k >= N: continue
            val += diff
            vis[k] = k + 1

        ans.append(val)

    print(*ans, sep="\n")



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

import itertools

N = int(input())
A = list(map(int, input().split()))

ans = 0

B = list(itertools.combinations(A,2))

for i in range(len(B)):
    ans += B[i][0] * B[i][1]

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

#print(B)
#print(len(B))
print(ans)

### FIXED CODE ###

MOD = 1000000007
 
N = int(input())
A = list(map(int, input().split())) 
 
ans = 0
s = sum(A)
 
for a in A:
    s -= a
    ans += (a * s)

ans %= MOD

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

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        a.append(c)
a.sort()
ans = sum(a[-n:])
print(ans)

### FIXED CODE ###

import collections
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
k = collections.Counter(a)
for _ in range(m):
    b, c = map(int, input().split())
    k[c] += b
ans = 0
count = 0
for key in list(reversed(sorted(list(k.keys())))):
    ans += (min(k[key], n - count)) * key
    count += min(k[key], n - count)
    if count == n:
        break
print(ans)
### BUGGY CODE ###

n = int(input())
ai = []
bi = []
ci = []
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

for i in range(0,n):
    cnt = 0
    for j in range(0,n):
        if a[i] >= b[j]:
            break
        cnt += 1
    ai.append(cnt)

for i in range(0,n):
    cnt = 0
    for j in range(0,n):
        if b[i] >= c[j]:
            break
        cnt += 1
    bi.append(cnt)

ans = 0
for i in range(0,n):
    if ai[i] > 0:
        for j in range(0,ai[i]):
            ans += bi[j]

print(ans)



### FIXED CODE ###

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

bmul = [0]*(n+1)
ci = 0

for bi in range(n):
    while ci != n and c[ci] <= b[bi]:
        ci += 1
    bmul[bi] = n-ci
for i in range(n):
    bmul[n-i-1] += bmul[n-i]
bi = 0
ai = 0
ret = 0
for ai in range(n):
    while bi != n and b[bi] <= a[ai]:
        bi += 1
    ret += bmul[bi]
print(ret)
### BUGGY CODE ###

# 全探索する

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())

P = [None] * N
for i in range(N):
  P[i] = list(map(int,readline().split()))

ans = 10 ** 18 * 4 + 1
for ix in range(N-1):
  for jx in range(ix,N):
    # X軸が決まる
    left = P[ix][0]
    right = P[jx][0]
    if left > right:
      left,right = right,left
    for iy in range(N-1):
      for jy in range(iy,N):
        up = P[iy][1]
        down = P[jy][1]
        if up < down:
          up,down = down,up
        d = abs(up - down) * abs(right - left)
        if d > ans:
          continue
        cnt = 0
        for i in range(N):
          if left <= P[i][0] <= right and down <= P[i][1] <= up:
            cnt += 1
        if cnt >= K:
          ans = d
print(ans)

### FIXED CODE ###

# 全探索する

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())

P = [None] * N
for i in range(N):
  P[i] = list(map(int,readline().split()))

ans = 10 ** 18 * 4 + 1
for ix in range(N-1):
  for jx in range(ix,N):
    # X軸が決まる
    left = P[ix][0]
    right = P[jx][0]
    if left > right:
      left,right = right,left
    for iy in range(N-1):
      for jy in range(iy,N):
        up = P[iy][1]
        down = P[jy][1]
        if up < down:
          up,down = down,up
        d = abs(up - down) * abs(right - left)
        if d > ans:
          continue
        cnt = 0
        for i in range(N):
          if left <= P[i][0] <= right and down <= P[i][1] <= up:
            cnt += 1
        if cnt >= K:
          ans = d
print(ans)
### BUGGY CODE ###

def get_gcd(numbers):
    """Helper function to get GCD of list of numbers."""
    import math
    from functools import reduce
    # gcd is associative
    return reduce(lambda x, y: math.gcd(x, y), numbers)


def sum_of_gcd_tuples():
    K = int(input())
    total = 0
    for a in range(1, K + 1):
        for b in range(1, K + 1):
            for c in range(1, K + 1):
                total += get_gcd([a, b, c])

    print(total)


sum_of_gcd_tuples()

### FIXED CODE ###

def sum_of_gcd_tuples():
    from math import gcd
    K = int(input())
    total = 0

    for a in range(1, K + 1):
        for b in range(1, K + 1):
            for c in range(1, K + 1):
                total += gcd(gcd(a, b), c)

    print(total)


sum_of_gcd_tuples()
### BUGGY CODE ###

#coding: utf-8
N = int(input())
L = list(map(int, input().split()))

cnt = 0
tri_cnt = 0
mem = 0

#全てが奇数になるまで実行し続ける
while(tri_cnt != len(L)):
    if(L[mem]%2 != 0):
        mem += 1
    else:
        L[mem] //= 2
        # for i in range(len(L)):
        #     if(i != mem):
        #         #L[i] = L[i] * 3
        #         print('',end='')
        cnt += 1

    tri_cnt = 0
    for i in range(len(L)):
        if (L[i] % 2 != 0):
            tri_cnt += 1
    # print(L)
    # print(tri_cnt)
else:
    print(cnt)

### FIXED CODE ###

#coding: utf-8
N = int(input())
L = list(map(int, input().split()))

cnt = 0
tri_cnt = 0
mem = 0

#全てが奇数になるまで実行し続ける
while(mem != len(L)):
    if(L[mem]%2 != 0):
        mem += 1
    else:
        L[mem] //= 2
        # for i in range(len(L)):
        #     if(i != mem):
        #         L[i] = L[i] * 3
        #         print('',end='')
        cnt += 1

    # tri_cnt = 0
    # for i in range(len(L)):
    #     if (L[i] % 2 != 0):
    #         tri_cnt += 1
else:
    print(cnt)
### BUGGY CODE ###

INF = 10 ** 9 + 7
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(N):
    for j in range(H):
        if dp[j] == INF: continue
        if j + ab[i][0] <= H:
            dp[j + ab[i][0]] = min(dp[j + ab[i][0]], dp[j] + ab[i][1])
        else:
            dp[H] = min(dp[H], dp[j] + ab[i][1])

print(dp[H])

### FIXED CODE ###

INF = 10 ** 18
H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
dp = [INF for i in range(H + 1)]

dp[0] = 0

for i in range(N):
    for j in range(H):
        if j - ab[i][0] + 1 >= 0:
            dp[j + 1] = min(dp[j + 1], dp[j - ab[i][0] + 1] + ab[i][1])
        else:
            dp[j + 1] = min(dp[j + 1], dp[0] + ab[i][1])

print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np

n = int(input())
s_li = input().split()
num = list(map(int, s_li))

product = 1

for i in range(n):
    product = product * num[i-1]


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

### FIXED CODE ###

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

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

product = 1

if 0 in a_li:
    product = 0
else:
    for i in a_li:
        product *= i
        if product > 10**18:
            print(-1)
            exit()

print(product)
### BUGGY CODE ###

n=int(input())
cnt=0
for i in range(n):
    for j in range(n):
        if i*j>=n:
            break
        for k in range(n):
            if i*j+k>n:
                break
            if i*j+k==n:
                cnt+=1
print(cnt)

### FIXED CODE ###

# Python3 program to count
# number of factors
# of an array of integers
MAX = 1000005

# array to store
# prime factors
factor = [0]*(MAX + 1)

# function to generate all
# prime factors of numbers
# from 1 to 10^6


def generatePrimeFactors():
    factor[1] = 1

    # Initializes all the
    # positions with their value.
    for i in range(2, MAX):
        factor[i] = i

    # Initializes all
    # multiples of 2 with 2
    for i in range(4, MAX, 2):
        factor[i] = 2

    # A modified version of
    # Sieve of Eratosthenes
    # to store the smallest
    # prime factor that divides
    # every number.
    i = 3
    while(i * i < MAX):
        # check if it has
        # no prime factor.
        if (factor[i] == i):
            # Initializes of j
            # starting from i*i
            j = i * i
            while(j < MAX):
                # if it has no prime factor
                # before, then stores the
                # smallest prime divisor
                if (factor[j] == j):
                    factor[j] = i
                j += i
        i += 1

# function to calculate
# number of factors


def calculateNoOFactors(n):
    if (n == 1):
        return 1
    ans = 1

    # stores the smallest
    # prime number that
    # divides n
    dup = factor[n]

    # stores the count of
    # number of times a
    # prime number divides n.
    c = 1

    # reduces to the next
    # number after prime
    # factorization of n
    j = int(n / factor[n])

    # false when prime
    # factorization is done
    while (j > 1):
        # if the same prime
        # number is dividing
        # n, then we increase
        # the count
        if (factor[j] == dup):
            c += 1

        # if its a new prime factor
        # that is factorizing n,
        # then we again set c=1 and
        # change dup to the new prime
        # factor, and apply the formula
        # explained above.
        else:
            dup = factor[j]
            ans = ans * (c + 1)
            c = 1

        # prime factorizes
        # a number
        j = int(j / factor[j])

    # for the last
    # prime factor
    ans = ans * (c + 1)

    return ans
# Driver Code


if __name__ == "__main__":

    # generate prime factors
    # of number upto 10^6
    generatePrimeFactors()
    # a = [10, 30, 100, 450, 987]
    # q = len(a)
    s=0
    for i in range(1, int(input())):
        s+=(calculateNoOFactors(i))
    print(s)

# This code is contributed
# by mits.
### BUGGY CODE ###

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

from operator import itemgetter
AB.sort(key = itemgetter(0))
AB.sort(key = itemgetter(1),reverse = True)

days = [0]*(M+1)
points = list(range(M+1))

from  bisect import bisect_right

for a,b in AB:
    point = M - a
    i = bisect_right(points,point)
    if i > 0:
        days[points[i-1]] = b
        points.pop(i-1)
print(sum(days))

### FIXED CODE ###

import heapq
from operator import itemgetter

def main():
    N, M = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    AB.sort(key = itemgetter(0))
    heap = []
    ans = 0
    cnt = 0
    for i in range(1,M + 1):
        while cnt < N and AB[cnt][0] <= i:
            heapq.heappush(heap,-1*AB[cnt][1])
            cnt += 1
        if len(heap) > 0:
            ans += heapq.heappop(heap)*-1
    print(ans)
    return

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

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

from math import log10

total=1
for i in range(n):
    total*=a[i]

if total-pow(10,18)>0:
    print(-1)
else:
    print(total)

### FIXED CODE ###

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

if a.count(0)>0:
    print(0)
    exit(0)

total=1
for i in a:
    total *=i

    if total>10**18:
        print(-1)
        exit(0)
    
print(total)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys
import math


def is_prime(n):
    if n == 2:
        return True
    elif n < 2 or not n % 2:
        return False

    k = 3
    while k <= math.sqrt(n):
        if not n % k:
            return False
        k += 2

    return True


def phi(n):
    y = n
    for k in range(2, n + 1):
        if not n % k and is_prime(k):
            y -= y / k
    return int(y)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
1000000

output:
400000
"""

import sys


def min_prime_factor(n):
    k = 2
    while True:
        if pow(k, 2) > n:
            return n
        if not n % k:
            return k
        k += 1


def phi(n):
    ans = n
    while True:
        p = min_prime_factor(n)
        if n == 1:
            break
        while not n % p:
            n //= p
        ans *= (1 - 1 / p)
    return int(ans)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1 = int(_input[0])
    print(phi(n1))