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

N=int(input())
L = [int(i) for i in input().split()]

ans = 1;
for i in range(N):
	ans *= L[i]
  
if ans > 1000000000000000000:
  ans = -1
print(ans)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
ans = 1
if 0 in L:
  print(0)
  exit()
for i in range(N):
  ans *= L[i]
  if ans > 10**18:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

s = input()

ans = 0
for i in range(len(s), 3, -1):
    for j in range(len(s)-i+1):
        if int(s[j:j+i])%2019 == 0:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
s = input()

ls = len(s)
t = [0]
j = 1
for i in range(ls):
    u = (int(s[ls-1-i])*j + t[-1]) % 2019
    t.append(u)
    j = (j * 10) % 2019
c = Counter(t)
k = list(c.keys())
ans = 0
for i in k:
    ans += c[i]*(c[i]-1)/2
print(int(ans))
### BUGGY CODE ###

"""
https://atcoder.jp/contests/tokiomarine2020/submissions/14229099
"""
N,K = map(int,input().split())
A = list(map(int,input().split()))

def update(A):
    b = [0]*N

    for i,a in enumerate(A):
        l = max(0,i-a)
        r = min(N-1,i+a)

        b[l] += 1
        if r+1 < N:
            b[r+1] -= 1
    
    res = []
    s = 0
    for i in b:
        s += i
        res.append(s)
    return res

for _ in range(min(K,75)):
    A = update(A)

print(*A)

### FIXED CODE ###

"""
https://atcoder.jp/contests/tokiomarine2020/submissions/14229099
"""
N,K = map(int,input().split())
A = list(map(int,input().split()))

def update(A):
    b = [0]*N

    for i,a in enumerate(A):
        l = max(0,i-a)
        r = min(N-1,i+a)

        b[l] += 1
        if r+1 < N:
            b[r+1] -= 1
    
    res = []
    s = 0
    for i in b:
        s += i
        res.append(s)
    return res

for _ in range(min(K,75)):
    A = update(A)

print(*A)
### BUGGY CODE ###

r=input().strip().split()
N=int(r[0])
a=int(r[1])
z=input().strip().split()
w=[]
for i in range (N):
  w.append((1+int(z[i]))/2)

maximum=0

for j in range (0,N-a+1):
  s=0
  for p in range (j,j+a):
    s+=w[p]
 
  if s>maximum:
    maximum=s

print(maximum)

### FIXED CODE ###

r=input().strip().split()
N=int(r[0])
a=int(r[1])
z=input().strip().split()
s=0
for p in range (a):
    s+=(1+int(z[p]))/2
maximum=s

for j in range (0,N-a):
  s-=(1+int(z[j]))/2
  s+=(1+int(z[j+a]))/2
  if s>maximum:
    maximum=s

print(maximum)
### BUGGY CODE ###

n,p=map(int,input().split())
i,a=2,1
while pow(i,n)<=p:
  while p%pow(i,n)==0:a*=i;p//=pow(i,n)
  i+=1
print(a)

### FIXED CODE ###

n,p=map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
  if p%(i**n)==0:print(i);exit()
### BUGGY CODE ###

l, r = map(int, input().split())

LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]

ans = 2018

for i in range(l, r + 1):
  for j in range(l, i):
    ans = min(ans, LUT[i % 2019][j % 2019])
    if ans == 0:
      break
    
print(ans)

### FIXED CODE ###

def main():
  l, r = map(int, input().split())
  LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]
  ans = 2018
  m = 2019
  for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
      ans = min(ans, LUT[i % m][j % m])
      if ans == 0:
        return 0
  return ans

print(main())
### BUGGY CODE ###

