Harryxun/stf_run huggingface dataset:
from sys import maxsize,stdin,stdout


def solve(ls, n, k):
	dp = [100001] * n
	dp[0] = 0
	if n == 1:
		return 0
	dp[1] = abs(ls[1] - ls[0])
	for i in range(2, n):
		j = 1
		while j <= k and i - j >= 0:
			dp[i] = (min((dp[i - j] + abs((ls[i - j]) - ls[i])), dp[i]))
			j += 1

	return dp[n - 1]


n, k = map(int, stdin.readline().split())
ls = list(map(int, stdin.readline().split()))
stdout.write((solve(ls, n, k)))


### FIXED CODE ###

from sys import stdout, stdin, maxsize

n, k = map(int, stdin.readline().split())
ls = list(map(int, stdin.readline().split()))
dp = [maxsize] * (n + 1)
dp[1] = 0
if n == 1:
	print(0)
else:
	dp[2] = abs(ls[1] - ls[0])
	for i in range(3, n + 1):
		j = 1
		while j <= k and i - j >= 0:
			dp[i] = min(dp[i - j] + abs(ls[i - 1] - ls[i - 1 - j]), dp[i])
			j += 1
	print(dp[n])
x = input()
a = []
check = []
for i in range(int(x)):
    a.append(int(input()) - 1)
    check.append(1)

index = 0



while True:
    check[index] = 0
    index = a[index]
    if check[index] == 0:
        print(-1)
    if index == 1:
        print(count)


### FIXED CODE ###

x = input()
a = []
check = []
for i in range(int(x)):
    a.append(int(input()) - 1)
    check.append(1)

index = 0
count = 0


while True:
    count += 1
    check[index] = 0
    index = a[index]

    if check[index] == 0:
        print(-1)
        break
    if index == 1:
        print(count)
        break
n, knapsack = map(int, input().split())
dp = [0] * (knapsack + 1)
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(knapsack - weight, 0, -1):
        if not dp[j]:
            continue
        new_value = dp[j] + value
        if dp[j + weight] < new_value:
            dp[j + weight] = new_value
    if dp[weight] < value:
        dp[weight] = value
print(max(dp))

### FIXED CODE ###

from math import isfinite

n, knapsack = map(int, input().split())
dpn = n * 100  # MAX VALUE
dp = [float('inf')] * (dpn + 1)
dp[0] = 0
for i in range(n):
    value, weight = map(int, input().split())
    for j in range(dpn - value, -1, -1):
        if not isfinite(dp[j]):
            continue
        new_weight = dp[j] + weight
        if new_weight <= knapsack and dp[j + value] > new_weight:
            dp[j + value] = new_weight

print(next(filter(lambda i: isfinite(dp[i]), range(dpn, -1, -1))))
c == 0
while True:
    x = int(input())
    if x == 0:
        break;
   
    c += 1
    print('Case',str(c) + ':',x)

### FIXED CODE ###

count = 1                                                                   
while True:
    x = input().strip()
    if x == '0':
        break
    print('Case %s: %s' % (count,x))
    count = count + 1
N = input()
num = list(N)
s = 0
for i in range(N):
  s += num[i]
if int(N) % s == 0:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

N = input()
num = list(N)
s = 0
for i in range(len(num)):
  s += int(num[i])
if int(N) % s == 0:
  print("Yes")
else:
  print("No")
a = [int(input()) for i in range(3)]
if a[0] == 2:
  print("Hello World")
elif:
  print(a[1]+a[2])

### FIXED CODE ###

a = int(input())
if a == 1:
  print("Hello World")
else:
  b = int(input())
  c = int(input())
  print(b + c)
# -*- coding: utf-8 -*-

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

# all_apples = sorted(p + q + r, key=lambda x: -x)

p_rest = sorted(p)
q_rest = sorted(q)
r_rest = sorted(r)

