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

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, M = mi()

lim = M // N
ans = 1

for i in range(1, lim+1):
    amari = M % i
    if not amari % i:
        ans = i

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N, M = mi()
yakusu = make_divisors(M)
lim = M // N
ind = bisect.bisect_right(yakusu, lim)
ans = 1

for i in reversed(range(1, ind)):
    amari = M % yakusu[i]
    if not amari:
        ans = yakusu[i]
        break

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

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

B = set(A)
t = 0
for i in B:
    s = A.count(i)
    if s >= i:
        t += s - i
    else:
        t += s
print(t)

### FIXED CODE ###

n = int(input())

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

import collections

C = collections.Counter(A)
t = 0
for i in C:
    if C[i] >= i:
        t += C[i] - i
    else:
        t += C[i]
print(t)
### BUGGY CODE ###

N,M=map(int,input().split())
from collections import defaultdict,deque
branch=defaultdict(dict)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a-1][b-1]=c
check=deque([({0:0},[0])])
inf=10**15
ans=-inf
while len(check)>0:
    scores,visited=check.popleft()
    now=visited[-1]
    for nex,s in branch[now].items():
        if nex==N-1:
            ans=max(ans,scores[now]+s)
        if nex not in visited:
            scores[nex]=scores[now]+s
            check.append((scores,visited+[nex]))
        elif scores[now]>=inf:
            continue
        elif scores[now]+s>scores[nex]:
            scores[nex]=inf
            check.append((scores,[nex]))
if ans>=inf:
    print('inf')
else:
    print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
big=10**13
data=[-1*float('inf')]*(N+1)
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
from collections import deque
check=deque()
check.append((1,0,set()))
data[1]=0
while len(check)>0:
    now=check.popleft()
    for b,c in branch[now[0]]:
        if now[1]+c>data[b]:
            if data[b]>big:continue
            if b in now[2]:
                data[b]=float('inf')
                check.append((now[0],float('inf'),now[2]|{now[0],b}))
                check.append((b,float('inf'),now[2]|{now[0],b}))
            else:
                data[b]=now[1]+c
                check.append((b,now[1]+c,now[2]|{now[0],}))
if data[N]>big:print('inf')
else:print(data[N])
### BUGGY CODE ###

s = input()
turn = 1
k = -1
while 1:
    for i in range(len(s)-2):
        if s[i] != s[i+2]:
            k = i
            if i < len(s) - 3:
                if s[i+1] == s[i+3]:
                    s = s[:i+1] + s[i+2:]
                    turn += 1
                    break
            if i > 0:
                if s[i+1] == s[i-1]:
                    s = s[:i+1] + s[i+2:]
                    turn += 1
                    break
    else:
        if k != -1:
            s = s[:k+1] + s[k+2:]
            turn += 1
            k = -1
        else:
            break
if turn%2 == 0:
    print("First")
else:
    print("Second")


        


### FIXED CODE ###

s = input()
turn = len(s)
if s[0] == s[turn-1]:
    turn += 1
if turn & 1:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

n,k = map(int,input().split())
a =list(map(int,input().split()))
b = []
c = 1
for i in range(0,k):
  c *= a[i]
