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

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[]
C=[]
for ai in range(len(A)):
    if A[ai]<0:
        B.append(A[ai])
    else:
        C.append(A[ai])
s=len(B)*len(C)
if K<=s:
    D=[]
    for bi in range(len(B)):
        for ci in range(len(C)):
            D.append(B[bi]*C[ci])
    D.sort()
    print(D[K-1])
else:
    E=[]
    for bi in range(len(B)):
        for bj in range(bi+1,len(B)):
            E.append(B[bi]*B[bj])
    for ci in range(len(C)):
        for cj in range(ci+1,len(C)):
            E.append(C[ci]*C[cj])
    E.sort()
    print(E[K-s-1])

### FIXED CODE ###

n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0

# 負数の数(nc)、0の数(zc)、正数の数(pc)を数える
for i in range(n):
 if arr[i]<0:
   nc+=1
 elif arr[i]==0:
   zc+=1
 else:
   pc+=1

# 積が負となるペアの個数を求める
ncc=nc*pc
# 積が0となるペアの個数を求める
zcc=zc*(nc+pc)+(zc*(zc-1))//2
# 積が正となるペアの個数を求める
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2

# K番目の値が負の場合
if k <= ncc:
 arr1=[]
 arr2=[]
 # 負数、正数をそれぞれ昇順に並べる
 for i in range(n):
   if arr[i] < 0:
     arr1.append(-arr[i])
   elif arr[i] > 0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l = 0         # left
 r = 10**18+1  # right 答えでもある
 # 負数のマイナスを取って計算しているため積の大小が逆転するので、大きなほうからK番目
 # 小さなほうから(積が負となるペアの個数-K)番目の値を求める
 k = ncc-k
 while r-l != 1: # rとlが1違い、すなわちrが答えとなるまで繰り返す
   mid=(l+r)//2 # 区間の中間値を更新
   cnt=0
   pos=c2-1
   # 区間[left, right)でのしゃくとり法
   # 各負数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる
   for i in range(c1):
     while pos!=-1:
       if arr2[pos] > mid//arr1[i]:
         pos-=1
       else:
         break        
     cnt+=pos+1
   # 勝手に決めた値mid以下の個数が(積が負となるペアの個数-K)個以上であれば真の値はmid以下
   if cnt > k:
     r = mid  # rightをmidに更新してやり直し
   # そうでなければ真の値はmid以上
   else:
     l = mid  # leftをmidに更新してカウントやり直し
 # 負数のマイナスを取って計算したので最後にマイナスを付けて出力する
 print(-r)

# K番目の値が0の場合
elif k <= (ncc+zcc):
 print(0)

# K番目の値が正の場合
else:
 arr1=[]
 arr2=[]
 for i in range(n): #負数、正数をそれぞれ昇順に並べる
   if arr[i] < 0:
     arr1.append(-arr[i])
   elif arr[i] > 0:
     arr2.append(arr[i])
 arr1=arr1[::-1]
 c1=len(arr1)
 c2=len(arr2)
 l=0
 r=10**18+1
 k -= (ncc+zcc) #正数の中で小さい順にK番目の数を調べたいので負数、0の数を取り除く
 while r-l != 1:
   mid=(l+r)//2
   cnt1=0
   pos1=c1-1
   # 各負数ごとに積が勝手に決めた値midよりも小さくなる負数の個数を求め足し合わせる(しゃくとり法)
   for i in range(c1):
     tmp=0
     while pos1 != -1:
       if arr1[pos1] > mid//arr1[i]:
         pos1-=1
       else:
         break
     tmp+=pos1+1
     # 各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
     if arr1[i]**2 < mid:
       tmp-=1
     cnt1+=tmp
   cnt1 = cnt1//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt2=0
   pos2=c2-1
   # 各正数ごとに積が勝手に決めた値midよりも小さくなる正数の個数を求め足し合わせる(しゃくとり法)
   for i in range(c2):
     tmp=0
     while pos2!=-1:
       if arr2[pos2] > mid//arr2[i]:
         pos2-=1
       else:
         break
     tmp+=pos2+1
     if arr2[i]**2 < mid:
       tmp-=1 #各要素について、自身を2回選んだ場合の積が勝手に決めた値mid以下なら条件を満たすペアの個数を1減らす
     cnt2+=tmp
   cnt2=cnt2//2 #上記の処理では同じペアが2回数えられているので個数を半分にする
   cnt=cnt1+cnt2
   if cnt >= k: #勝手に決めた値mid以下の個数がK個以上であれば真の値はmid以下
     r = mid
   else: #そうでなければ真の値はmid以上
     l = mid
 print(r)