ans = 0
p_count = 0
q_count = 0
r_count = 0
while (p_count + q_count + r_count) < (X + Y):
    if p_count < X and q_count < Y:
        candidates = [p_rest[-1], q_rest[-1], r_rest[-1]]
    elif p_count < X and q_count == Y:
        candidates = [p_rest[-1], 0, r_rest[-1]]
    elif p_count == X and q_count < Y:
        candidates = [0, q_rest[-1], r_rest[-1]]

    wanna_eat = max(candidates)
    eat_idx = candidates.index(wanna_eat)

    if eat_idx == 0:
        p_count += 1
        ans += p_rest.pop()
    elif eat_idx == 1:
        q_count += 1
        ans += q_rest.pop()
    else:
        r_count += 1
        ans += r_rest.pop()
    # print(candidates, eat_idx, wanna_eat, p_count, q_count, r_count)

print(ans)


### FIXED CODE ###

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

X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

# all_apples = sorted(p + q + r, key=lambda x: -x)

p_rest = sorted(p + [0])
q_rest = sorted(q + [0])
r_rest = sorted(r + [0])

ans = 0
p_count = 0
q_count = 0
r_count = 0
while (p_count + q_count + r_count) < (X + Y):
    if p_count < X and q_count < Y:
        candidates = [p_rest[-1], q_rest[-1], r_rest[-1]]
    elif p_count < X and q_count == Y:
        candidates = [p_rest[-1], 0, r_rest[-1]]
    elif p_count == X and q_count < Y:
        candidates = [0, q_rest[-1], r_rest[-1]]

    wanna_eat = max(candidates)
    eat_idx = candidates.index(wanna_eat)

    if eat_idx == 0:
        p_count += 1
        ans += p_rest.pop()
    elif eat_idx == 1:
        q_count += 1
        ans += q_rest.pop()
    else:
        r_count += 1
        ans += r_rest.pop()
    # print(candidates, eat_idx, wanna_eat, p_count, q_count, r_count)

print(ans)
-- [Char]あるいは String を Int にする
toInt :: (String -> Int)
toInt x = read x ::Int

--入力を受け取り、[Int]にする
getInts = do
  x <- getLine
  let y = (map$toInt)$words x -- 半角スペースで分割してInt にする
  return y

main = do
  _ <- getInts
  x <- getInts

  if ok x 0 == 1
    then putStrLn "Yes"
    else putStrLn "No"
  where
    ok x n =
      if null x
        then 1
        else if head x >= n
          then ok (tail x) $ max n $ (head x) - 1
          else 0


### FIXED CODE ###

N = int(input())
H = [int(zz) for zz in input().split()][::-1]
p = H[0]

for i in range(N):
    if H[i] > p:
        H[i] -= 1
        if H[i] > p:
            print('No')
            exit()
    p = H[i]

print('Yes')
r = float(input().split)
print("%.5f %.5f" %(r**2*3.14, 2*r*3.14))


### FIXED CODE ###

#
# 4b
#
import math


def main():
    r = float(input())
    S = r * r * math.pi
    L = 2 * r * math.pi
    print(f"{S:.6f} {L:.6f}")


if __name__ == '__main__':
    main()
n = int(input)

for i in range(n):
	present_list[i] = int(input())