b.append(c)
for i in range(0, n-k):
  b.append(b[i]*a[i+k]//a[i])
for j in range(1, len(b)):
  if b[j-1] < b[j]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k = map(int,input().split())
a =list(map(int,input().split()))
for i in range(0, len(a)-k):
  if a[i] < a[i+k]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

s = input()
n = len(s)
mod = 2019

cum = [0]*n
cum[n-1] = int(s[-1]) % mod
d = 10
for i in range(0, n-1)[::-1]:
    a = int(s[i]) * d % mod
    cum[i] = (cum[i+1]+a) % mod
    d *= 10
cnt = [0]*mod

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
mod = 2019

cum = [0]*n
cum[n-1] = int(s[-1]) % mod
d = [1]*n
for i in range(n-1)[::-1]:
    d[i] = d[i+1]*10%mod

for i in range(0, n-1)[::-1]:
    a = int(s[i]) * d[i] % mod
    cum[i] = (cum[i+1]+a) % mod
cnt = [0]*mod

ans = 0
for i in cum[::-1]:
    ans += cnt[i]
    cnt[i] += 1
    if i == 0:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
suma = [0 for i in range(n)]
for i in range(n):
    suma[i] = suma[i-1] + a[i]
ans = 0
for i in range(n):
    if suma[i] == 0:
        ans += 1
    for j in range(i):
        if suma[i]-suma[j] == 0:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

ans = 0
sum = [0 for i in range(n+1)]

for i in range(1, n+1):
    sum[i] = sum[i-1] + a[i-1]

count = Counter(sum)

for values in count.values():
    if values >= 2:
        ans += values * (values-1) // 2

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

from collections import deque

def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        src, dst = map(int, input().split())
        graph[dst].append(src)

    dist = [0] * (n+1)
    for node in range(1, n+1):
        visited = [False] * (n+1)
        q = deque([node])
        while q:
            at = q.popleft()
            visited[at] = True
            for to in graph[at]:
                dist[to] = max(dist[to], dist[at] + 1)
                if not visited[to]:
                    q.append(to)
    print(max(dist[1:]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque

def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    parents = [0] * (n+1)
    for _ in range(m):
        src, dst = map(int, input().split())
        graph[src].append(dst)
        parents[dst] += 1

    q = deque()
    for i in range(1, n+1):
        if parents[i] == 0:
            q.append(i)

    dists = [0] * (n+1)
    for i in q:
        dists[0] = 0

    while q:
        at = q.popleft()
        for to in graph[at]:
            parents[to] -= 1
            if parents[to] == 0:
                q.append(to)
                dists[to] = dists[at] + 1

    print(max(dists[1:]))


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

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

s = s_in()
q = n_in()

d = True

pre = ''
suf = ''

for _ in range(q):
    query = s_in()
    if len(query) == 1:
        d = not d
        pass
    else:
        _, f, c = query.split()
        if d:
            if f == '1':
                pre = c + pre
            else:
                suf = suf + c
        else:
            if f == '1':
                suf = suf + c
            else:
                pre = c + pre


if d:
    print(pre+s+suf)
else:
    print(suf[::-1]+s[::-1]+pre[::-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

s = s_in()
q = n_in()

d = True

pre = []
suf = []

for _ in range(q):
    query = s_in()
    if len(query) == 1:
        d = not d
    else:
        _, f, c = query.split()
        if d:
            if f == '1':
                pre.append(c)
            else:
                suf.append(c)
        else:
            if f == '1':
                suf.append(c)
            else:
                pre.append(c)

s = "".join(pre[::-1]) + s + "".join(suf)

if d:
    print(s)
else:
    print(s[::-1])
### BUGGY CODE ###

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = input()
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(list(tmp))

que = []

for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que.copy()
while len(que) != H * W:
    tmp = next_que.copy()
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(tmp)

que = []
for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que
while len(que) != H * W:
    tmp = next_que
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter


def bfs(start):
    queue = deque([start])
    dist = [-1] * n
    dist[start] = 0
    while queue:
        v = queue.popleft()
        for nv in graph[v]:
            if dist[nv] != -1:
                continue
            queue.append(nv)
            dist[nv] = dist[v] + 1
    return dist


n, x, y = map(int, input().split())
# 0-indexed nodes
x -= 1
y -= 1

graph = defaultdict(set)
for i in range(n - 1):
    graph[i].add(i + 1)
    graph[i + 1].add(i)
graph[x].add(y)
graph[y].add(x)

dic = defaultdict(int)
for i in range(n):
    for k, v in Counter(bfs(i)).items():
        dic[k] += v

[print(dic[i] // 2) for i in range(1, n)]


### FIXED CODE ###

from collections import defaultdict

n, x, y = map(int, input().split())
x -= 1
y -= 1

circle = y - x + 1
a = [0 for _ in range(circle)]
for i in range(1, circle // 2 + 1):
    a[i] = i
    a[-i] = i

dists = defaultdict(int)
for i in range(n - 1):
    if i >= y:
        for j in range(i + 1, n):
            dists[j - i] += 1
    elif x < i < y:
        for j in a[1:y - i + 1]:
            dists[j] += 1
        for j in range(1, n - y):
            dists[a[y - i] + j] += 1
    else:
        # i <= x
        for j in range(i + 1, x):
            dists[j - i] += 1
        for j in a:
            dists[x - i + j] += 1
        for j in range(1, n - y):
            dists[x - i + a[-1] + j] += 1

for i in range(1, n):
    print(dists[i])
### BUGGY CODE ###

s = input()
k = int(input())

ss = set()
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        ss.add(s[i:j])

for i, s in enumerate(sorted(ss), start=1):
    if i == k:
        print(s)
        break


### FIXED CODE ###

s = input()
k = int(input())

ss = set()
for i in range(len(s)):
    for j in range(i+1, min(i+6, len(s)+1)):
        ss.add(s[i:j])

for i, s in enumerate(sorted(ss), start=1):
    if i == k:
        print(s)
        break
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(input().split(),dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],((A > x).astype(int)*2-1).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  B -= np.min(B) - 1
  M = B.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

left = 0 # 答はleftより大きいである
right = 10**9 # 答はright以下である
while right - left > 1:
  mid = (left+right)//2
  if test(mid):
    right = mid
  else:
    left = mid
    
answer = right
print(answer)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a>x else -1))
  m = min(B)-1
  B = [x-m for x in B]

  BIT = [0]*(N+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
answer = AA[right]

print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x <= y:
          return x
        else:
          return y

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res, seg[p])
            if q&1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 10**9+1

    # num: n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num

    init(A)

    ans = float('inf')
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += query(i-k, i+1)
            else:
                temp1 = query(0, i+1)
                temp2 = query(n-(k-i), n)
                if temp1 <= temp2:
                    t += temp1
                else:
                    t += temp2
        if t <= ans:
            ans = t
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

n, w = [int(i) for i in input().split()]
a = [0] * (w + 1)
for _ in range(n):
    b, c = [int(i) for i in input().split()]
    for i in reversed(range(w + 1)):
        if i + b >= w + 1:
            continue
        d = i + b
        a[d] = max(a[d], a[i] + c)
print(a[-1])


### FIXED CODE ###

n, w = [int(i) for i in input().split()]
a = [0] * (w + 1)
for _ in range(n):
    b, c = [int(i) for i in input().split()]
    for i in reversed(range(w + 1)):
        if i + b >= w + 1:
            continue
        d = i + b
        a[d] = max(a[d], a[i] + c)
print(a[-1])
### BUGGY CODE ###

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

A_dict = {}
for i in A_set:
    A_dict[i] = A.count(i)
A_dict = sorted(A_dict.items(), key=lambda x:x[1])

ans = 0
if len(A_set) > K:
    for i in range(len(A_set) - K):
        ans += A_dict[i][1]
        
print(ans)


### FIXED CODE ###

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

A_dict = {x:0 for x in A_set}
for i in A:
    A_dict[i] += 1
A_dict = sorted(A_dict.items(), key=lambda x:x[1])

ans = 0
if len(A_set) > K:
    for i in range(len(A_set) - K):
        ans += A_dict[i][1]
        
print(ans)
### BUGGY CODE ###

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

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
pq = [0 for _ in range(N)]
for _ in range(Q) :
    p, q = map(int, input().split())
    pq[p-1]  += q
    
visited = [False] * N
visited[0] = True

ret = [0] * N
def bfs(cur, score) :
    ret[cur] = score + pq[cur]
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, ret[cur])

bfs(0, 0)
    
print(*ret)

### FIXED CODE ###

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

N, Q = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    v[a-1].append(b-1)
    v[b-1].append(a-1)
    
pq = [0 for _ in range(N)]
for _ in range(Q) :
    p, q = map(int, input().split())
    pq[p-1] += q
    
visited = [False] * N
visited[0] = True

ret = [0] * N
def bfs(cur, score) :
    ret[cur] = score + pq[cur]
    for nex in v[cur] :
        if not visited[nex] :
            visited[nex] = True
            bfs(nex, ret[cur])

bfs(0, 0)
    
print(*ret)
### BUGGY CODE ###

N = int(input())
a = [sorted(list(input())) for _ in range(N)]

ans = 0
for n in range(1,N):
  if a[n] in a[:n]:
    ans += a[:n].count(a[n])
print(ans)

### FIXED CODE ###

N = int(input())
a = [''.join(sorted(list(input()))) for _ in range(N)]
import collections
c = collections.Counter(a)
c_ls = list(c.values())
ans = 0
for i in range(len(c_ls)):
  ans += c_ls[i] * (c_ls[i]-1)//2
print(ans)
### BUGGY CODE ###

#powerful discount tickets
import bisect
n,m=map(int,input().split())
lists=list(map(int,input().split()))
lists=sorted(lists)
for _ in range(m):
    #m回この作業を繰り返す
    maxi=lists[-1]
    lists.remove(maxi)
    bisect.insort(lists,maxi/2)
ans=0
import math
for some in lists:
    ans+=math.floor(some)
print(ans)

### FIXED CODE ###

from bisect import bisect_right
import heapq
n,m=map(int,input().split())
lists=list(map(int,input().split()))
uselists=[]
for _ in lists:
    uselists.append(-_)

heapq.heapify(uselists)

cnt=0
while cnt<m:
    y=heapq.heappop(uselists)

    z=(-y)//2
    heapq.heappush(uselists,-z)
    

    cnt+=1
anslist=[]
for j in uselists:
    anslist.append(-j)
print(sum(anslist))
### BUGGY CODE ###

from collections import Counter
N = int(input())
Si = [input() for _ in range(N)]

count = 0
for i in range(0, N):
    C1 = Counter(Si[i])
    for j in range(i+1, N):
        if C1 == Counter(Si[j]):
            count += 1
        else:
            pass
print(int(count))            

### FIXED CODE ###

from collections import Counter
N = int(input())
S = ["".join(sorted(input())) for i in range(N)]
ans = 0
for i in Counter(S).values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    assert N == len(p)
    answer = 0
    for i in range(N-K+1):
        check = sum(list(map(lambda x: (1+x)/2, p[i:i+K])))
        if answer <= check:
            answer = check
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    answer = sum(p[0:K])
    r = answer
    for i in range(N-K):
        answer = answer - p[i] + p[i+K]
        r = max(r, answer)
    print((r+K)/2)


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

import numpy as np

n = int(input())

a = []
for _ in range(n):
    aa = input().split('.')
    aaa = int(aa[0])*10**9
    if len(aa) == 2:
        aaa += int(aa[1])*10**(9-len(aa[1]))
    a2, a5 = 0, 0
    while aaa % 2 == 0:
        a2 += 1
        aaa = aaa // 2
    while aaa % 5 == 0:
        a5 += 1
        aaa = aaa // 5
    a.append([a2, a5])

na = np.array(a)

ans = 0
for i, aa in enumerate(a):
    ans += np.count_nonzero((na[i+1:, 0] >= 18-aa[0]) & (na[i+1:, 1] >= 18-aa[1]))

print(ans)


### FIXED CODE ###

import numpy as np

n = int(input())

ans = 0
ma = np.zeros((19, 19), dtype=np.int)
for _ in range(n):
    aa = input().split('.')
    a2, a5 = 0, 0
    if len(aa) == 1:
        aaa = int(aa[0])
        a2, a5 = 9, 9
    else:
        aaa = int(aa[0]) * 10 ** 9
        aaa += int(aa[1])*10**(9-len(aa[1]))

    while aaa % 2 == 0:
        a2 += 1
        aaa = aaa // 2
    while aaa % 5 == 0:
        a5 += 1
        aaa = aaa // 5

    a2, a5 = min(a2, 18), min(a5, 18)

    oa2, oa5 = 18-a2, 18-a5
    ans += ma[oa2, oa5]

    ma[:a2+1, :a5+1] += 1

print(ans)