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

import sys
S=sys.stdin.readlines()
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(S[0])
X=[list(map(int,S[i+1].split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  V=[Bsum(B1,X[i][1]+1),Bsum(B2,X[i][1]+1)]
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*(pow(2,V[0],mod)-1)%mod
    if Z[j][1]:
      A=A*(pow(2,i-V[0],mod)-1)%mod
    if Z[j][2]:
      A=A*(pow(2,V[1],mod)-1)%mod
    if Z[j][3]:
      A=A*(pow(2,N-i-1-V[1],mod)-1)%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)

### FIXED CODE ###

import sys
S=sys.stdin.readlines()
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(S[0])
X=[list(map(int,S[i+1].split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  V=[Bsum(B1,X[i][1]+1),Bsum(B2,X[i][1]+1)]
  W=[pow(2,V[0],mod)-1,pow(2,i-V[0],mod)-1,pow(2,V[1],mod)-1,pow(2,N-i-1-V[1],mod)-1]
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*W[0]%mod
    if Z[j][1]:
      A=A*W[1]%mod
    if Z[j][2]:
      A=A*W[2]%mod
    if Z[j][3]:
      A=A*W[3]%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)
### BUGGY CODE ###

x, y, z, k = [int(elem) for elem in input().split()]
a_lst = [int(elem) for elem in input().split()]
b_lst = [int(elem) for elem in input().split()]
c_lst = [int(elem) for elem in input().split()]

ab_lst = []
for a in a_lst:
  for b in b_lst:
    ab_lst.append(a + b)

ab_lst = sorted(ab_lst, reverse=True)
    
res = []
for ab in ab_lst[:k]:
  for c in c_lst:
    res.append(ab + c)

res = sorted(res, reverse=True)
for elem in res[:k]:
  print(elem)
    


  
    

### FIXED CODE ###

x,y,z,k = map(int, input().split())
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)
 
cakes = []
for x, a in enumerate(A):
    if x+1 > k: break
        
    for y, b in enumerate(B):
        if (x+1)*(y+1) > k: break
            
        for z, c in enumerate(C):
            if (x+1)*(y+1)*(z+1) > k: break
                
            cakes.append(a+b+c)
    
cakes.sort(reverse=True)      
for cake in cakes[:k]:
    print(cake)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(set(a))
ans = 0
for i in b:
    if a.count(i) < i:
        ans += a.count(i)
    elif a.count(i) > i:
        ans += a.count(i)-i
    else:
        continue
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
ans = 0 
c = Counter(list(map(int, input().split())))

for key, value in c.items():
    if key < value:
        ans += value-key
    elif key > value:
        ans += value
print(ans)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
As.insert(0, 0)
Ans = [0 for _ in range(N + 1)]
Ans[N] = As[N]
for i in range(N - 1, 0, -1):
    p = i * 2
    s = 0
    while p <= N:
        s ^= Ans[p]
        p += i
    Ans[i] = 0 if s == As[i] else 1
M = sum(Ans)
print(M)
if M > 0:
    bs = ""
    for i in range(1, N + 1):
        if Ans[i] != 0:
            bs += "%d " % i
    bs = bs.rstrip(" ")
    print(bs)

### FIXED CODE ###

N = int(input())
As = list(map(bool, map(int, input().split())))
As.insert(0, False)
Ans = [False for _ in range(N + 1)]
Ans[N] = As[N]
for i in range(N - 1, 0, -1):
    p = i * 2
    s = False
    while p <= N:
        s ^= Ans[p]
        p += i
    Ans[i] = s ^ As[i]
M = sum(Ans)
print(M)
if M > 0:
    c = True
    for i in range(1, N + 1):
        if Ans[i]:
            if c:
                c = False
            else:
                print(" ", end="")
            print(i, end="")
    print("")
### BUGGY CODE ###

S = input()
ls = len(S)
box = [1]*ls

Sc = S
Sc = Sc.replace("RL", "X")

counter = 0
mval = 0


for i in Sc:
    if i != "X":
        counter += 1
        mval = max(counter, mval)
    else:
        counter = 0

if mval % 2 == 0:
    pass
else:
    mval += 1


for i in range(mval):
    boxc = box.copy()
    for j, k in enumerate(S):
        if box[j] == 0:
            continue

        if k == "R":
            box[j+1] += boxc[j]
            box[j] -= boxc[j]
        else:
            box[j-1] += boxc[j]
            box[j] -= boxc[j]

print(' '.join(map(str, box)))

### FIXED CODE ###

S = list(str(input()))
ls = len(S)
a = [1]*ls
for i in range(ls-2):
    if S[i] == S[i+1] == "R":
        a[i+2] += a[i]
        a[i] = 0
for i in range(ls)[::-1]:
    if S[i] == S[i-1] == "L":
        a[i-2] += a[i]
        a[i] = 0
print(" ".join(map(str, a)))
### BUGGY CODE ###

from heapq import heappop,heappush
def main(a,b):
    for i in range(n):
        if b[i]<=a[i]:
            pass
        else:
            print(-1)
            exit()
    pq=[]
    [heappush(pq,[-x,i]) for i,x in enumerate(a)]
    ans=0
    while pq:
        v,i=heappop(pq)
        v=-v
        vv=v
        v-=b[i]
        tmp=a[(i-1)%n]+a[(i+1)%n]
        ans+=v//tmp
        v%=tmp
        v+=b[i]
        a[i]=v
        if v==b[i]:continue
        elif vv<=v or v<b[i]:
            print(-1)
            exit()
        heappush(pq,[-v,i])
    print(ans)
if __name__=='__main__':
    n=int(input())
    b=list(map(int,input().split()))
    a=list(map(int,input().split()))
    main(a,b)


### FIXED CODE ###

def main(n,a,b):
    ans=0
    while True:
        cnt=0
        for i in range(n):
            m=a[(i-1)%n]+a[(i+1)%n]
            if m<a[i] and b[i]<a[i]:
                a[i]-=b[i]
                cnt+=a[i]//m
                a[i]%=m
                a[i]+=b[i]
        if cnt==0:break
        ans+=cnt
    if a==b:
        print(ans)
    else:
        print(-1)
if __name__=='__main__':
    n=int(input())
    b=list(map(int,input().split()))
    a=list(map(int,input().split()))
    main(n,a,b)
### BUGGY CODE ###

#2問目
NQ = input().split()
N,Q = int(NQ[0]), int(NQ[1])
S = input()
P = [input().split() for i in range(Q)]
for i in range(Q):
    print(S.count("AC", int(P[i][0])-1, int(P[i][1])))

### FIXED CODE ###

#2問目
NQ = input().split()
N,Q = int(NQ[0]), int(NQ[1])
S = input()
P = [input().split() for i in range(Q)]
 
#累積和
ruiseki = [0]*N
for i in range(1,N):
    if(S[i] == "C" and S[i-1] == "A"):
        ruiseki[i] = ruiseki[i-1] + 1
    else:
        ruiseki[i] = ruiseki[i-1]
 
for j in range(Q):
    print(ruiseki[int(P[j][1]) - 1] - ruiseki[int(P[j][0]) - 1])
### BUGGY CODE ###

def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    def calc(x,y):return (int(x)%kk,int(y)%kk)
    b=[[0]*(kk+1) for _ in [0]*(kk+1)]
    w=[[0]*(kk+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":b[int(x)%kk+1][int(y)%kk+1]+=1
        else:w[int(x)%kk+1][int(y)%kk+1]+=1
    b=[list(ac(i)) for i in b]
    w=[list(ac(i)) for i in w]
    for i in range(1,kk+1):
        for j in range(kk+1):
            b[i][j]+=b[i-1][j]
            w[i][j]+=w[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(kk):
            if j==0:
                b_t=((j,j+k,0),(j+k,kk,1))
            elif j<k:
                b_t=((0,j,-1),(j,j+k,0),(j+k,kk,1))
            elif j==k:
                b_t=((0,j,-1),(j,kk,0))
            else:
                b_t=((0,j-k,-2),(j-k,j,-1),(j,kk,0))
            black=[]
            white=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
                    else:
                        white.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            for tx1,ty1,tx2,ty2 in white:
                ret+=w[tx1][ty1]+w[tx2][ty2]-w[tx1][ty2]-w[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()

### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    n,k=map(int,input().split())
    kk=2*k
    xyc=[input().split() for _ in [0]*n]
    b=[[0]*(k+1) for _ in [0]*(kk+1)]
    for x,y,c in xyc:
        if c=="B":
            if int(y)%kk<k:
                b[int(x)%kk+1][int(y)%k+1]+=1
            else:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
        else:
            if int(y)%kk<k:
                b[(int(x)+k)%kk+1][int(y)%k+1]+=1
            else:
                b[int(x)%kk+1][int(y)%k+1]+=1
    b=[list(ac(i)) for i in b]
    for i in range(1,kk+1):
        for j in range(k+1):
            b[i][j]+=b[i-1][j]
    ans=0
    for i in range(kk):
        if i==0:
            a_t=((i,i+k,0),(i+k,kk,1))
        elif i<k:
            a_t=((0,i,-1),(i,i+k,0),(i+k,kk,1))
        elif i==k:
            a_t=((0,i,-1),(i,kk,0))
        else:
            a_t=((0,i-k,-2),(i-k,i,-1),(i,kk,0))
        for j in range(k):
            if j==0:
                b_t=((0,k,0),)
            else:
                b_t=((0,j,-1),(j,k,0))
            black=[]
            for i,j,l in a_t:
                for x,y,z in b_t:
                    if (l+z)%2==0:
                        black.append((i,x,j,y))
            ret=0
            for tx1,ty1,tx2,ty2 in black:
                ret+=b[tx1][ty1]+b[tx2][ty2]-b[tx1][ty2]-b[tx2][ty1]
            ans=max(ans,ret)
    print(ans)
main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import math
line = list(map(int,input().split()))

A,B,N =line[0],line[1],line[2]

ans = (N+1)//B
if ans ==0:
    print(math.floor(A*N/B)-A*math.floor(N/B))
else:
    kouho =[0 for j in range(ans)]
    for i in range(1,ans+1):
        x= i*B-1
        kouho[i-1]=(math.floor(A*x/B)-A*math.floor(x/B))
    
    kouho.append(math.floor(A*N/B)-A*math.floor(N/B))
    print(max(kouho))

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    import sys
    line = sys.stdin.readline
    A,B,N = map(int,input().split())
    if B>N:
        ans = A*N//B
    else:
        ans = A*(B-1)//B
    print(ans)

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

N,M = map(int,input().split())
C = []
for _ in range(N):
    A,B = map(int,input().split())
    C.append([A,B])
C = sorted(C,key=lambda x:x[0],reverse=True)
C = sorted(C,key=lambda x:x[1],reverse=True)
rev = 0
hist = [0 for _ in range(M+1)]
for x in C:
    A,B = x[0],x[1]
    if 0 in hist[-A-1::-1]:
        ind = hist[-A-1::-1].index(0)
        hist[M-A-ind]=1
        rev += B
print(rev)

### FIXED CODE ###

import bisect
N,M = map(int,input().split())
C = []
for _ in range(N):
    A,B = map(int,input().split())
    C.append([A,B])
C = sorted(C,key=lambda x:x[0],reverse=True)
C = sorted(C,key=lambda x:x[1],reverse=True)
rev = 0
hist = list(range(0,M+1))
for x in C:
    A,B = x[0],x[1]
    ind = bisect.bisect_right(hist,M-A)
    if ind>0:
        hist.pop(ind-1)
        rev += B
print(rev)
### BUGGY CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
c = [list(map(int, input().split())) for i in range(N)]

cost0 = []
cost1 = []
cost2 = []
indices = [2, 0, 1]
for color in range(C):
  cost = [0, 0, 0]
  for i in range(N):
    idx = indices[i%3]
    for j in range(N):
      cost[idx] += D[c[i][j]-1][color]
      idx = (idx + 1) % 3
  cost0.append([cost[0], color])
  cost1.append([cost[1], color])
  cost2.append([cost[2], color])

cost0.sort()
cost1.sort()
cost2.sort()
ans = float('inf')
for i in range(3):
  for j in range(3):
    for k in range(3):
      if len(set([cost0[i][1], cost1[j][1], cost2[k][1]])) == 3:
        ans = min(ans, cost0[i][0]+cost1[j][0]+cost2[k][0])

print(ans)

### FIXED CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
c = [list(map(int, input().split())) for i in range(N)]

cost0 = []
cost1 = []
cost2 = []
indices = [2, 0, 1]
for color in range(C):
  cost = [0, 0, 0]
  for i in range(N):
    idx = indices[i%3]
    for j in range(N):
      cost[idx] += D[c[i][j]-1][color]
      idx = (idx + 1) % 3
  cost0.append([cost[0], color])
  cost1.append([cost[1], color])
  cost2.append([cost[2], color])

cost0.sort()
cost1.sort()
cost2.sort()
ans = float('inf')
for i in range(3):
  for j in range(3):
    for k in range(3):
      if len(set([cost0[i][1], cost1[j][1], cost2[k][1]])) == 3:
        ans = min(ans, cost0[i][0]+cost1[j][0]+cost2[k][0])

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

from collections import Counter
N=int(input())
s=[sorted(input()) for i in range(N)]

def factorial(num):
    x=1
    for i in range(num,0,-1):
        x = x *i

    return x

s.sort()

ans=0
ref=s[0]

cnt=1

for i in range(1,N):
    if s[i]==ref:
        cnt+=1
        if i==N-1:
            ans+=factorial(cnt)//factorial(cnt-2)//2
    else:
        ref=s[i]
        if cnt>1:
            ans+=factorial(cnt)//factorial(cnt-2)//2
        cnt=1

print(ans)

### FIXED CODE ###

from collections import Counter
N=int(input())
s=[str(sorted(input())) for i in range(N)]

ans=0
cnt={}

for i in range(N):
    if s[i] in cnt:
        ans+=cnt[s[i]]
        cnt[s[i]]+=1
    else:
        cnt[s[i]]=1
        
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000)

def slime(slist,t):
    if len(slist)==1:
        if len(t)==0:
            return slist[0]
        elif slist[0]==t[0]:
            return t
        else:
#            t.append(slist[0])
            t.insert(0,slist[0])
        return t
    else:
        if slist[0]==slist[1]:
            del slist[0]
        else:
#            t.append(slist[0])
            t.insert(0,slist[0])
            del slist[0]
        return slime(slist,t)
        


n=int(input())
s=input()
slist=[]
t=[]

for i in range(len(s)):
    slist.append(s[i])
    
t=slime(slist,t)
print(len(t))

### FIXED CODE ###

n=int(input())
s=input()
if n==1:
    print(1)
else:
    slist=[]
    for i in range(len(s)):
        slist.append(s[i])
    
    for i in range(len(s)-1,0,-1):
        if slist[i-1]==slist[i]:
            del slist[i]

    print(len(slist))
### BUGGY CODE ###

from itertools import combinations
N,K=map(int,input().split())
px = [0 for _ in range(N)]
py = [0 for _ in range(N)]
for i in range(N):
  px[i],py[i] = list(map(int,input().split()))
a=10**20
for c in combinations(range(N), min(K,4)):
  px_ = [px[i] for i in c]
  py_ = [py[i] for i in c]
  px0,px1 = min(px_),max(px_)
  py0,py1 = min(py_),max(py_)
  dx,dy = px1-px0,py1-py0
  if a < dx*dy: continue
  cnt = 0
  for i in range(N):
    if px0<=px[i] and px[i]<=px1 and py0<=py[i] and py[i]<=py1:
      cnt += 1
  if K <= cnt: a = min(a, dx*dy)
print(a)


### FIXED CODE ###

N,K=map(int,input().split())
p = sorted([[int(_) for _ in input().split()] for i in range(N)])
a=10**20
for xi in range(N-K+1):
  for xj in range(xi+K-1,N):
    q = sorted(y for x,y in p[xi:xj+1])
    for yi in range(xj-(xi+K-1)+1):
      yj = yi+K-1 #Is the number always K?
      if q[yi]<=p[xi][1] and p[xj][1]<=q[yj]:
        a = min(a, (p[xi][0]-p[xj][0])*(q[yi]-q[yj]))
print(a)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [None]*n
dp[0], dp[1] = 0, abs(h[0]-h[1])
for i, hi in enumerate(h[2:], 2):
  di = 10**9
  m = i-k if i>k else 0
  for j in range(m, i):
    dj = dp[j] + abs(h[j]-hi)
    if di > dj:
      di = dj
    dp[i] = di
print(dp[-1])

### FIXED CODE ###

def main():
    n, K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = 10**10
    dp = [inf]*n
    dp[0] = 0
    for i, (di, hi) in enumerate(zip(dp[1:], h[1:]), 1):
        num = max(i-K, 0)
        for dk, hk in zip(dp[num:i], h[num:i]):
            a = dk+abs(hi-hk)
            if di > a:
                di = a
        dp[i] = di
    print(dp[n-1])

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


def knap(w,v,c,n):
    if c==0 or n==0:
        return 0
    if w[n-1]<=c:
        return max(knap(w,v,c-w[n-1],n-1)+v[n-1],knap(w,v,c,n-1))
    else:
        return knap(w,v,c,n-1)
      
n,c=map(int,input().split())
v= []
w = []
for  i in range(n):
  W,V=map(int,input().split())
  w.append(W)
  v.append(V)
print(knap(w,v,c,n))

### FIXED CODE ###

from collections import Counter
import math
from collections import Counter
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##########################################################
# for i in range(int(input())):
# arr = list(map(int, input().split()))
# a,b= map(int, input().split())
import bisect
#for i in range(int(input())):
def knapSack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    # Build table K[][] in bottom up manner
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]

    return K[n][W]


n, c = map(int, input().split())
w = []
v = []
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
print(knapSack(c, w, v, n))
### BUGGY CODE ###

import itertools
import bisect
N = int(input())
S = str(input())

char = [[] for _ in range(3)]

for i in range(N):
    s = S[i]
    if s == "R":
        char[0].append(i)
    elif s == "G":
        char[1].append(i)
    else:
        char[2].append(i)

ans = 0

for f, s, t in itertools.permutations(range(3), 3):
    for i in char[f]:
        # print(char[s])
        sec_start = bisect.bisect_left(char[s], i)
        for j in char[s][sec_start: ]:
            thi_start = bisect.bisect_left(char[t], j)
            for k in char[t][thi_start: ]:
                if j - i != k - j:
                    # print(i, j, k)
                    ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

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

dic = Counter(S)
ans = dic["R"] * dic["G"] * dic["B"]

for cntr in range(N):
    i = 1
    while True:
        left = cntr - i
        right = cntr + i
        if not (0 <= left and right < N): break
        if S[left] != S[cntr] and S[cntr] != S[right] and S[right] != S[left]: ans -= 1
        i += 1

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

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

max = max(a)
min = max * -1
ans = 10000000
prev = 10000000
list = []
flag = 0
for b in range(min,max):
  sum = 0
  j = 0
  for i in a:
    j += 1
    sum += abs(i - (b+j))
  if ans > sum:
    ans = sum
  if prev < sum:
    flag += 1
  if flag == 2:
    break
  prev = sum

print(ans)

### FIXED CODE ###

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

b = []

for i in range(n):
  b.append(a[i]-(i+1))

# print(b)
b.sort()
# print(b)

min_b=b[n//2]
# print(min_b)

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

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i,d in enumerate(s):
	if d=="?":
		for x in range(10):
			for y in range(13):
				dp[i+1][(y*10+x)%13] += dp[i][y]
	else:
		d = int(d)
		for y in range(13):
			dp[i+1][(y*10+d)%13] += dp[i][y]
	for j in range(13):
		dp[i+1][j] %= mod
print(dp[n][5])

### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
for i,d in enumerate(s):
	if d=="?":
		for x in range(10):
			for y in range(13):
				dp[i+1][(y*10+x)%13] += dp[i][y]
	else:
		d = int(d)
		for y in range(13):
			dp[i+1][(y*10+d)%13] += dp[i][y]
	for j in range(13):
		dp[i+1][j] %= mod
print(dp[n][5])
### BUGGY CODE ###

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


### FIXED CODE ###

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