print(sum(present_list)-present_list[-1]//2)

### FIXED CODE ###

n = int(input())
present_list = [0]*n
for i in range(n):
	present_list[i] = int(input())
present_list = sorted(present_list)
print(sum(present_list)-present_list[-1]//2)
N, K = map(int, input().split())
S = input()
width,l,r = [],[],[]

for i in range(K):
  if "0" not in S:
    break()
  for j in range(N-1):
    if j == 0:
      sw = 1
      l.append(0)
      for k in range(j,N-1-j):
        if S[k] == "0" and S[k+1] == "1":
          r.append(k+1) #r自体は1
          sw = 2
        if sw == 2 and S[k] == "1" and S[k+1] == "0":
          width.append(k-j)
          break
    if S[j] == "0" and S[j+1] == "1":
      sw = 1
      for k in range(j+1,N-1-j):
        if S[k] == "1" and S[k+1] == "0":
          l.append(k+1)
        if S[k] == "0" and S[k+1] == "1":
          r.append(k+1) #r自体は1
          sw = 2
        if sw == 2 and S[k] == "1" and S[k+1] == "0":
          width.append(k-j)
          break
  idx = width.index(max(width))
  ans = max(width)
  S = S[:l[idx]] + "1"*(r[idx]-l[idx]) + S[r[idx]:]
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = list(map(int,list(input())))
A = []
B = []
if S[0] == 1:
  A.append(0)
  B.append(1)
else:
  A.extend([0,1])
  B.extend([0,0])
  
for i in range(1,N):
  if S[i] == S[i-1]:
    if S[i] == 0:
      A[-1] += 1
    else:
      B[-1] += 1
  else:
    if S[i] == 0:
      A.append(1)
      B.append(0)
    else:
      A.append(0)
      B.append(1)
if B[-1] == 0:
  A.append(0)
  B.append(0)

M = len(A)
tmp = sum(A[0:2*K+1]) + sum(B[0:2*K+1])
ans = tmp
for i in range(2,M-2*K,2):
  tmp -= A[i-1] + B[i-2]
  tmp += A[i+2*K-1] + B[i+2*K]
  ans = max(ans,tmp)
print(ans)
l=[]
while(item=input().split()):
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n or w<0:
		return(0)
	elif w-l[i][0]<0:
		return(0)
	else:
		return(max(solve(i+1,w),l[i][1]+solve(i+1,w-l[i][0])))

print(solve(0,W))

### FIXED CODE ###

value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])
n,k=map(int,input().split())

a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)

l=-1
r=10**12
def ok():
    s=0
    for i in range(n):
        s+=max(0,int(int(a[i])-int(c/f[i])))
    return s<=k

while(l+1<r):
    c=int((l+r)/2)
    if ok():
        r=c
    else:
        l=c
print(r)

### FIXED CODE ###

a,b=map(int,input().split())
if a<10 and b<10:
  print(a*b)
else:
  print(-1)
s = input()
n = len(s)
t = s.replace("x","")
if not t:
  print(0)
  exit()
l = len(t)
if t != t[::-1]:
  print(-1)
  exit()
plc = [-1]
for i in range(n):
  if s[i] != x:
    plc.append(i)