import itertools
N = map(int, input())
L_list = list(map(int, input().split()))
sum = 0
#L_list = [3 4 2 1]なら[3,4,2],[3,4,1],[3,2,1],[4,2,1]の4通り
L_combinations = list(itertools.combinations(L_list,3))
for L_combination in L_combinations:
    if L_combination[0] < L_combination[1] + L_combination[2] and L_combination[1] < L_combination[2] + L_combination[0] and L_combination[2] < L_combination[0] + L_combination[1]:
        sum += 1

print(sum)

### FIXED CODE ###

N = int(input())
L_list = list(map(int, input().split()))
sum = 0

L_list.sort()

from bisect import bisect_left

for i in range(N):
    for j in range(i+1, N):
        t = L_list[i]+L_list[j]
        idx = bisect_left(L_list, t)
        sum += max(0, idx-(j+1))
        
print(sum)
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
counter=0
for i in range(a[0]-1,a[n-1]+2):
    sum=a.count(i-1)+a.count(i)+a.count(i+1)
    if sum>counter:
        counter=sum

print(counter)


### FIXED CODE ###

import collections
n=int(input())
a=sorted(list(map(int,input().split())))
c=collections.Counter(a)
counter=0
for i in range(a[0],a[n-1]+1):
    sum=c[i-1]+c[i]+c[i+1]
    if sum>counter:
        counter=sum

print(counter)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0
A = []
X = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def f(n):
    return sum(abs(x-n) for x in X)


def main():
    global X
    setrecursionlimit(100000)
    set_inputs()
    X = [a - (i + 1) for i, a in enumerate(A)]
    b = round(float(sum(X)) / float(N))
    ans = f(b)
    a = b - 1
    c = b + 1
    while ans != min(f(a), f(b), f(c)):
        if f(a) < f(b):
            b = a
            a = b - 1
            c = b + 1
        else:
            b = c
            a = b - 1
            c = b + 1
        ans = f(b)
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0
A = []
X = []


def set_inputs():
    global N, A
    N = get_int()
    A = get_li()
    return


def f(n):
    return sum(abs(x-n) for x in X)


def main():
    global X
    setrecursionlimit(100000)
    set_inputs()
    X = [a - (i + 1) for i, a in enumerate(A)]
    X.sort()
    b = X[0]
    i = 1
    passed = 0
    same = 1
    coming = N - 1
    ans = f(b)
    tmp = ans
    while i < N:
        if X[i] == b:
            same += 1
            coming -= 1
            i += 1
            continue
        diff = X[i] - b
        tmp = tmp + (passed + same - coming) * diff
        ans = min(ans, tmp)
        b = X[i]
        passed += same
        same = 1
        coming -= 1
        i += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


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

N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
MOD=10**9+7
ans=0
dp=[[0]*(M+1) for _ in range(N+1)]
ans=[[0]*(M+1) for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            dp[i+1][j+1]=(ans[i][j]+1)%MOD
        else:
            dp[i+1][j+1]=0
        ans[i+1][j+1]=(ans[i][j+1]+ans[i+1][j]-ans[i][j]+dp[i+1][j+1])%MOD
print((ans[N][M]+1)%MOD)

### FIXED CODE ###

N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))
MOD=10**9+7
ans=0
dp=[[0]*(M+1) for _ in range(N+1)]
ans=[[0]*(M+1) for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        if S[i]==T[j]:
            dp[i+1][j+1]=(ans[i][j]+1)%MOD
        else:
            dp[i+1][j+1]=0
        ans[i+1][j+1]=(ans[i][j+1]+ans[i+1][j]-ans[i][j]+dp[i+1][j+1])%MOD
print((ans[N][M]+1)%MOD)
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())
count = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            count += reduce(math.gcd, (a, b, c))

print(count)


### FIXED CODE ###

import math

count = 0

K = int(input())
for a in range(1, K+1):
    for b in range(1, K+1):
        temp = math.gcd(a, b)
        for c in range(1, K+1):
            count += math.gcd(temp, c)

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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left