### BUGGY CODE ###

def f():
    n,k = map(int,input().split())

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

#print(h)

    o = [0]* n

    for a in range(1,n):
        o[a] = min(o[b]+abs(h[a]-h[b]) for b in range(max(0,a-k),a))

    print(o[n-1])

f()

### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))
 
	dp=[0]*N
 
	for i in range(1,N):
		dp[i] = min(
			dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i)
		)
	print(dp[N-1])
main()
### BUGGY CODE ###

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] == INF:
          continue
        else:
            for j in magic:
                if i-j[0] < 0:
                    if ans[0] > ans[i]+j[1]:
                        ans[0] = ans[i]+j[1]
                elif ans[i-j[0]] > ans[i]+j[1]:
                    ans[i-j[0]] = ans[i]+j[1]
    return ans[0]
print(num())



### FIXED CODE ###

def num():
    from sys import stdin
    h, n = map(int, input().split())
    magic = [list(map(int, stdin.readline().split())) for _ in range(n)]
    INF = float('inf')
    ans = [INF]*(h+1)
    ans[-1] = 0

    for i in range(h, 0, -1):
        if ans[i] != INF:
            for j, k in magic:
                if i-j < 0:
                    num = ans[i]+k
                    if ans[0] > num:
                        ans[0] = num
                else:
                    num = ans[i]+k
                    if ans[i-j] > num:
                        ans[i-j] = num
    return ans[0]
print(num())
### BUGGY CODE ###

H,W=map(int, input().split())
S=[input() for i in range(H)]
s=[[0]*W for h in range(H)]
b=0
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            s[h][w]=-1
            b+=1
q=[]
i=1
q.append((0,0))
while (H-1,W-1) not in q:
    q2=[]
    for h,w in q:
        s[h][w]=i
        if h>0 and s[h-1][w]==0:
            q2.append((h-1,w))
        if h<H-1 and s[h+1][w]==0:
            q2.append((h+1,w))
        if w>0 and s[h][w-1]==0:
            q2.append((h,w-1))
        if w<W-1 and s[h][w+1]==0:
            q2.append((h,w+1))
    q=q2
    i+=1
print(H*W-i-b)

### FIXED CODE ###

H,W=map(int, input().split())
S=[input() for i in range(H)]
s=[[0]*W for h in range(H)]
b=0
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            s[h][w]=-1
            b+=1
q=[]
i=1
q.append((0,0))
s[0][0]=1
while (H-1,W-1) not in q:
    q2=[]
    i+=1
    for h,w in q:
        if h>0 and s[h-1][w]==0:
            q2.append((h-1,w))
            s[h-1][w]=i
        if h<H-1 and s[h+1][w]==0:
            q2.append((h+1,w))
            s[h+1][w]=i
        if w>0 and s[h][w-1]==0:
            q2.append((h,w-1))
            s[h][w-1]=i
        if w<W-1 and s[h][w+1]==0:
            q2.append((h,w+1))
            s[h][w+1]=i
    q=q2
    if len(q)==0:
        break
if len(q)==0:
    print(-1)
else:
    print(H*W-i-b)
### BUGGY CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = [LI() for _ in range(n)]
    r = [0] * (w+1)
    for a,b in aa:
        for i in range(w-a,-1,-1):
            if r[i+a] < b + r[i]:
                r[i+a] = b + r[i]

    return max(r)


print(main())


### FIXED CODE ###

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,w = LI()
    aa = sorted([LI() for _ in range(n)])
    r = [0] * (w+1)
    mx = 0
    for a,b in aa:
        mx += a
        for i in range(min(mx, w-a),-1,-1):
            if r[i+a] < b + r[i]:
                r[i+a] = b + r[i]

    return max(r)


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

N = int(input())

p = list(map(float, input().split()))

dp = [[0 for j in range(N+2)] for i in range(N+1)]
dp[0][1] = 1

for i in range(N):
    for j in range(i+2):
        dp[i+1][j+1] = dp[i][j+1] * (1 - p[i]) + dp[i][j] * p[i]

