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

def calc_lcs(X, Y):
    max_lcs = 0
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = [[0]*1001 for i in range(1000+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
            max_lcs = max(max_lcs, c[i][j])
    return max_lcs


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())

    for _ in range(num):
        X = input()
        Y = input()
        # X = 'abcbdab'
        # Y = 'bdcaba'


        # ???????????????
        result = calc_lcs(X, Y)

        # ???????????¨???
        print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

最長共通部分列
"""


c = []
def prep_array(X, Y):
    global c
    """ 値が0の2次元配列を用意する。サイズは入力データの最大値を想定して縦横(1000+1)以上必要。 """
    # from array import array
    # c = [array('I', [0] * (len(X)+1)) for _ in range(len(Y)+1)]  #  arrayで用意
    c = [[0]*(len(Y)+2) for _ in range(len(X)+2)] #  リストで用意
    return c


def check_max(array):
    """ 2次元配列の中の最大の値を返す """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]のアクセス方法を変更
    リストの値を一旦変数に保存するように変更
    最長共通部分長を関数内で計算するように変更
    4/5 のテストデータを使用してプロファイリングすると実効時間は 5.6秒
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs


if __name__ == '__main__':
    # データの入力
    num = int(input())
    #f = open('input.txt')
    #num = int(f.readline())

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        # 処理の実行
        result = calc_lcs4(X, Y, prep_array(X, Y))

        # 結果の表示
        print(result)
### BUGGY CODE ###

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

result=1

if 0 in A:
    result=0

for i in range(N):
    result = result*A[i]

if result > 10**18:
    result=-1

print(result)

### FIXED CODE ###

import sys
n = input()
list_num =list(map(int,input().split()))
output = 1
if 0 in list_num:
    print(0)
    sys.exit()
for i in list_num:
    output = output * i
    if output > 10 ** 18:
        print(-1)
        sys.exit()
print(output)
### BUGGY CODE ###

import math

num = int(input())

box = [1,2,3,4,5,6,7,8,9]
k=0



if num < 10:
    print(box[num-1])

else:
    while True:
        #boxに入っている数字がnumと同じ個数だったら終わり
        if len(box)==num:
            print(box[num-1])
            break

        k = k+1 #k=数字
        k1 = str(k)
        for i in range(len(k1)-1):
            if i == len(k1)-2:
                if abs(int(k1[i])-int(k1[i+1]))<=1:
                    box.append(k)
            if abs(int(k1[i])-int(k1[i+1]))<=1:
                continue
            else:break


### FIXED CODE ###

a = [1,2,3,4,5,6,7,8,9]
i = -1
N = int(input())

while True:
    if  len(a) >= N:
        print(a[N-1])
        break
    i = i + 1
    n = int(str(a[i])[-1])
    x = a[i]*10 + n-1
    y = a[i]*10 + n
    z = a[i]*10 + n+1
    if n != 9 and n != 0:
        w = (x,y,z)
        a.extend(w)
    elif n == 9:
        w = (x,y)
        a.extend(w)
    elif n == 0:
        w = (y,z)
        a.extend(w)
### BUGGY CODE ###

class BinaryIndexedTree:
    def __init__(self,n,default = 0):
        self.s = [default]*(n+1)
        self.n = n
    
    def add(self,val,idx):
        while idx < self.n+1:
            self.s[idx] = self.s[idx] + val
            idx += idx&(-idx)
        return
    
    def get(self,idx):
        res = 0
        while idx > 0:
            res = res + self.s[idx]
            idx -= idx&(-idx)
        return res

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

n = int(input())
S = [ord(s) - ord('a') for s in input()[:-1]]

BIT = [BinaryIndexedTree(n) for i in range(26)]

for i,s in enumerate(S):
    BIT[s].add(1,i+1)

Q = int(input())
ans = []
for _ in range(Q):  
    flag,x,y = input().split()

    if flag == "1":
        i = int(x)
        c = ord(y) - ord('a')
        BIT[S[i-1]].add(-1,i)
        BIT[c].add(1,i)
        S[i-1] = c
    else:
        l = int(x)
        r = int(y)
        res = 0
        for i in range(26):
            # print([BIT[i].get(r),BIT[i].get(l)])
            res += (BIT[i].get(r) > BIT[i].get(l-1))
        ans.append(str(res))
print("\n".join(ans))


### FIXED CODE ###

class BinaryIndexedTree:
    def __init__(self,n,default = 0):
        self.s = [default]*(n+1)
        self.n = n
    
    def add(self,val,idx):
        while idx < self.n+1:
            self.s[idx] = self.s[idx] + val
            idx += idx&(-idx)
        return
    
    def get(self,idx):
        res = 0
        while idx > 0:
            res = res + self.s[idx]
            idx -= idx&(-idx)
        return res

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

n = int(input())
S = [ord(s) - ord('a') for s in input()[:-1]]

BIT = [BinaryIndexedTree(n) for i in range(26)]

for i,s in enumerate(S):
    BIT[s].add(1,i+1)

Q = int(input())
ans = []
for _ in range(Q):  
    flag,x,y = input().split()

    if flag == "1":
        i = int(x)
        c = ord(y) - ord('a')
        BIT[S[i-1]].add(-1,i)
        BIT[c].add(1,i)
        S[i-1] = c
    else:
        l = int(x)
        r = int(y)
        res = 0
        for i in range(26):
            # print([BIT[i].get(r),BIT[i].get(l)])
            res += (BIT[i].get(r) > BIT[i].get(l-1))
        ans.append(str(res))
print("\n".join(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
h = list(map(int, input().split()))
init = (10 ** 4) * N
dp = [init] * N
dp[0] = 0
 
for i, h_i in enumerate(h):
    if i == 0:
        continue
    Resmin = init
    for j in range(1, K+1):
        if i - j < 0:
            break
        tmp = dp[i-j] + abs(h_i - h[i-j])
        if tmp < Resmin:
            Resmin = tmp
    dp[i] = Resmin
     
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [0] * N

for i, hi in enumerate(h):
    if i == 0:
        continue
    if i - K < 0:
        dp[i] = min(dpk + abs(hi-hk) for dpk, hk in zip(dp[:i], h[:i]))
    else:
        dp[i] = min(dpk + abs(hi-hk) for dpk, hk in zip(dp[i-K:i], h[i-K:i]))

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

from collections import defaultdict

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

adj = defaultdict(list)
in_deg = defaultdict(int)
for u, row in enumerate(a, 1):
    for v1, v2 in zip(row, row[1:]):
        uu1, vv1 = min(u, v1), max(u, v1)
        uu2, vv2 = min(u, v2), max(u, v2)
        adj[(uu1, vv1)].append((uu2, vv2))
        in_deg[(uu1, vv1)]
        in_deg[(uu2, vv2)] += 1

now = [tpl for tpl, val in in_deg.items() if val == 0]
day = 0
while now:
    day += 1
    nxt = []
    for u in now:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt.append(v)

    now = nxt

if max(in_deg.values()) > 0:
    day = -1

print(day)


### FIXED CODE ###

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


def match2int(x, y):
    x, y = min(x, y), max(x, y)
    return (2 * n - 1 - x) * x // 2 + y - x - 1


match_sm = n * (n - 1) // 2

adj = [[] for _ in range(match_sm)]
in_deg = [0] * match_sm
for i, li in enumerate(a):
    for j, k in zip(li, li[1:]):
        j -= 1
        k -= 1
        match1 = match2int(i, j)
        match2 = match2int(i, k)
        adj[match1].append(match2)
        in_deg[match2] += 1

cnd = [i for i, e in enumerate(in_deg) if e == 0]
day = 0
while cnd:
    nxt_cnd = []
    for u in cnd:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt_cnd.append(v)

    cnd = nxt_cnd
    day += 1

if in_deg.count(0) != match_sm:
    day = -1

print(day)
### BUGGY CODE ###

import math
A,B,N = [int(i)for i in input().split()]
tmpmax = 0
breakflag=False
for i in range(N+1):
  tmp=math.floor(A*i/B)-A*math.floor(i/B)
  if tmp > tmpmax:
    tmpmax = tmp
  elif tmp < tmpmax:
    breakflag=True
  elif tmp == tmpmax and breakflag:
    break
print(tmpmax)

### FIXED CODE ###

import math
A,B,N = [int(i)for i in input().split()]

def func(A, B, N):
  if N>B-1:
    return math.floor(A*(B-1)/B)-A*math.floor((B-1)/B)
  else:
    return math.floor(A*N/B)-A*math.floor(N/B)


print(func(A,B,N))
### BUGGY CODE ###

s = input()
l1 = len(s)

for i in range(l1):
    if '01' in s or '10' in s:
        s = s.replace('01', '')
        s = s.replace('10', '')
    else:
        break
        
print(l1 - len(s))

### FIXED CODE ###

s = input()
cnt = [s.count('0'), s.count('1')]

print(len(s) - (max(cnt) - min(cnt)))
### BUGGY CODE ###

# D - Match Matching
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from collections import defaultdict

MATCH = [(0, 6), (1, 2), (2, 5), (3, 5), (4, 4), (5, 5), (6, 6), (7, 3), (8, 7), (9, 6)]
N, M = map(int, input().split())
A = list(int(x) for x in input().split())
MA = []
for a in A:
    MA.append(MATCH[a])
MA.sort(key=lambda x: x[1])

def dfs(tmp, s):
    global ans
    if s == N:
        ans = max(ans, tmp)    
    for ma in MA:
        if s+ma[1] <= N:
            tmp = tmp*10 + ma[0]
            dfs(tmp, s + ma[1])
            tmp //= 10

tmp = 0
ans = 0
dfs(tmp, 0)
print(ans)

### FIXED CODE ###

# D - Match Matching

N, M = map(int, input().split())
A = list(int(x) for x in input().split())
match_list = [('0', 6), ('1', 2), ('2', 5), ('3', 5), ('4', 4), ('5', 5), ('6', 6), ('7', 3), ('8', 7), ('9', 6)]
MA = []
for a in A:
    MA.append(match_list[a])
MA.sort(key=lambda x: x[0], reverse=True)

# dp[i] := i本のマッチを使って作れる最大桁数
dp = [-1] * (N+1)
dp[0] = 0
for i in range(N+1):
    for j in range(M):
        if i-MA[j][1] >= 0:
            dp[i] = max(dp[i], dp[i-MA[j][1]] + 1)

remain_keta = dp[N]
remain_match = N
ans = ''
for i in range(dp[N]):
    for ma in MA:
        # 大きい数字から一桁使った時に、
        # 残り桁がちょうど一桁減っている場合
        if remain_match >= ma[1] and dp[remain_match - ma[1]] == remain_keta - 1:
            ans +=  ma[0]
            remain_keta -= 1
            remain_match -= ma[1]
            break

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

N=int(input())
A = [int(input()) for i in range(N)]
for i,a in enumerate(A):
  B = A[:]
  B[i]=0
  print(max(B))


### FIXED CODE ###

N=int(input())
A = [int(input()) for i in range(N)]
maxval = max(A)
argmaxval = A.index(maxval)
for i,a in enumerate(A):
  if i==argmaxval:
    B = A[:]
    B[i]=0
    print(max(B))
  else:
    print(maxval)
### BUGGY CODE ###

n = int(input())
c = input()
min_count = n
for i in range(n):
    s = c.count('R')
    W = c[:s].count('W')
    R = c[s:].count('R')
    """
    if W <= R:
        count = R # W + (R - W) # 仕切りより左側の白い石W個と、右側に残った赤い石R-W個
    else: # W >R
        count = W # R + (W - R)
    # 結局のところ、count = max(W,R)
    """
    count = max(W,R)        
    if min_count > count:
        min_count = count   
print(min_count)

### FIXED CODE ###

n = int(input())
c = input()
r = c.count('R')
w = c.count('W')
count = 0
for i in range(r):
    if c[i] == 'W':
        count += 1
print(count)
### BUGGY CODE ###

import math
N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
idx = []
for i in range(N):
  B[A[i]-1] += 1
  if B[A[i]-1] >= 2 and not A[i]-1 in idx:
    idx.append(A[i]-1)

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

Cs = []
C = []
for j in idx:
  if B[j]-1 >= 2:
    Cs.append(nCr(B[j]-1, 2))
  else:
    Cs.append(0)
  C.append(nCr(B[j], 2))
Ctot = sum(C)

for i in range(N):
  current_idx = A[i]-1
  count = Ctot
  for k, j in enumerate(idx):
    if j == current_idx:
      count += Cs[k]
      count -= C[k]
  print(count)

### FIXED CODE ###

N = int(input())
A = [int(s) for s in input().split()]
B = [0 for i in range(N)]
def nC2(n):
  return n*(n-1)//2
for i in range(N):
  B[A[i]-1] += 1
Ctot = 0
for i in range(N):
  Ctot += nC2(B[i])
for i in range(N):
  current_idx = A[i]-1
  if B[current_idx] == 1:
    count = Ctot
  else:
    count = Ctot + nC2(B[current_idx]-1) - nC2(B[current_idx])
  print(count)
### BUGGY CODE ###

#ABC118C-MonstersBattleRoyale.py

from sys import stdin
import numpy as np

input = stdin.readline

N = int(input())

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

A = set(A)
A = list(A)

def countzero(list):
    i = 0
    for a in list:
        if a == 0:
            i += 1
    return i

while len(A) != 1:
    a = countzero(A)
    A.sort()
    for i in range(a+1,len(A)):
        A[i] = A[i] % A[a]
    if a >= N-1:
        break

i = 0
while True:
    if A[i] != 0:
        print(A[i])
        break
    i += 1


### FIXED CODE ###

#ABC118C-MonstersBattleRoyale.py

from sys import stdin
from functools import reduce
import fractions

input = stdin.readline

N = int(input())

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

answer = reduce(fractions.gcd, A)
print(answer)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c
import numpy as np

N, Q = map(int, input().split())
N = int(N)
S = input()
lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append((l - 1, r - 1))

locations = []
for i in range(len(S) - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        locations.append(i)
locations = np.array(locations)
# print('locations', locations)

t = []
for i in range(len(S) + 1):
    t.append(np.count_nonzero(locations < i))
# print(t)
for l, r in lr:
    print(t[r] - t[l])


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0]
for i in range(2, len(S) + 1):
    if S[i - 2:i] == 'AC':
        v = cnt[-1] + 1
    else:
        v = cnt[-1]
    cnt.append(v)

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

n = int(input())
L = []
count = 0
for i in range(n):
    L.append(input())

for j in range(n):
    for k in range(j+1, n):
        st1 = sorted(list(L[j]))
        st2 = sorted(list(L[k]))
        if st1 == st2:
            count += 1

print(count)


### FIXED CODE ###

n = int(input())
D = {}
count = 0
for i in range(n):
    line = "".join(sorted(list(input())))
    if line not in D:
        D[line] = 0
    else:
        D[line] += 1
        count += D[line]

print(count)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

H, W = list(map(int, input().split()))
A = [list(input()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


hw = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            if ok(h, w) and A[h][w] == '#':
                hw.add((h, w))

ans = -1
while len(hw) > 0:
    ans += 1
    nexts = set()
    while len(hw) > 0:
        h, w = hw.pop()
        if ok(h + 1, w) and A[h + 1][w] == '.':
            A[h + 1][w] = '#'
            nexts.add((h + 1, w))
        if ok(h - 1, w) and A[h - 1][w] == '.':
            A[h - 1][w] = '#'
            nexts.add((h - 1, w))
        if ok(h, w + 1) and A[h][w + 1] == '.':
            A[h][w + 1] = '#'
            nexts.add((h, w + 1))
        if ok(h, w - 1) and A[h][w - 1] == '.':
            A[h][w - 1] = '#'
            nexts.add((h, w - 1))
    hw = nexts
print(ans)


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

H, W = list(map(int, input().split()))
A = np.array([list(input()) for _ in range(H)])

counts = np.zeros((H, W))
counts[A == '.'] = np.inf

for h in range(1, H):
    counts[h, :] = np.minimum(counts[h, :], counts[h - 1, :] + 1)
    counts[-1 - h, :] = np.minimum(counts[-1 - h, :], counts[-h, :] + 1)
for w in range(1, W):
    counts[:, w] = np.minimum(counts[:, w], counts[:, w - 1] + 1)
    counts[:, -1 - w] = np.minimum(counts[:, -1 - w], counts[:, -w] + 1)

print(int(np.max(counts)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = (ans + (lcm // v)) % MOD
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = ans + (lcm // v)
print(ans % MOD)
### BUGGY CODE ###

N, Y = map(int, input().split())
x = 0
otoshidama = {}
for i in range(N+1):
    for j in range(N-i+1):
        for k in range(N-i-j+1):
            if i+j+k == N:
                if Y == i*10000 + j*5000 + k*1000:
                    while x == 0:
                        print(i, j, k)
                        x += 1
if x == 0:
    print('-1 -1 -1')

### FIXED CODE ###

N, Y = map(int, input().split())
for i in range(N+1):
    for j in range(N-i+1):
        k = N - i - j
        t = (i, j, k)
        if Y == i*10000 + j*5000 + k*1000:
           print(*t)
           exit()
print('-1 -1 -1')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def solve(a,w,dp):
    if not a or w==0: return 0
    if (str(a),w) in dp: return dp[(str(a),w)]
    maxx=0
    for i in range(len(a)):
        if a[i][0]<=w:
            maxx=max(maxx,a[i][1]+solve(a[:i]+a[i+1:],w-a[i][0],dp))
    dp[(str(a),w)]=maxx
    return maxx
if __name__=='__main__':
    n,w=map(int,input().split())
    a=[]
    sw=0
    for i in range(n):
        p,q=map(int,input().split())
        a.append((p,q))
        sw+=a[-1][0]
    a.sort(key=lambda x: x[0])
    print(solve(a,w,{}))

### FIXED CODE ###

def solve(w,v,tv,W):
    dp=[float('inf')]*(tv+1)
    dp[0]=0
    for i in range(len(w)):
        for j in range(tv-v[i],-1,-1):
            dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i])
    maxx=0
    for i in range(tv+1):
        if dp[i]<=W:
            maxx=max(maxx,i)
    return maxx
if __name__=='__main__':
    n,W=map(int,input().split())
    w=[]
    v=[]
    for i in range(n):
        p,q=map(int,input().split())
        w.append(p)
        v.append(q)
    print(solve(w,v,sum(v),W))
### BUGGY CODE ###

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

ans=1

for i in a:
    ans=ans*i

if ans>1000000000000000000:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

import sys

def main():
    n = int(input())
    a=sys.stdin.readline().rstrip().split()
    if '0' in a:
        print(0)
        return
    ans=1
 
    for i in a:
        ans=ans*int(i)
        if ans>1000000000000000000:
            print("-1")
            return
    else:
        print(ans)
main()
### BUGGY CODE ###

memo = {}

def gcd(a, b):
    if (a, b) in memo.keys():
        return memo[(a, b)]
    if b == 0:
        return a
    return gcd(b, a % b)

n = input()
a_list = map(int, raw_input().split())
max_g = 0
for exclude in reversed(xrange(n)):
    g = a_list[0] if exclude > 0 else a_list[1]
    for i, a in enumerate(a_list):
        if i == 0 or i == exclude:
            continue
        g_new = gcd(g, a)
        if (g, a) not in memo:
            memo[(g, a)] = g_new
        g = g_new
        if g <= max_g:
            break
    if g > max_g:
        max_g = g
print(max_g)


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    g = gcd(b, a % b)
    return g

n = input()
a_list = map(int, raw_input().split())

gs1 = [None] * n
gs1[0] = a_list[0]
for i in xrange(1, n):
    gs1[i] = gcd(gs1[i - 1], a_list[i])

gs2 = [None] * n
gs2[n - 1] = a_list[n - 1]
for i in reversed(xrange(n - 1)):
    gs2[i] = gcd(gs2[i + 1], a_list[i])

max_g = 0
for exclude in xrange(n):
    if exclude == 0:
        g = gs2[1]
    elif exclude == n - 1:
        g = gs1[n - 2]
    else:
        g = gcd(gs1[exclude - 1], gs2[exclude + 1])
    if g > max_g:
        max_g = g
print(max_g)
### BUGGY CODE ###

s_list = list(input())
res = 0
for i in range(len(s_list)):
    if s_list[i] == 'A':
        for j in range(i,len(s_list)):
            if s_list[j] == 'Z':
                res = max(res,len(s_list[i:j+1]))
print(res)

### FIXED CODE ###

s_list = list(input())
a_num = 0
z_num = 0
for i,a in enumerate(s_list):
    if a == 'A':
        a_num = i
        break
rs_list = reversed(s_list)
for j,z in enumerate(rs_list):
    if z == 'Z':
        z_num = j
        break
if z_num == 0:
    print(len(s_list[a_num:]))
else:
    print(len(s_list[a_num:-z_num]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    p = 1
    m = pow(10, 18)
    for n in A:
        p = p * n
    if p > m:
        return -1
    return p


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    p = 1
    m = pow(10, 18)
    if 0 in A: return 0
    for n in A:
        p = p * n
        if p > m:
            return -1
    return p


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

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

from operator import itemgetter

n, m = list(map(int, input().split()))
shops = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    shops.append((a, b))

shops = sorted(shops, key=itemgetter(0))
drink = [[a] * b for (a, b) in shops]
drink = sum(drink, [])
# print(drink)
answer = sum(drink[:m])
print(answer)

### FIXED CODE ###

from operator import itemgetter

n, m = list(map(int, input().split()))
shops = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    shops.append((a, b))

shops = sorted(shops, key=itemgetter(0))
rest = m
cost = 0
for a, b in shops:
    if rest > b:
        cost += a * b
        rest -= b
    else:
        cost += a * rest
        break

print(cost)