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

n,m=map(int,input().split())
val =[[]for _ in range(10**5+1)]
for _ in range(n):
	a,b=map(int,input().split())
	val[a].append(b)
mval = [0]*(10**5
+1)
for i in range(1,m+1):
	val[i].sort(reverse=True)
	mval[i] = val[i][0] if val[i] else 0
ans = 0
for dayleft in range(1,m+1):
	cidx = mval.index(max(mval[1:dayleft+1]))
	if cidx == 0:
		continue
	ans += mval[cidx]
	del val[cidx][0]
	mval[cidx] = 0 if val[cidx]==[] else val[cidx][0]

print(ans)

### FIXED CODE ###

from heapq import heappush, heappop
n,m=map(int,input().split())
works = []
for _ in range(n):
	a,b=map(int,input().split())
	if a>m:
		continue
	works.append((a,b))
works.sort(reverse=True)
q=[]
ans=0

for dayleft in range(1,m+1):
	while works and works[-1][0]<=dayleft:
		a,b=works.pop()
		heappush(q,-b)
	if q:
		b = -heappop(q)
		ans+=b
print(ans)
### BUGGY CODE ###

def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        else:
            for j in range(N):
                if dp[i]+AB[j][1] < dp[i+AB[j][0]]:
                    dp[i+AB[j][0]] = dp[i]+AB[j][1]
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


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

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

def main():
    N=int(input())  #数値入力 「N」だけの入力のとき
    H=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
    ans = 0
    a = 0
    for i in range(N):
        a = 0
        for j in range(N-i):
            if i+j == N-1:
                if a > ans:
                    ans = a
                break
            elif H[i+j] >= H[i+j+1]:
                a += 1
            else:
                if a > ans:
                    ans = a
                break
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
H = [int(x) for x in input().split()]
ans = 0
cnt = 0
for ind,i in enumerate(H[:-1]):
    if(i>=H[ind+1]):
        cnt += 1
    else:
        cnt = 0
    ans = max(ans,cnt)
print(ans)
### BUGGY CODE ###

from collections import deque