print(sum(dp[N][N + N//-2 + 2:]))


### FIXED CODE ###

N = int(input())

p = list(map(float, input().split()))

dp = [[0 for j in range(N+2)] for i in range(N+1)]
dp[0][1] = 1

for i in range(N):
    for j in range(i+2):
        dp[i+1][j+1] = dp[i][j+1] * (1 - p[i]) + dp[i][j] * p[i]

print(sum(dp[N][N + N//-2 + 2:]))
### BUGGY CODE ###

def psolve(k, Xs, N):
    arr = [[]]
    i = Xs[0]
    for x in Xs:
        if x <= i + k:
            arr[-1].append(x)
        else:
            arr.append([])
            arr[-1].append(x)
            i = x
            if len(arr) > N:
                break

    if len(arr) <= N:
        ans = sum([max(a) - min(a) for a in arr])
        return ans
    else:
        return 10 ** 9


def solve(N, M, Xs):
    Xs = sorted(Xs)
    ans = 10 ** 9
    for k in range(0, (Xs[-1] - Xs[0]) + 1):
        ans = min(ans, psolve(k, Xs, N))
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, M, Xs))


### FIXED CODE ###


def solve(N, M, Xs):
    Xs = sorted(Xs)
    diffs = sorted([Xs[i+1] - Xs[i] for i in range(M-1)], reverse=True)
    return Xs[-1] - Xs[0] - sum(diffs[:N-1])


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    Xs = list(map(int, input().split(" ")))
    print(solve(N, M, Xs))
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST(N)

mx = 0
for i in range(1, N+1):
    cnt = 0
    nxt = i
    for a in A:
        if a == nxt:
            cnt += 1
            nxt += 1
    mx = max(mx, cnt)
print(N - mx)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST(N)

B = [0] * N
for i, a in enumerate(A):
    B[a-1] = i

mx = cnt = 1
for i in range(N-1):
    if B[i] < B[i+1]:
        cnt += 1
    else:
        cnt = 1
    mx = max(mx, cnt)
print(N - mx)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
T=0
x=0
L=10**9+7

for i in range(0,N):
    for j in range(i+1,N):
        x=x+A[j]
    y=A[i]*x
    T+=y
    x=0

ans=T%L
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7 #先に書いておく

s=[0] #sのリスト(累積和)
for i in range(0,N): #累積和を作る
    s.append(s[i]+A[i])

sum=0
for j in range(0,N): #合計をだす
    sum+=A[j]*(s[N]-s[j+1])

ans=sum%MOD #10^9+7で割った余りが答え
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
li = [(int(j) + 1) / 2 for j in input().split()]
li2 = [sum(li[m:m+k]) for m in range(0, len(li) - k + 1, 1)]

print(max(li2))

### FIXED CODE ###

n, k = map(int, input().split())
li = [(int(j) + 1) / 2 for j in input().split()]

if k == 1:
  print(max(li))
else:
  a = 0
  for i in range(n-k+1):
    if i == 0:
      xe = sum(li[0:k])
    else:
      xe = xe - li[i-1] + li[i+k-1]
    a = max(a, xe)
  print(a)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
A = list(map(int, input().split()))
A_p = np.array([a + (i+1) for i, a in enumerate(A)])
A_m = np.array([a - (i+1) for i, a in enumerate(A)])
# print(A_p)
# print(A_m)
count = 0
for i in range(1, n+1):
    tmp = A_p[:i] + A_m[n-i:n]
    # print(tmp)
    # print(np.count_nonzero(tmp))
    tmp2 = A_p[n-i:n] + A_m[:i]
    count += len(tmp) - np.count_nonzero(tmp)
    count += len(tmp2) - np.count_nonzero(tmp2)

print(count)


### FIXED CODE ###

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(int)
for i in range(n):
    ap[i - a[i]] += 1

ans = 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)
### BUGGY CODE ###

A, B, N = map(int,input().split())
res = []
for x in range(1,N+1):
    res.append(int(A*x/B) - (A*int(x/B)))
print(max(res))

### FIXED CODE ###

A, B, N = map(int,input().split())
x = min(B-1,N)
res = int(A*x/B) - (A*int(x/B))
print(res)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
te=set(range(1,n+1))
for i in range(m):
    x,y=map(int,input().split())
    tes=set(range(x,y+1))
    te=te&tes
print(len(te))

### FIXED CODE ###

n,m=map(int,input().split())
l=1;ma=n
te=set(range(1,n+1))
for i in range(m):
    x,y=map(int,input().split())
    l=max(x,l)
    ma=min(ma,y)
print(abs(l-ma)+1 if l<=ma else 0)
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

import queue, itertools

dxy = ((1,0), (-1,0), (0,1), (0,-1))
ans = 0
for s, t in itertools.combinations(itertools.product(range(H), range(W)), 2):
    if S[s[0]][s[1]] == '#' or S[t[0]][t[1]] == '#': continue
    
    q = queue.Queue()
    seen = [[0]*W for _ in range(H)]
    dist = [[0]*W for _ in range(H)]     

    q.put(s)
    while not q.empty():
        v = q.get()
        x, y = v[1], v[0]
        seen[y][x] = 1
        for dx, dy in dxy:
            nx, ny = x+dx, y+dy
            if nx<0 or ny<0 or nx>=W or ny>=H or S[ny][nx] == '#' or seen[ny][nx] == 1: continue
            dist[ny][nx] = dist[y][x] + 1
            q.put((ny, nx))
    
    ans = max(ans, dist[t[0]][t[1]])

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

import queue, itertools

dxy = ((1,0), (-1,0), (0,1), (0,-1))
ans = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '#': continue
    
    q = queue.Queue()
    dist = [[-1]*W for _ in range(H)]     

    q.put(s)
    dist[s[0]][s[1]] = 0
    while not q.empty():
        y, x = q.get()         
        for dx, dy in dxy:
            nx, ny = x+dx, y+dy
            if nx<0 or ny<0 or nx>=W or ny>=H or S[ny][nx] == '#' or dist[ny][nx] >= 0: 
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.put((ny, nx))
    
    ans = max(ans, max(map(max, dist)))

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

from fractions import gcd
import sys 
input = sys.stdin.readline

def lcm(a,b):
    return a*b//gcd(a,b)

mod=10**9+7
N = int(input())
A = list(map(int,input().split()))

if N==1:
    print(1)
    exit()

Gcd = lcm(A[0],A[1])
ans = (Gcd//A[0]+Gcd//A[1])%mod
temp = Gcd//A[1]
#print(temp)

for i in range(1,N-1):
    Gcd = lcm(A[i],A[i+1])
    temp2 = Gcd//A[i]
    Gcd2 = lcm(temp,temp2)
    a = Gcd2//temp
    b = Gcd2//temp2

    temp = Gcd//A[i+1]*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod
    #Gcd %= mod
    c = A[i+1]
    d = Gcd//c
    d %= mod
    ans += d*b
    #ans += Gcd//A[i+1]*b
    ans %= mod


print(ans)






### FIXED CODE ###

from fractions import gcd
import sys 
input = sys.stdin.readline

def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return K*x

mod=10**9+7
N = int(input())
A = list(map(int,input().split()))

if N==1:
    print(1)
    exit()

Gcd = gcd(A[0],A[1])
ans = (A[0]//Gcd+A[1]//Gcd)%mod
temp = A[0]//Gcd

for i in range(1,N-1):
    #Gcd = lcm(A[i],A[i+1])
    Gcd = gcd(A[i],A[i+1])
    #temp2 = Gcd//A[i]
    temp2 = A[i+1]//Gcd
    #Gcd2 = lcm(temp,temp2)
    Gcd2 = gcd(temp,temp2)

    #a = Gcd2//temp
    a = temp2//Gcd2
    #b = Gcd2//temp2
    b = temp//Gcd2

    temp = A[i]//Gcd*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod


    Gcd %= mod #注意
    c = A[i]
    c %= mod
    d = c*pow_mod(Gcd,mod-2)
    #d = Gcd//c
    d %= mod


    e = b*d%mod
    ans += e
    #ans += Gcd//A[i+1]*b
    ans %= mod


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

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
evisited = [[False] * n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

def dfs(p, v):
    if visited[v]:
        return
    visited[v] = True
    for i in edges[v]:
        if i != p and not evisited[v][i]:
            dfs(v, i)
    count = 0
    for i in edges[v]:
        if i != p and not evisited[v][i]:
            print(v + 1, i + 1)
            evisited[i][v] = True
            count += 1
    if count % 2 == 1:
        print(v + 1, p + 1)
        evisited[p][v] = True

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    la = len(edges[a - 1])
    lb = len(edges[b - 1])
    edges[a - 1].append([b - 1, lb])
    edges[b - 1].append([a - 1, la])

def dfs(p, v):
    visited[v] = True
    for (i, r) in edges[v]:
        if not visited[i] and r != -1 and i != p:
            dfs(v, i)
    odd = False
    pr = -1
    for (i, r) in edges[v]:
        if i != p:
            if r != -1:
                edges[i][r][1] = -1
                odd = not odd
        else:
            pr = r
    if odd:
        edges[p][pr][1] = -1

if m % 2 == 1:
    print(-1)
else:
    dfs(-1, 0)
    for v in range(n):
        for (i, r) in edges[v]:
            if r >= 0:
                print(v + 1, i + 1)
### BUGGY CODE ###

import math
k =  int(input())
ans = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += math.gcd((math.gcd(a, b)), c)

print(ans)


### FIXED CODE ###

import math
k =  int(input())
ans = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        if math.gcd(a, b) == 1:
            ans += k
        else:
            for c in range(1, k+1):
                ans += math.gcd((math.gcd(a, b)), c)

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

n, W = map(int, input().split())
ab = [tuple(map(int, input().split()))for _ in range(n)]
ab.sort(reverse=True)

dp = [0]*W
for w, v in ab:
    for j in reversed(range(W)):
        if j-w < 0:
            break
        if dp[j] < dp[j-w]+v:
            dp[j] = dp[j-w]+v
    if dp[0] < v:
        dp[0] = v
print(max(dp))


### FIXED CODE ###

n, W = map(int, input().split())
ab = [tuple(map(int, input().split()))for _ in range(n)]
ab.sort(reverse=True)

dp = [0]*W
for w, v in ab:
    for j in reversed(range(W)):
        if j-w < 0:
            break
        if dp[j] < dp[j-w]+v:
            dp[j] = dp[j-w]+v
    if dp[0] < v:
        dp[0] = v
print(max(dp))
### BUGGY CODE ###

N, M = map(int, input().split())

members = [-1] * N

group_count = 0
groups = [0] * N
group_dict = {}
for m in range(M):
    A, B = map(int, input().split())
    A = A - 1
    B = B - 1
    if members[A]==-1 and members[B]==-1:
        members[A] = members[B] = group_count
        groups[group_count] = 2
        group_dict[group_count] = [A, B]
        group_count += 1
    
    elif members[A]!=-1 and members[B]==-1:
        members[B] = members[A]
        groups[members[A]] += 1
        group_dict[members[A]].append(B)
    
    elif members[B]!=-1 and members[A]==-1:
        members[A] = members[B]
        groups[members[B]] += 1
        group_dict[members[B]].append(A)
    
    else:
        if members[A] != members[B]:
            old = members[B]
            groups[members[A]] += groups[members[B]]
            groups[members[B]] = 0
            group_dict[members[A]] = group_dict[members[A]] +  group_dict[members[B]]
            for aaaaaa in group_dict[members[B]]:
                members[aaaaaa] = members[A]
            group_dict[old] = []

ans = max(groups)
if ans == 0:
    print(1)
else:
    print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(x)]

N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    uf.unite(A-1, B-1)

ans = max(uf.get_size(i) for i in range(N))
print(ans)
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((c, d),int)
X1=np.zeros((c, d),int)
X2=np.zeros((c, d),int)
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
 X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
 X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
  if j>=2:
   X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
  else:
    X2[i][j-1]=0
print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
def amari(a):
  return a % 998244353
X0=[[0]*d for i in range(c)]
X1=[[0]*d for i in range(c)]
X2=[[0]*d for i in range(c)]
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=amari(X0[a-1][j-1]*(a-1))
 X1[a-1][j]=amari(X0[a-1][j-1]+X1[a-1][j-1]*(a-1))
 X2[a-1][j]=amari(X1[a-1][j-1]+X2[a-1][j-1]*a)
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=amari((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j)
  if j>=2:
   X2[i][j-1]=amari(X1[i][j-2]+X2[i][j-2] *(i+1))
print(amari(X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1]))
### BUGGY CODE ###

n = int(input())
s = sorted(["".join(sorted((input()))) for i in range(n)])
count = 0

for j in range(n - 1):
    for k in range(j + 1, n):
        if s[j] == s[k]:
            count += 1

print(count)

### FIXED CODE ###

from operator import itemgetter

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

# 2次元配列の文字を、左から優先にソート
s_sort = sorted(s, key = itemgetter(0, 1, 2, 3, 4, 5, 6, 7, 8, 9))

count = 0
s_count = 0

l = s_sort[0]

for i in range(1, n):
    if l == s_sort[i]:
        #同じ文字があるごとにカウントの数が増える（同じ文字が2つなら1個の組み合わせ、3つなら3つの組み合わせがある）
        s_count += 1
        count += s_count
    else:
        l = s_sort[i]
        s_count = 0

print(count)