N = int(input())
Pn = [[i,j] for i,j in enumerate(list(map(int, input().split())))]
Pn = sorted(Pn,key=lambda x:-x[1])

In = [Pn[0][0]]
ans = 0
for i,p in Pn[1:]:
  cnt = 0
  c = bisect_left(In,i)
  In.insert(c,i)

  # Choose leftside bigger
  if c > 0:
    l,r = 0,0
    if c == 1:
      l = In[c-1]+1
    elif c > 1:
      l = In[c-1]-In[c-2]
    if c == len(In)-1:
      r = N-In[c]
    elif c < len(In)-1:
      r = In[c+1]-In[c]
    cnt += l*r

  # Choose rightside bigger
  if c < len(In)-1:
    l,r = 0,0
    if c == len(In)-2:
      r = N-In[c+1]
    elif c < len(In)-2:
      r = In[c+2]-In[c+1]
    if c == 0:
      l = In[c]+1
    elif c > 0:
      l = In[c]-In[c-1]
    cnt += l*r
  ans += cnt*p

print(ans)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-



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

In = [0] * (N+1)
for i in range(N):
  In[Pn[i]] = i+1

cnt = 0
l = [0] + [i for i in range(N+1)]
r = [i+1 for i in range((N+1))] + [N+1]

for v in range(1, N+1):
  i = In[v]
  
  l1 = l[i]
  l2 = l[l1]
  r1 = r[i]
  r2 = r[r1]
  cnt += ((l1-l2) * (r1-i) + (i-l1) * (r2-r1)) * v
  
  l[r1] = l1
  r[l1] = r1
    
print(cnt)
### BUGGY CODE ###

#
import sys
import math
import numpy as np
import itertools

# いくつか入力
h,w = (int(i) for i in input().split())  

# 2次元配列
grid = []
for i in range(h):
    array = list(input())
    grid.append(array)

a = np.zeros((h,w), dtype=np.int)
#print(yoko)
b = np.zeros((h,w), dtype=np.int)
for i in range(h):
    for j in range(w):
        if grid[i][j]=='#':
            b[i][j] = 0
        else:
            b[i][j] = 1

for i in range(h):
    temp = 0
    for j in range(w):
        temp = (temp + 1)*b[i][j]
        a[i][j] += temp

for i in range(h):
    temp = 0
    for j in range(w-1,-1,-1):
        temp = (temp + 1)*b[i][j]
        a[i][j] += temp

for j in range(w):
    temp = 0
    for i in range(h):
        temp = (temp + 1)*b[i][j]
        a[i][j] += temp

for j in range(w):
    temp = 0
    for i in range(h-1,-1,-1):
        temp = (temp + 1)*b[i][j]
        a[i][j] += temp

answer=3
for i in range(h):
    for j in range(w):
        answer=max(a[i][j],answer)
#print(a)
print(answer-3)



### FIXED CODE ###

#
import sys
import math
import numpy as np
import itertools

# いくつか入力
h,w = (int(i) for i in input().split())  

# 2次元配列
grid = []
for i in range(h):
    array = list(input())
    grid.append(array)
b = np.array(grid)
b = np.where(b == ".", 1, 0)

a1 = np.zeros((h,w), dtype=np.int)
a2 = np.zeros((h,w), dtype=np.int)
a3 = np.zeros((h,w), dtype=np.int)
a4 = np.zeros((h,w), dtype=np.int)
#print(b)

for i in range(1,h):
    a1[i] += (a1[i-1]+1)*b[i-1]

for i in range(h-2,-1,-1):
    a2[i] += (a2[i+1]+1)*b[i+1]

for i in range(1,w):
    a3[:, i] += (a3[:, i-1]+1)*b[:, i-1]

for i in range(w-2,-1,-1):
    a4[:, i] += (a4[:, i+1]+1)*b[:, i+1]

#print(a1,a2,a3,a4)

answer = ( (a1+a2+a3+a4)*b ).max()