N = int(input())
EhasV = [set() for x in range(N)]
EE = [0] * (N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    EE[i] = {a,b}
    EhasV[a].add(i)
    EhasV[b].add(i)

K = len(max(EhasV,key=len))
Vcolor = [set(range(1,K+1)) for x in range(N)]

Ecolor = [-1] * (N-1)

q = deque()
q.append(0)
while q:
    v1 = q.pop()
    for e in EhasV[v1]:
        if Ecolor[e] != -1:
            continue
        color = Vcolor[v1].pop()
        Ecolor[e] = color
        edgeside = EE[e]
        edgeside.discard(v1)
        v2 = edgeside.pop()
        Vcolor[v2].discard(color)
        q.append(v2)

print(*([K]+Ecolor),sep='\n')

### FIXED CODE ###

from collections import deque

N = int(input())
EhasV = [set() for x in range(N)]
EhasVnums = [0] * N
EE = [0] * (N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    EE[i] = {a,b}
    EhasV[a].add(i)
    EhasV[b].add(i)
    EhasVnums[a] += 1
    EhasVnums[b] += 1

K = len(max(EhasV,key=len))
Vcolor = [set(range(1,EhasVnums[x]+1)) for x in range(N)]
Ecolor = [-1] * (N-1)

q = deque()
q.append(0)
while q:
    v1 = q.pop()
    for e in EhasV[v1]:
        if Ecolor[e] != -1:
            continue
        color = Vcolor[v1].pop()
        Ecolor[e] = color
        edgeside = EE[e]
        edgeside.discard(v1)
        v2 = edgeside.pop()
        Vcolor[v2].discard(color)
        q.append(v2)

print(*([K]+Ecolor),sep='\n')
### BUGGY CODE ###

N=int(input())

li=[]
l=0
m=0

for i in range(N//2):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))



### FIXED CODE ###

import math 

N=int(input())

li=[]
l=0
m=0

for i in range(math.floor(math.sqrt(N))):
  if N%(i+1)==0:
    l=i
    m=N/(i+1)-1
    li.append(l+m)
  else:
    pass

print(int(min(li)))
### BUGGY CODE ###

N = int(input())
num = list(map(int,input().split()))
a = 1
for n in num:
  a = n*a
if a> 10**18:
  a=-1
print(a)

### FIXED CODE ###

import sys
N = int(input())
num = list(map(int,input().split()))
num.sort(reverse=True)
a = 1
if num[-1] == 0:
  print(0)
else:
  for n in range(N):
    a = num[n]*a
    if a> 10**18:
      print(-1)
      sys.exit()
  print(a)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    x,y = i, (n//i)*i
    ans += ((n//i)*(x+y)//2)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n+1):
    x,y = i, (n//i)*i
    ans += ((n//i)*(x+y)//2)
print(ans)
### BUGGY CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
def check(x):
  if x==0:
    return 0
  else:
    t=0
    for i in range(N):
      t+=math.ceil(A[i]/x)-1
    if t<=K:
      return 10
    else:
      return 0
low=1
high=max(A)
sig=(low+high)//2
tf=0
if K==0:
  tf=1
  ans=high
while tf==0:
  if check(sig)==10:
    if check(sig-1)==0:
      ans=sig
      break
    else:
      high=sig-1
      sig=(low+sig)//2
  else:
    low=sig+1
    sig=(high+sig)//2
print(ans)

### FIXED CODE ###

import math
N,K=map(int,input().split())
A=list(map(int,input().split()))
def check(x):
  if x==0:
    return 0
  else:
    t=0
    for i in range(N):
      t+=math.ceil(A[i]/x)-1
    if t<=K:
      return 10
    else:
      return 0
low=0
high=max(A)
sig=(low+high)//2
tf=0
if K==0:
  tf=1
  ans=high
while tf==0:
  if check(sig)==10:
    if check(sig-1)==0:
      ans=sig
      break
    else:
      high=sig-1
      sig=(low+high)//2
  else:
    low=sig+1
    sig=(high+low)//2
print(ans)
### BUGGY CODE ###

import collections

def solve(K, r):
    dic = collections.defaultdict(set)
    for i, n in enumerate(r):
        dic[n].add(i)
    ans = 0
    for i, n in enumerate(r):
        for k in range(i,K):
            target_sum = abs(k-i)-n
            if k in dic[target_sum]:
                ans+=1
    return ans
k = int(input())
r = list(map(int, input().split()))
print(solve(k, r))

### FIXED CODE ###

import collections

def solve(k, r):
    count = {}
    ans = 0
    for i, n in enumerate(r):
        target = i-n
        ans += count.get(target, 0)
        count[i+n] = count.get(i+n, 0)+1
    return ans
k = int(input())
r = list(map(int, input().split()))
print(solve(k, r))
### BUGGY CODE ###

a,b,x = map(int, input().split())
count = 0
for i in range(a,b+1) :
    if i % x == 0 :
        count += 1
print(count)


### FIXED CODE ###

a,b,x = map(int, input().split())
ans = max((b//x) - ((a-1)//x), 0)
print(ans)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(0,n+1,r):
    for j in  range(0,n+1,g):
        if (n - i - j)%b == 0 and (n - i - j)/b >= 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(0,n+1,r):
    for j in range(0,n+1-i,g):
        if (n - i - j)%b == 0 and (n - i - j)%b >= 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
numbers = list(map(int,input().split()))
numOfOperation = int(input())
sums = sum(numbers)
for i in range(numOfOperation):
    B,C = map(int,input().split())
    cnt = 0
    for j in range(len(numbers)):
        if numbers[j] == B : 
            cnt += 1
            numbers[j] = C
    sums += cnt * (C - B)
    print(sums)


### FIXED CODE ###

N = int(input())
numbers = list(map(int,input().split()))
numOfOperation = int(input())
dic = {}

for num in numbers:
    if num in dic : dic[num] += 1
    else: dic[num] = 1
    

sums = sum(numbers)
for i in range(numOfOperation):
    B,C = map(int,input().split())
    if (B in dic) : 
        cnt = dic[B]
        dic[B] = 0
        if (C not in dic) : dic[C] = cnt
        else : dic[C] += cnt
        sums += cnt * (C - B)
    print(sums)
### BUGGY CODE ###

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


def make_cmb_table(n):
    fact = [1]
    for i in range(1, n+1):
        fact.append(fact[i-1] * i)

    ifact = [0] * (n+1)
    ifact[n] = pow(fact[n], -1)
    for i in range(n, 0, -1):
        ifact[i-1] = ifact[i] * i
    return (fact, ifact)


def cmb(n, r, table):
    if r > n:
        return 0
    return int(table[0][n] * table[1][n - r] * table[1][r])


def main():
    n = int(input())
    a = list(map(str, input().split()))
    table = make_cmb_table(n)

    d = dict()
    for i in range(n):
        if a[i] in d:
            d[a[i]] = d[a[i]] + 1
        else:
            d[a[i]] = 1

    total = 0
    normal = dict()
    target = dict()
    for k, v in d.items():
        t = cmb(v, 2, table)
        normal[k] = t
        target[k] = cmb(v-1, 2, table)
        total += t

    for i in range(n):
        print(total - normal[a[i]] + target[a[i]])


main()


### FIXED CODE ###

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


def main():
    n = int(input())
    a = list(map(str, input().split()))

    d = dict()
    for i in range(n):
        if a[i] in d:
            d[a[i]] = d[a[i]] + 1
        else:
            d[a[i]] = 1

    total = 0
    normal = dict()
    target = dict()
    for k, v in d.items():
        if v == 1:
            normal[k] = 0
            target[k] = 0
        else:
            normal[k] = (v-1) * ((v-1) + 1) // 2
            target[k] = normal[k] - (v-1)
            total += normal[k]

    for i in range(n):
        print(total - normal[a[i]] + target[a[i]])


main()
### BUGGY CODE ###

n = int(input())
str_dic = {}
for _ in range(n):
    inp = input()
    if inp in str_dic:
        str_dic[inp] += 1
    else:
        str_dic[inp] = 1

max_str = [s[0] for s in str_dic.items() if s[1] == max(str_dic.values())]

sorted_max_str = sorted(max_str)

for s in sorted_max_str:
    print(s)


### FIXED CODE ###

n = int(input())
str_dic = {}
for _ in range(n):
    inp = input()
    if inp in str_dic:
        str_dic[inp] += 1
    else:
        str_dic[inp] = 1

max_num = max(str_dic.values())

max_str = [s[0] for s in str_dic.items() if s[1] == max_num]

for s in sorted(max_str):
    print(s)
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(1,N+1):
    for j in range(1,N):
        if i <=j:
            break
        for k in range(1,N):
            if i <=k or i<= k+j:
                break
            for l in range(1,N):
                if i <=l or i < k+j+l:
                    break
                if l**2+j**2+k**2+l*j+j*k+k*l==i:
                    ans+=1
    print(ans)
    ans=0

### FIXED CODE ###

N=int(input())

ans=[0]*N

for i in range(1,int(N**0.5)):
    if i**2 >=N:
        break
    for j in range(1,int(N**0.5)):
            if i**2+j**2+i*j>=N:
                break
            for k in range(1,int(N**0.5)):
                    if i**2+j**2+k**2+i*j+j*k+k*i <=N:
                        ans[i**2+j**2+k**2+i*j+j*k+k*i-1] +=1

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

def main():
    s=input()
    t=input()
    dp=[[""]*(len(t)+1) for _ in range(len(s)+1)]
    for i in range(1,len(s)+1):
        for j in range(1,len(t)+1):
            if s[i-1]==t[j-1]:
                dp[i][j]=dp[i-1][j-1]+s[i-1]
            else:
                if len(dp[i-1][j])>=len(dp[i][j-1]):
                    dp[i][j]=dp[i-1][j]
                else:
                    dp[i][j]=dp[i][j-1]
                    
    print(dp[len(s)][len(t)])
if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    s=input()
    t=input()
    dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
    for i in range(1,len(s)+1):
        for j in range(1,len(t)+1):
            if s[i-1]==t[j-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    i=len(s)
    j=len(t)
    result=[]
    while i!=0 and j!=0:
        if dp[i][j]==dp[i-1][j]:
            i-=1
        elif dp[i][j]==dp[i][j-1]:
            j-=1
        elif dp[i][j]==dp[i-1][j-1]+1:
            result.append(s[i-1])
            i-=1
            j-=1
    s="".join(result)
    s=s[::-1]
    print(s)
if __name__=="__main__":
    main()
### BUGGY CODE ###

N = int(input())


def f(n):
    res = 0
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):
                tmp = x*x + y * y + z*z + x * y + y*z + z*x
                if tmp == n:
                    res += 1
                elif tmp > n:
                    break
    return res


for i in range(1, N+1):
    print(f(i))


### FIXED CODE ###

import math
N = int(input())


def f(n):
    m = int(math.sqrt(n)+0.5)
    res = 0
    for x in range(1, m+1):
        for y in range(x, m+1):
            k = n - (x * x + y * y + x * y)
            if k < 1:
                break
            l = y
            r = m+1
            while r - l > 1:
                z = (r + l) // 2
                tmp = (x + y + z) * z
                if tmp <= k:
                    l = z
                else:
                    if r == z + 1:
                        r -= 1
                    else:
                        r = z + 1
            if (x+y+l) * l == k:
                s = set()
                s.add(x)
                s.add(y)
                s.add(l)
                if len(s) == 3:
                    res += 6
                elif len(s) == 2:
                    res += 3
                else:
                    res += 1
    return res


for i in range(1, N+1):
    print(f(i))
### BUGGY CODE ###

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

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

    if 0 in A:
        print(0)
        exit()

    if x > 10 ** 18:
        print(-1)
        exit()

print(x)


### FIXED CODE ###

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

if 0 in A:
        print(0)
        exit()

x = 1
for i in range(N):
    x = x * A[i]
        
    if x > 10 ** 18:
        print(-1)
        exit()

print(x)
### BUGGY CODE ###

N, Q = [int(i) for i in input().split()]
S = input()

cs = []
for i in range(1, 1 + N):
  cs.append(S[:i].count('AC'))

for l, r in ([int(i) for i in input().split()] for _ in range(Q)):
  print(cs[r - 1] - cs[l - 1])


### FIXED CODE ###

N, Q = [int(i) for i in input().split()]
S = input()
lrs = [[int(i) for i in input().split()] for _ in range(Q)]


cache = {1: {'c': 0, 'm': False}}
cnt = 0
for i in range(1, N):
    if S[i - 1]+S[i] == 'AC':
        cnt += 1
    cache[i + 1] = {'c': cnt, 'm': True}

for l, r in lrs:
    print(cache[r]['c'] - cache[l]['c'])
### BUGGY CODE ###

import sys
N = int(input())

for h in range(1, 3501):
    for n in range(1, h+1):
        if (4/N - 1/h - 1/n) == 0: continue
        w = 1 // (4/N - 1/h - 1/n)
        if 0 < w and 4/N == 1/h + 1/n + 1/w:
            print(h, n, int(w))
            sys.exit()


### FIXED CODE ###

import sys

N = int(input())
for h in range(1, 3501):
    for n in range(1, h+1):
        if (4*h*n - N*h - N*n) <= 0:
            continue
        w_int = N*h*n // (4*n*h - N*h - N*n)
        w_float = N*h*n / (4*n*h - N*h - N*n)
        if w_int == w_float:
            print(h, n, w_int)
            sys.exit()
### BUGGY CODE ###

#
import sys
import math
import numpy as np
import itertools


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

# リストに入れる
a = [int(i) for i in input().split()] 

# n行複数列の数をリストに
bc = [[int(i) for i in input().split()] for i in range(m)] 

bc=sorted(bc, key=lambda x: -x[1])
a=sorted(a)
x = []

for i in range(m):
    for j in range(bc[i][0]):
        x.append(bc[i][1])
        if len(x)>=n:
            break
    if len(x)>=n:
        break
pmax = min(n,len(x))
z=0
for i in range(pmax+1):
    y=0
    for j in range(0,i):
        y += x[j]
    for j in range(i,n):
        y += a[j]
    z=max(y,z)

print(z)


### FIXED CODE ###

#
import sys
import math
import numpy as np
import itertools


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

# リストに入れる
a = [int(i) for i in input().split()] 

# n行複数列の数をリストに
bc = [[int(i) for i in input().split()] for i in range(m)] 

bc=sorted(bc, key=lambda x: -x[1])
a=sorted(a)
x = []

for i in range(m):
    for j in range(bc[i][0]):
        x.append(bc[i][1])
        if len(x)>=n:
            break
    if len(x)>=n:
        break
pmax = min(n,len(x))
z=0
y=0
# no replace
for i in range(n):
    y += a[i]
z=y
# replacing one by one
for i in range(pmax):
    y += x[i]
    y -= a[i]
    z=max(y,z)

print(z)
### BUGGY CODE ###

n, k = map(int, input().split())

a = []
b = []
for i in range(n):
    tmp1, tmp2 = map(int, input().split())
    a.append(tmp1)
    b.append(tmp2)

p_list = []
t = zip(a, b)
ts = sorted(t)
a, b = zip(*ts)
for ai, bi in zip(a, b):
    for i in range(bi):
        p_list.append(ai)

print(p_list[k-1])




### FIXED CODE ###

n, k = map(int, input().split())

a = []
b = []
for i in range(n):
    tmp1, tmp2 = map(int, input().split())
    a.append(tmp1)
    b.append(tmp2)

p_list = []
t = zip(a, b)
ts = sorted(t)
a, b = zip(*ts)
ans = 0
count = 0
for ai, bi in zip(a, b):
    count += bi
    if count >= k:
        ans = ai
        break

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

import math

def IsPrimer(num):
	if num == 1:
		isprimer = False
	else:
		isprimer = True
		for divisor in range(2, int(math.sqrt(num)) + 1):
			if num % divisor == 0:
				isprimer = False
				break
	return isprimer

while True:
	try:
		num = eval(input())
		count = 0
		for i in range(2, num + 1):
			if IsPrimer(i):
				count += 1
		print(count)
	except EOFError:
		break

### FIXED CODE ###

# sieve of Eratosthenes
N = 1000000
isprimer = [True for i in range(N)]
isprimer[0], isprimer[1] = False, False
for i in range(2, N):
	if not isprimer[i]:
		continue
	for j in range(i * 2, N, i):
		isprimer[j] = False

while True:
	try:
		num = eval(input())
		count = 0
		for i in range(2, num + 1):
			if isprimer[i]:
				count += 1
		print(count)
	except EOFError:
		break
### BUGGY CODE ###

import numpy as np
n, m = map(int, input().split())
a = list(map(int, input().split()))
l = np.array(a)
for i in range(m):
    idx = l.argmax()
    l[idx] = l[idx]//2
print(sum(l))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
for _ in range(m):
    t = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-t//2))
print(-sum(a))
### BUGGY CODE ###

x = input()
while "ST" in x:
  x=x.replace("ST","")
print(len(x))

### FIXED CODE ###

x = input()
scount, tcount, c = 0, 0, 0
for i in range(len(x)):
  if x[c]=="S":
    scount+=1
  else:
    if scount>0:
      scount-=1
    else:
      tcount+=1
  c+=1
print(tcount*2)
### BUGGY CODE ###

import sys
import functools
import itertools
import math

def bfs(H, W, S):
    cost = [[0]*(W+2) for _ in range(H+2)]
    visited = []
    unvisited = [(1,1)]
    cost[1][1] = 1
    while unvisited:
        now = unvisited[0]
        unvisited = unvisited[1:]
        visited.append(now)
        if S[now[1]-1][now[0]] != '#' and (now[0], now[1]-1) not in visited:
            cost[now[1]-1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]-1))
        if S[now[1]+1][now[0]] != '#' and (now[0], now[1]+1) not in visited:
            if now[1]+1 == H and now[0] == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]+1][now[0]] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0], now[1]+1))
        if S[now[1]][now[0]-1] != '#' and (now[0]-1, now[1]) not in visited:
            cost[now[1]][now[0]-1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]-1, now[1]))
        if S[now[1]][now[0]+1] != '#' and (now[0]+1, now[1]) not in visited:
            if now[1] == H and now[0]+1 == W:
                return cost[now[1]][now[0]] + 1
            cost[now[1]][now[0]+1] = cost[now[1]][now[0]] + 1
            unvisited.append((now[0]+1, now[1]))
    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.insert(H+1,'#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def bfs(H, W, S):
    visited = [[False]*(W+2) for _ in range(H+2)]
    visited[1][1] = True
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            for t1, t2 in zip([-1,+1,0,0],[0,0,-1,1]):
                dx = x + t1
                dy = y + t2
                if S[dy][dx] != '#' and not visited[dy][dx]:
                    if dy == H and dx == W:
                        return dist
                    un.append((dx,dy))
                    visited[dy][dx] = True
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.append('#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

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

N = int(input())
A = []
A2 = []
A5 = []
for i in range(N):
    a=input()
    tmp = int(a.replace('.', ''))
    count2 = 0
    count5 = 0
    for _ in range(18):
        if tmp % 2 == 0:
            count2 += 1
            tmp /= 2
        else:
            break
    for _ in range(18):
        if tmp % 5 == 0:
            count5 += 1
            tmp /= 5
        else:
            break
    if a.find('.') > 0:
        count2 += 10 - len(a) + a.find('.')
        count5 += 10 - len(a) + a.find('.')
    else:
        count2 += 9
        count5 += 9
    A2.append(count2)
    A5.append(count5)
ans=0
for i in range(N):
    for j in range(i+1,N):
        if A2[i] + A2[j] >= 18 and A5[i] + A5[j] >= 18:
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
a = [[0 for j in range(19)] for i in range(19)]
ans=0
for _ in range(N):
    A=input()
    if A.find('.') > 0:
        count2 = 10 - len(A) + A.find('.')
        count5 = 10 - len(A) + A.find('.')
    else:
        count2 = 9
        count5 = 9
    tmp = int(A.replace('.', ''))
    while count2 < 18:
        if tmp % 2 == 0:
            count2 += 1
            tmp //= 2
        else:
            break
    while count5 < 18:
        if tmp % 5 == 0:
            count5 += 1
            tmp //= 5
        else:
            break
    for i in range(18-count2,19):
        for j in range(18-count5,19):
            ans += a[i][j]
    a[count2][count5] += 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
h_s = list(map(int, input().split()))+[0]*K
# print(h_s)
dp = [float("inf")]*(N+K)
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i]+abs(h_s[i]-h_s[i+j]))

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h_s = list(map(int, input().split()))+[0]*K
# print(h_s)
dp = [float("inf")]*(N+K)
dp[0] = 0
 
for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i]+abs(h_s[i]-h_s[i+j]))
 
print(dp[N-1])
### BUGGY CODE ###

N = int(input())
for h in range(1, 3501):
    for w in range(1, 3501):
        b = 4*h*w - N*(h+w)
        if b == 0: continue
        a = N*h*w
        n = a//b
        r = a%b
        if r == 0 and n > 0:
            print(h, n, w)
            exit()

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for w in range(1, 3501):
        b = 4*h*w - N*(h+w)
        if b == 0: continue
        a = N*h*w
        n = a//b
        r = a%b
        if r == 0 and n > 0:
            print(h, n, w)
            exit()