plc.append(n)
l = len(plc)
if l%2 == 0:
  fm = plc[:l//2]
  lt = plc[l//2:]
else:
  fm = plc[l//2+1]
  lt = plc[l//2:]
lt = lt[::-1]
ans = 0
for i in range(1,len(fm)):
  ans += abs((fm[i]-fm[i-1])-(lt[i]-lt[i-1]))
print(ans)
  

### FIXED CODE ###

s = input()
n = len(s)
t = s.replace("x","")
if not t:
  print(0)
  exit()
l = len(t)
if t != t[::-1]:
  print(-1)
  exit()
plc = [-1]
for i in range(n):
  if s[i] != "x":
    plc.append(i)
plc.append(n)
l = len(plc)
if l%2 == 0:
  fm = plc[:l//2]
  lt = plc[l//2:]
else:
  fm = plc[:l//2+1]
  lt = plc[l//2:]
lt = lt[::-1]
ans = 0
for i in range(1,len(fm)):
  ans += abs((fm[i]-fm[i-1])-(lt[i-1]-lt[i]))
print(ans)
#include <stdio.h>
int main(void) {
	int x;
	
    scanf("%d", &x);
    printf("%d\n", x*x*x);

    return 0;

}

### FIXED CODE ###

a, b = map(int, input().split())
sq = a * b
leng = a*2 + b*2
print('{} {}'.format(sq,leng))
from sys import exit
from collections import deque

n, m = map(int,input().split())
a = deque(int(input()) for i in range(m))

base = a.popleft()
p = 10 ** 9 + 7

dp = [1] * (n+1)

if base == 0:
    print(0)
    exit()

for i in range(1, n+1):
    if base == i:
        dp[i] = 0
        if len(a) != 0:
            base = a.popleft()
        continue
    if i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % p
    if dp[i] == 0:
        print(0)
        exit()

print(dp[n])

### FIXED CODE ###

from sys import exit
from collections import deque

n, m = map(int,input().split())
a = deque(int(input()) for i in range(m))

if len(a) != 0:
    base = a.popleft()
else:
    base = -1

p = 10 ** 9 + 7

dp = [1] * (n+1)

if base == 0:
    print(0)
    exit()

for i in range(1, n+1):
    if base == i:
        dp[i] = 0
        if len(a) != 0:
            base = a.popleft()
        continue
    if i == 1:
        dp[i] = 1
    else:
        dp[i] = (dp[i-2] + dp[i-1]) % p
    if dp[i] == 0:
        print(0)
        exit()

print(dp[n])
weather1 = input().split()
weather2 = input().split()
match = 0
for i in range(0,2):
    if weather1[i] == weather2[i]:
        match += 1
print(count)

### FIXED CODE ###

weather1 = input()
weather2 = input()
match = 0
for i in range(0,3):
    if weather1[i] == weather2[i]:
        match += 1
print(match)
n = int(input())
aa = list(map(int, input().split()))
oo = [str(a) for a in np.argsort(aa)+1] 
print(" ".join(oo))

### FIXED CODE ###

import numpy as np
n = int(input())
aa = list(map(int, input().split()))
oo = [str(a) for a in np.argsort(aa)+1] 
print(" ".join(oo))
n = int(input())
a = int(input())
b = int(input())
if n == 1:
  print("Hello World")
else:
  print(a+b)

### FIXED CODE ###

n = int(input())
if n == 1:
  print("Hello World")
else:
  a = int(input())
  b = int(input())
  print(a+b)
r,g,b = map(int,input().split())
if ((100*a + 10*g + b)%4 == 0):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

r, g, b = map(int,input().split())
total = r*100 + g*10 + b
if total % 4 == 0:
	print('YES')
else:
	print('NO')
n = int(input())
a = input().split()
mi = abs(int(a[0]))
ans =  0 
count = 0
for i in range(n):
    ans = ans + abs(int(a[i]))
    if mi > abs(int(a[i])):
        mi = abs(int(a[i]))
    if int(a[i])<0:
        count = count + 1
if count%2 ==0:
    print(ans)
else:
    print(ans-2*mi)


### FIXED CODE ###

i = input().split()
a = float(i[0])
b = float(i[1])
t = float(i[2])
f = True
n = 0
while(f):

    if t  + 0.5 < n * a:
       f = False
       break
    n = n + 1
n = n-1
print(int(n * b))
n = int(input())
if n==1:
  print(0)
else:
  cnt = 0
  flg = 0
  for i in range(1000000):
    if n<i:
      break
    if i==0 or i==1 or n%i!=0:
      continue
    j = i
    while(n%j==0):
      if flg==0:
        flg = 1
      n = int(n/j)
      j *= i
      cnt += 1
  if flg==0:
    print(1)
  else:
    print(cnt)

### FIXED CODE ###

from decimal import Decimal as dc
a,b = map(dc, input().split())
print(int(a*b))
n = int(input())
ans = 0
for i in range(int(n**0.5)):
  if n%i == 0:
    l = i + (n/i) -2 #-2は(0,0)->(1,1)の分
    ans = min(ans, l)
print(ans)

'''
10^12 以下の 正整数 N が与えられます。
この整数を i×j (i,j∈N) と表したとき，i+j−2 の最小値を求める問題です。
まず，愚直に考えると [1, N] の範囲で 2 重ループを回し，ij=N となる 2 整数の和の最小値を更新すればよいです。しかし，これは O(N2) となり，到底間に合いません。
ここで，約数 (つまり，ij=N, i≤j となる i,j すべて) を列挙する際，一方の約数 i は N−−√ 以下であることを利用します。もう一方の約数 j は N÷i から求まるので，すべての約数は O(N−−√) で求まることがわかります。
あとは，すべての i,j の組を列挙し，i+j−2 の最小値を求めれば良いです。1×N=N であることは自明なので，1+N–2=N–1 を初期値にしておきましょう。

計算量 O(N−−√)
'''

### FIXED CODE ###

n = int(input())
ans = 10**12
for i in range(1, int(n**0.5)+1):
  if n%i == 0:
    l = (i+(n/i)-2) #-2は(0,0)->(1,1)の分
    ans = min(ans, l)
print(int(ans))

'''
10^12 以下の 正整数 N が与えられます。
この整数を i×j (i,j∈N) と表したとき，i+j−2 の最小値を求める問題です。
まず，愚直に考えると [1, N] の範囲で 2 重ループを回し，ij=N となる 2 整数の和の最小値を更新すればよいです。しかし，これは O(N2) となり，到底間に合いません。
ここで，約数 (つまり，ij=N, i≤j となる i,j すべて) を列挙する際，一方の約数 i は N−−√ 以下であることを利用します。もう一方の約数 j は N÷i から求まるので，すべての約数は O(N−−√) で求まることがわかります。
あとは，すべての i,j の組を列挙し，i+j−2 の最小値を求めれば良いです。1×N=N であることは自明なので，1+N–2=N–1 を初期値にしておきましょう。

計算量 O(N−−√)
'''
n = int(input())
x = []
u = []
s = 0
for i in range(n):
    x.append(input())
    u.append(input())
    if u[i] == 'JPY':
      s = s + int(x)
    if u[i] == 'BTC':
      s = s + ( float(x) *  380000.0) 

print(s)

### FIXED CODE ###

n = int(input())
x = []
u = []
s = 0
for i in range(n):
    x, u = map(str, input().split())
    if u == 'JPY':
      s = s + int(x)
    if u == 'BTC':
      s = s + ( float(x) *  380000.0) 

print(s)
# -*- coding: utf-8 -*-

def f(s):
    # print(s)
    if s.startswith("dream"):
        return f(s[5:]) or f(s[7:])
    elif s.startswith("erase"):
        return f(s[5:]) or f(s[6:])
    elif s=="":
        return True
    else:
        return False

if f(input()):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

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

s = input()[::-1]
w = [
    "dream"[::-1]
    ,"dreamer"[::-1]
    ,"erase"[::-1]
    ,"eraser"[::-1]
]

while len(s)>0:
    if s.startswith(w[0]):
        s = s[len(w[0]):]
    elif s.startswith(w[1]):
        s = s[len(w[1]):]
    elif s.startswith(w[2]):
        s = s[len(w[2]):]
    elif s.startswith(w[3]):
        s = s[len(w[3]):]
    else:
        break

if len(s)==0:
    print("YES")
else:
    print("NO")
a,b,c=map(int,input().split())
e,d,f=map(int,input().split())
g,h,i=map(int,input().split())
bingo = [a,b,c,d,e,f,g,h,i]
a_list= []
yes = 0
N = int(input())
for i in range(0,N):
    b = int(input())
    if b in bingo:
        a_list.append(bingo.index(b))
if 0 in a_list:
    if 1 in a_list:
        if 2 in a_list:
            yes = 1
    if 3 in a_list:
        if 6 in a_list:
            yes = 1
    if 4 in a_list:
        if 8 in a_list:
            yes = 1
if 1 in a_list:
    if 4 in a_list:
        if 7 in a_list:
            yes = 1
if 2 in a_list:
    if 4 in a_list:
        if 6 in a_list:
            yes = 1
    if 5 in a_list:
        if 8 in a_list:
            yes = 1
if 3 in a_list:
    if 4 in a_list:
        if 5 in a_list:
            yes = 1
if 6 in a_list:
    if 7 in a_list:
        if 8 in a_list:
            yes = 1
if yes == 1:
    print("Yes")
if yes == 0:
    print("No")

### FIXED CODE ###

a = int(input())
if a%2==0:
    n = a/2
else:
    n = (a+1)/2
print(int(n))
a,b,c=input()

if a == b and b == c:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b,c=map(int,input().split())
if a == b and b == c:
    print("Yes")
else:
    print("No")
A = input()
B = input()

A = int(A)
B = int(B)

if A > B :
    X = A
    A = A - 1

else :
    X = B
    B = B - 1

if A > B :
    X = X + A
else :
    X = X + B

print(X)


### FIXED CODE ###

A,B = input().split(' ')

A = int(A)
B = int(B)

if A > B :
    X = A
    A = A - 1

else :
    X = B
    B = B - 1

if A > B :
    X = X + A
else :
    X = X + B

print(X)
from bisect import bisect_left, bisect_right
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
                    
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    if len(A) < 2: break
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
                    
print(ans)
N, M = [int(i) for i in input().split()]
data_ls = list()
for i in range(M):
    data_ls.append([int(i) -1 for i in input().split()])
A_ls, B_ls = zip(*data_ls)
conv_ls = list()

par = list(range(N))
rank = [1] * N

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
        rank[y] += rank[x]
        rank[x] = rank[y]
    else:
        par[y] = x
        rank[x] += rank[y]
        rank[y] = rank[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def ranking(x):
    return rank[find(x)]

def main():
    conv_ls.append(0)
    for i, (x,y) in enumerate(data_ls[::-1]):
        N1 = ranking(x)
        N2 = ranking(y)
        if is_same(x, y):
            conv_ls.append(conv_ls[i])
        else:
            conv_ls.append(conv_ls[i] + N1 * N2)
        unite(x,y)
    for conv in conv_ls[::-1][1:]:
        print(int(N * (N - 1) / 2 - conv))

main()

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
data_ls = list()
for i in range(M):
    data_ls.append([int(i) -1 for i in input().split()])
A_ls, B_ls = zip(*data_ls)
conv_ls = list()

par = list(range(N))
rank = [1] * N

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
        rank[y] += rank[x]
        rank[x] = rank[y]
    else:
        par[y] = x
        rank[x] += rank[y]
        rank[y] = rank[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def ranking(x):
    return rank[find(x)]

def main():
    conv_ls.append(0)
    for i, (x,y) in enumerate(data_ls[::-1]):
        N1 = ranking(x)
        N2 = ranking(y)
        if is_same(x, y):
            conv_ls.append(conv_ls[i])
        else:
            conv_ls.append(conv_ls[i] + N1 * N2)
            unite(x,y)
    for conv in conv_ls[::-1][1:]:
        print(int(N * (N - 1) / 2 - conv))

main()
def nmx(x):
    r = 0
    for a in As:
        r += d2[max(0, x-a)]
    return -r
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())))
mn, mx = As[0], As[-1]

j = 0
n = N
d2 = []
for i in range(mx*2):
    while True:
        if j>=N:
            break
        if i <= As[j]:
            break
        j += 1
        n -= 1
    d2.append(n)
# d2[i] : i以上のaがいくつあるか
r = bsearch(-M, 1, 10**7, nmx)
from itertools import accumulate
aas = list(accumulate([0]+As[::-1]))
rr = 0
c = 0
for a in As[::-1]:
    if c+d2[max(0, r-a)] > M:
        rr += a*(M-c) + aas[M-c]
        break
    else:
        rr += a*d2[max(0, r-a)] + aas[d2[max(0, r-a)]]
    c += d2[max(0, r-a)]
print(rr)


### FIXED CODE ###


def nmx(x):
    r = 0
    for a in As:
        r += d2[max(0, x-a)]
    return -r
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())))
mn, mx = As[0], As[-1]

j = 0
n = N
d2 = []
for i in range(mx*2):
    while True:
        if j>=N:
            break
        if i <= As[j]:
            break
        j += 1
        n -= 1
    d2.append(n)
# d2[i] : i以上のaがいくつあるか
# nmx(x) : x以上のペアが何通りあるか
r = bsearch(-M, 1, mx*2, nmx)
r += 1
from itertools import accumulate
aas = list(accumulate([0]+As[::-1]))
rr = 0
c = 0
for a in As[::-1]:
    idx = min(mx*2-1, max(0, r-a))
    rr += a*d2[idx] + aas[d2[idx]]
    c += d2[idx]
rr += (r-1)*(M-c)
print(rr)
from itertools import combinations
N = int(input())
d = [0]*128
for _ in range(N): dic[ord(input()[0])] += 1
print(sum([d[ord(p0)]*d[ord(p1)]*d[ord(p2)] for p0,p1,p2 in combinations('MARCH', 3)]))


### FIXED CODE ###

from itertools import combinations
from collections import Counter
N = int(input())
S = Counter()
for _ in range(N):
  S[input()[0]] += 1
print(sum([S[p0]*S[p1]*S[p2] for p0,p1,p2 in combinations('MARCH', 3)]))
quit()