print(answer+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1;
        E[a].append(b)
        E[b].append(a)

    dp=[1]*n
    dp[0]=k
    def dfs(v,p)->None:
        if(p!=-1):
            count=0
            for nv in E[v]:
                if(nv==p): continue
                dp[nv]=k-2-count
                count+=1
                dfs(nv,v)
        else:
            count=0
            for nv in E[v]:
                dp[nv]=k-1-count
                count+=1
                dfs(nv,v)

    dfs(0,-1)
    ans=1
    for i in range(n):
        ans*=dp[i]
        ans%=MOD
    print(ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1;
        E[a].append(b)
        E[b].append(a)

    dp=[1]*n
    dp[0]=k
    def dfs(v,p)->None:
        if(p!=-1):
            count=0
            for nv in E[v]:
                if(nv==p): continue
                dp[nv]=k-2-count
                count+=1
                dfs(nv,v)
        else:
            count=0
            for nv in E[v]:
                dp[nv]=k-1-count
                count+=1
                dfs(nv,v)

    dfs(0,-1)
    ans=1
    for i in range(n):
        ans*=dp[i]
        ans%=MOD
    print(ans)
resolve()
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
x=0
for i in range(N):
  for k in range(i):
    x+=A[i]*A[k]
print(x%1000000007)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
x=0
x=sum(A)**2
for i in A:
  x-=i**2
print(x//2%1000000007)
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
P, Y = [], []
pref = [[] for _ in range(N+1)] # non-0-indexed
for m in range(M):
    p,y = map(int, input().split())
    P.append(p)
    Y.append(y)
    bisect.insort(pref[p], y)

ans = []   
for p,y in zip(P,Y):
    a = "{:0>6}".format(p)
    i = bisect.bisect(pref[p], y)
    a += "{:0>6}".format(i)
    ans.append(a)

for a in ans:
    print(a)

### FIXED CODE ###

import bisect
N, M = map(int, input().split())
P, Y = [], []
pref = [[] for _ in range(N+1)] # non-0-indexed
for m in range(M):
    p,y = map(int, input().split())
    P.append(p)
    Y.append(y)
    pref[p].append(y)

for i,pre in enumerate(pref):
    pref[i] = sorted(pre)

for p,y in zip(P,Y):
    a = "{:0>6}".format(p)
    i = bisect.bisect(pref[p], y)
    a += "{:0>6}".format(i)
    print(a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
 
count = 0
for i in range(n):
  for j in range(n):
    if i != j and a[i] % a[j] == 0:
      break
    elif j == n-1:
      count += 1
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
m = 1000005

count = 0
cnt = [0] * m
for i in range(n):
  if cnt[a[i]] == 0:
    for j in range(a[i], m, a[i]):
      cnt[j] += 1
  else:
    cnt[a[i]] = 2
for i in range(n):
  if cnt[a[i]] == 1:
    count += 1
print(count)
### BUGGY CODE ###

s = input()
n = len(s)
dp = [0]

for i, c in enumerate(s):
    new = [0] * (i + 2)
    km = c == 'g'
    for j in range(i % 2, i + 1, 2):
        new[j + 1] = dp[j] - (not km)
        if j:
            new[j - 1] = max(new[j - 1], dp[j] + km)
    dp = new

print(max(dp))


### FIXED CODE ###

s = input()
print(len(s) // 2 - s.count('p'))
### BUGGY CODE ###

n,a=open(0)
for i in range(int(n)):print(a.count(str(i+1)))

### FIXED CODE ###

n,*l=map(int,open(0).read().split());a=[0]*n
for i in l:a[i-1]+=1
print(*a)
### BUGGY CODE ###

MOD = 10**9+7

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

def gcd(x,y):
    while y:
        x,y = y,x%y
    return x

LCM = A[0]
for i in range(1,N):
    GCD = gcd(LCM,A[i])
    LCM = LCM*A[i]//GCD

ans = 0

for i in range(N):
    ans += LCM//A[i]
    ans %= MOD

print(ans%MOD)

### FIXED CODE ###

MOD = 10**9+7

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

def gcd(x,y):
    while y:
        x,y = y,x%y
    return x

LCM = A[0]
for i in range(1,N):
    GCD = gcd(LCM,A[i])
    LCM = LCM*A[i]//GCD
LCM %= MOD
ans = 0

for i in range(N):
    ans += LCM*pow(A[i],MOD-2,MOD)
    ans %= MOD

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

N = int(input())
A = [int(x) for x in input().split()]
B = list()
cut = 0
trend = ""

for i in range(N):
	B.append(A[i])
	if len(B) == 2 or trend == "neutral":
		if min(B) == max(B):
			trend = "neutral"
		elif A[i] == max(B):
			trend = "up"
		elif A[i] == min(B):
			trend = "down"
	elif len(B) > 2:
		if trend == "up" and A[i] != max(B):
			cut += 1
			B = [A[i]]
		elif trend == "down" and A[i] != min(B):
			cut += 1
			B = [A[i]]
print(cut + 1)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = list()
cut = 0
trend = ""

for i in range(N):
	B.append(A[i])
	if len(B) == 2 or trend == "neutral":
		if min(B) == max(B):
			trend = "neutral"
		elif A[i] == max(B):
			trend = "up"
		elif A[i] == min(B):
			trend = "down"
	elif len(B) > 2:
		if trend == "up" and A[i] < B[-2]:
			cut += 1
			B = [A[i]]
		elif trend == "down" and A[i] > B[-2]:
			cut += 1
			B = [A[i]]
print(cut + 1)
### BUGGY CODE ###



def comp(ext,list0,dev):
    c=int((ext[0]+ext[1])/2)
    if list0[int((ext[0]+ext[1])/2)]>dev:
        return ext[0],int((ext[0]+ext[1])/2)
    else:
        return int((ext[0]+ext[1])/2),ext[1]


def bis(a,b,list0,dev):
    ls=[a,b]
    while ls[0]+1<ls[1]:
        ls=comp(ls,list0,dev)
    if list0[ls[0]]==dev:
        return ls[0]-1
    elif list0[ls[1]]==dev:
        return ls[1]-1
    else:
        return ls[0]


n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(0,n-2):
    for b in range(a+1,n-1):
        if l[a]+l[b]>l[n-1]:
            c=n-1
        elif l[a]+l[b]<l[b+1]:
            c=b
        else:
            c=bis(b,n-1,l,l[a]+l[b])
        s=s+c-b
print(s)

### FIXED CODE ###

def bis_right(lis,dev):
    a=0
    b=len(lis)-1
    while a<b:
        c=(a+b)//2
        if lis[c]>dev:
            b=c
        else:
            a=c+1
    if lis[a]<=dev:
        return a
    return a-1



n=int(input())
l=[int(x) for x in input().split()]
l.sort()
s=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=bis_right(l[b+1:],l[a]+l[b]-1)
        s+=c+1
print(s)
### BUGGY CODE ###

m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [0 for j in range(len(str2)+1)]
    for j in range(len(str1)):
        A_copy = A[:]
        for k in range(len(str2)):
            if(str1[j]==str2[k]):
                A[k+1] = A_copy[k]+1
            else:
                if(A[k] > A[k+1]):
                    A[k+1] = A[k]
    print(A[-1])


### FIXED CODE ###

def LCS(str1,str2):
    A = [0 for _ in range(len(str2)+1)]
    for i in range(len(str1)):
        A_copy = A[:]
        for j in range(len(str2)):
            if(str1[i]==str2[j]):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])


m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    LCS(str1,str2)
### BUGGY CODE ###

# A - Integer Product 
from decimal import Decimal

n = int(input())
a = [input() for _ in range(n)]

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  bi = Decimal(a[i])*(10**9)
  c = 0
  while(bi%2 == 0):
    c += 1
    bi //= 2
  p2[i] = c
  bi = Decimal(a[i])*(10**9)
  c = 0
  while(bi%5 == 0):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(50)] for _ in range(50)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(48,-1,-1):
  for j in range(48,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[max(18-p2[i],0)][max(18-p5[i],0)]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)

### FIXED CODE ###

# A - Integer Product 
n = int(input())
a = [input() for _ in range(n)]

# bi=ai*(10**9)とすると、(aiは小数第9位までの小数だからbiは整数)
# ai*ajが整数<=>bi*bj/(10**18)が整数<=>bi*bjが素因数に2を18個、5を18個持つ。
# p2[i]:biを素因数分解したときの2の数。
# p5[i]:biを素因数分解したときの5の数。
# c25[i][j]:bi...bnのうち、素因数に2をi個以上、5をj個以上持つbiの数。
# biに対して、ペアになれるのはc25[18-p2[i]][18-p5[i]]個。
# ただし、自分自身は含めないのでbiが素因数として2を9個以上、5を9個以上もつときは―1する。
# また、(bi,bj)と(bj,bi)を重複して数えてしまうので、最後に//2する。

p2 = [0 for _ in range(n)]
p5 = [0 for _ in range(n)]

for i in range(n):
  if '.' in a[i]:
    bi = int(a[i].replace('.','')+'0'*(9-(len(a[i])-a[i].index('.')-1)))
  else:
    bi = int(a[i])*(10**9)
  c = 0
  while(bi%2 == 0 and c < 18):
    c += 1
    bi //= 2
  p2[i] = c
  c = 0
  while(bi%5 == 0 and c < 18):
    c += 1
    bi //= 5
  p5[i] = c

c25 = [[0 for _ in range(20)] for _ in range(20)]
for i in range(n):
  c25[p2[i]][p5[i]] += 1
for i in range(18,-1,-1):
  for j in range(18,-1,-1):
    c25[i][j] += c25[i+1][j]+c25[i][j+1]-c25[i+1][j+1]

ans = 0
for i in range(n):
  ans += c25[18-p2[i]][18-p5[i]]
  if p2[i] >= 9 and p5[i] >= 9:
    ans -= 1
print(ans//2)
### BUGGY CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
max_l = 0
max_i = 0
ans = 0
if k == 1:
    a = max(l)
    print(a * (a + 1) / 2 / a)
else:
    for i in range(n - k + 1):
        hikaku = 0
        for j in range(k):
            hikaku += l[i+j]
        if max_l < hikaku:
            max_i = i
            max_l = hikaku
    for i in range(k):
        a = l[max_i + i]
        ans += a * (a + 1) / 2 / a
    print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
at = l[0]
ans = 0
max_i = 0
max_l = sum(l[:k])
hikaku = sum(l[:k])
if k == 1:
    a = max(l)
    print(a * (a + 1) / 2 / a)
else:
    for i in range(1, n - k + 1):
        hikaku = hikaku - at + l[i + k - 1]
        at = l[i]
        if max_l < hikaku:
            max_i = i
            max_l = hikaku
    for i in range(k):
        a = l[max_i + i]
        ans += a * (a + 1) / 2 / a
    print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  w=[]
  v=[]
  dp=[[0 for _ in range(W+1)] for __ in range(n+1)]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n)[::-1]:
    for j in range(W+1):

      if j<w[i]:
        dp[i][j]=dp[i+1][j]

      else:
        dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

  return dp[0][W]

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  w=[]
  v=[]
  dp=[[0 for _ in range(W+1)] for __ in range(n+1)]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n)[::-1]:
    for j in range(W+1):

      if j<w[i]:
        dp[i][j]=dp[i+1][j]

      else:
        dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

  return dp[0][W]

# main()
print(main())