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

from functools import lru_cache


@lru_cache(maxsize=None)
def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

li = []

for i in range(n):
    tmp = arr[:i] + str(1 ^ int(arr[i])) + arr[i + 1:]
    li.append(int(tmp, 2))

for x in li:
    print(rec(x))

### FIXED CODE ###

from functools import lru_cache


def popcnt(x):
    return bin(x).count("1")


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


ret = [rec(x) for x in range(2 * 10**5 + 1)]


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
b=[]
c=[]
for i in range(0, m):
    ib,ic = map(int, input().split(" "))
    b.append(ib)
    c.append(ic)
for i in range(0, m):
    if c[i] < a[0]:
        continue
    a[0:b[i]] = list(map(lambda x: x if c[i] < x else c[i], a[0:b[i]]))
    a.sort()
print(sum(a))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))
a.sort()
bc=[None]*m
for i in range(m):
    bc[i] = list(map(int, input().split(" ")))
bc.sort(reverse=True, key=lambda x:x[1])
l=[]
for [b,c] in bc:
    l.extend([c]*b)
    if n < len(l):
        break
for i in range(n):
    if len(l) <= i or l[i] <= a[i]:
        break
    a[i] = l[i]
print(sum(a))
### BUGGY CODE ###

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

# 考え方
# 目標：最大値の最小化
# にぶたん
# 必要条件：A[i] <= A[i+1] => F[i] >= F[i+1]

# sort
# Aは昇順、Fは降順(任意)
A = sorted(A)
F = sorted(F, reverse=True)

# にぶたん(参考：juppy)
ng = -1
ok = 10 ** 12  # 取り得る最大値

while ok - ng > 1:  # 収束判定
    mid = (ok + ng) // 2
    cost = 0

    for i, e in enumerate(A):
        cost += max(0, e - mid // F[i])
    
    if cost <= K:
        ok = mid
    
    else:
        ng = mid

print(ok)

### FIXED CODE ###

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

# 考え方
# 目標：最大値の最小化
# にぶたん
# 必要条件：A[i] <= A[i+1] => F[i] >= F[i+1]

# sort
# Aは昇順、Fは降順(任意)
A = sorted(A)
F = sorted(F, reverse=True)

# にぶたん(参考：juppy)
ng = -1
ok = 10 ** 12  # 取り得る最大値

while ok - ng > 1:  # 収束判定
    mid = (ok + ng) // 2
    cost = 0

    for i, e in enumerate(A):
        cost += max(0, e - mid // F[i])
    
    if cost <= K:
        ok = mid
    
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import sys #追加
sys.setrecursionlimit(10**9)

n,m = map(int,input().split())
al = list(map(int,input().split()))

#a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

#a,bの最小公倍数
def lcm(a, b):
   return a * b // gcd (a, b)


bl = [i//2 for i in al]
bl = sorted(bl)
ans = 1
for b in bl:
   ans = lcm(ans, b)

for a in al:
   if ans % a == 0:
      print(0)
      import sys
      sys.exit()

def ceil(a, b):
   return a // b + (a % b > 0)

print(ceil(m // ans, 2))


### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(10**9)
import time
s = time.time()

n,m = map(int,input().split())
al = list(map(int,input().split()))

bl = [i//2 for i in al]
from fractions import gcd
ans = 1
for b in bl:
   if time.time() - s > 1.9:
      print(0)
      import sys
      sys.exit()
   ans = (ans * b) // gcd(ans, b)

for a in al:
   if time.time() - s > 1.9:
      print(0)
      import sys
      sys.exit()
   if ans % a == 0:
      print(0)
      import sys
      sys.exit()

def ceil(a, b):
   return a // b + (a % b > 0)

print(ceil(m // ans, 2))
### BUGGY CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
cr = []
for j in range(-max(ar),max(ar)+1):
    count = 0
    for i in range(a):
        count += abs(ar[i] - (i+1 + j))
    cr.append(count)
print(min(cr))

### FIXED CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
ar = [r - (i+1) for i,r in enumerate(ar)]
br = sorted(ar)
b = br[a//2]
count = 0
for i in range(a):
    count += abs(ar[i] - b)
print(count)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 99999999

for i in range(N):
    # print(S[:i].count('W'))
    # print(S[i:].count('E'))
    # print("---------")
    ans = min(ans, S[:i].count('W')+S[i:].count('E'))
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

ans = 99999999

cnt_w = 0
cnt_e = 0
i = 0
for j in range(i):
    if S[j] == 'W':
        cnt_w += 1
for j in range(i,N):
    if S[j] == 'E':
        cnt_e += 1
ans = cnt_w + cnt_e

for i in range(N):
    if S[i] == 'W':
        cnt_w += 1
    else:
        cnt_e -= 1
    ans = min(cnt_w + cnt_e, ans)
print(ans)
### BUGGY CODE ###

def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = n
                    if i > 0:
                        tmp += i * dp[i-1][j][k]
                    if j > 0:
                        tmp += j * dp[i+1][j-1][k]
                    if k > 0:
                        tmp += k * dp[i][j+1][k-1]
                    dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

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

N = int(input())
P = list(map(int, input().split()))
answer = []

for i in range(N):
    if P[i] <= min(P[0: i + 1]):
        answer.append(i)
print(len(answer))

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
answer = 0
minimum = P[0]

for i in range(N):
    if P[i] <= minimum:
        answer += 1
    minimum = min(P[i], minimum)
print(answer)
### BUGGY CODE ###

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

# dp[i][j]: 足場iまで見た時 jまでの最小コスト
dp = [[0 for j in range(n)] for i in range(n)]

dp[1][1] = abs(h[1] - h[0])

for i in range(n):
    if i == 0 or i == 1:
        continue

    dp[i] = dp[i - 1]

    cost1jump = dp[i - 1][i - 1] + abs(h[i] - h[i - 1])
    cost2jump = dp[i - 1][i - 2] + abs(h[i] - h[i - 2])
    dp[i][i] = min(cost1jump, cost2jump)

print(dp[-1][-1])


### FIXED CODE ###

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

# dp[i][j]: 足場iまで見た時 jまでの最小コスト
dp = [0 for i in range(n)]

dp[1] = abs(h[1] - h[0])

for i in range(n):
    if i == 0 or i == 1:
        continue

    cost1jump = dp[i - 1] + abs(h[i] - h[i - 1])
    cost2jump = dp[i - 2] + abs(h[i] - h[i - 2])
    dp[i] = min(cost1jump, cost2jump)

print(dp[-1])
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
f=0
b=[]
t=0
c=[]
for i in range(n-1):
 for l in range(i+1,n):
  b=p[i:l+1]
  t=max(b)
  b.remove(t)
  for j in range(b.count(t)):
   b.remove(t)
  c.append(max(b))
print(sum(c))

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)
### BUGGY CODE ###

import math
def is_prime(x):
    if x <= 1:
        return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

n = int(input())
lst_c = []
for c in range(1,n): #c != n
    lst_c.append(n-c)

lst_c2 = []
prime_cnt = 0
for i in range(len(lst_c)):
    if not(is_prime(lst_c[i])):
        lst_c2.append(lst_c[i])
    else:
        prime_cnt += 1
        

#print(lst_c)


cnt = 0
cnt2 = 0
for i in range(len(lst_c2)):
    if lst_c2[i] != 1:
        for j in range(1,int(lst_c2[i]**0.5)+1):
            if lst_c2[i]%j ==0:
                cnt += 1
                if lst_c2[i]/j == j:
                    cnt2 +=1
        lst_c2[i] = cnt
        cnt = 0
        #cnt2 = 0


print(sum(lst_c2)*2-cnt2 + 2*prime_cnt -1)

### FIXED CODE ###

def func(x):
    ans = 0
    for a in range(1, n):
        for b in range(1, n):
            c = n - a * b
            if c <= 0:
                break
            ans += 1
    return ans

n = int(input())
print(func(n))
### BUGGY CODE ###

from collections import deque

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

graph = [[] for i in range(N)]
for i in range(M):
    L,R,D = map(int, input().split())
    graph[L-1].append([R-1, D])
    graph[R-1].append([L-1, -D])

visited = [False] * N

def bfs(id):
    dist = [int(1e10)] * N
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()
        visited[v] = True

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if not visited[i]:
        bfs(i)

print("Yes")

### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(N)]
for i in range(M):
    L,R,D = map(int, input().split())
    graph[L-1].append([R-1, D])
    graph[R-1].append([L-1, -D])

dist = [int(1e10)] * N

def bfs(id):
    Q = deque()
    Q.append(id)
    dist[id] = 0

    while len(Q) != 0:
        v = Q.popleft()

        for edge in graph[v]:
            u, d = edge[0], edge[1]

            if dist[u] == int(1e10):
                dist[u] = dist[v] + d
                Q.append(u)
            elif dist[u] != dist[v] + d:
                print("No")
                exit()


for i in range(N):
    if dist[i] == int(1e10):
        bfs(i)

print("Yes")
### BUGGY CODE ###

N = int(input())
S = str(input())

R = []
G = []
B = []

for i in range(1,N+1):
    if S[i-1] == 'R':
        R.append(i)
    elif S[i-1] == 'G':
        G.append(i)
    elif S[i-1] == 'B':
        B.append(i)

ans = 0
for a in R:
    for b in G:
        for c in B:
            i = min(a,b,c)
            k = max(a,b,c)
            j = a+b+c-i-k
            if j-i != k-j:
                ans += 1


print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())

r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = S.count('B')

ans = r_cnt*g_cnt*b_cnt

for i in range(N):
    for d in range(1, N):
        j = i + d
        k = j + d
        if k >= N:break
        if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
            ans -= 1

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

import copy
#import bisect
from statistics import median


N = int(input())

X = input().split()
X = [ int(x) for x in X]
"""
N = 4
X = [2,4,4,3]
"""
j = int(N/2)
F = copy.deepcopy(X)
F.sort()

median1 = int(N/2 - 1)
median2 = int(N/2) 

for i in range(N):
    #print(F, median1, median2)
    
    if X[i] < median(F):
        ans = F[median2]
    else:
        ans = F[median1]
    print(int(ans))

### FIXED CODE ###

from statistics import median, median_low, median_high


N = int(input())

X = input().split()
X = [ int(x) for x in X]
"""
N = 4
X = [2,4,4,3]
"""
median = median(X)
#F = copy.deepcopy(X)
"""
F = X[:]
F.sort()

median1 = int(N/2 - 1)
median2 = int(N/2) 

if median.is_integer():
    median1 = median
    median2 = median
else:
    median1 = median - 0.5
    median2 = median + 0.5
"""
median1 = median_low(X)
median2 = median_high(X)
   
for i in range(N):
    #print(F, median1, median2)
    
    if X[i] < median:
        ans = median2
    else:
        ans = median1
    print(int(ans))
### BUGGY CODE ###

import numpy as np
import functools
import operator

Π = functools.partial(functools.reduce, operator.mul)
N=int(input())
L=list(int(x) for x in input().split())
sum=(Π(L))
if sum > 10**18:
	print("-1")
else:
	print(sum)

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


N = readint()
S = readstr()
Q = readint()
K = readints()

ans = []
for k in K:
    m = 0
    c = 0
    a = [0]
    if 'D' not in S:
        ans.append(0)
        break
    d = S.find('D')
    for i in range(d+1,min(N,d+k)):
        if S[i]=='M':
            m += 1
        if S[i]=='C':
            c += 1
            a[-1] += m
    a.append(a[-1])
    for i in range(d+1,N):
        if i+k-1<N:
            if S[i+k-1]=='M':
                m += 1
            elif S[i+k-1]=='C':
                c += 1
                a[-1] += m
        if S[i-1]=='M':
            m -= 1
            a[-1] -= c
        elif S[i-1]=='C':
            c -= 1
        if S[i]=='D':
            a.append(a[-1])
    ans.append(sum(a[:-1]))
printrows(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


N = readint()
S = readstr()
Q = readint()
K = readints()

if 'D' not in S:
    printrows([0]*Q)
    exit()
d = S.find('D')
e = S.rfind('D')
ans = []
for k in K:
    m = 0
    c = 0
    a = 0
    for i in range(d+1,min(N,d+k)):
        if S[i]=='M':
            m += 1
        if S[i]=='C':
            c += 1
            a += m
    b = a
    for i in range(d+1,N):
        if i+k-1<N:
            if S[i+k-1]=='M':
                m += 1
            elif S[i+k-1]=='C':
                c += 1
                a += m
        if S[i-1]=='M':
            m -= 1
            a -= c
        elif S[i-1]=='C':
            c -= 1
        if S[i]=='D':
            b += a
            if i==e:
                break
    ans.append(b)
printrows(ans)
### BUGGY CODE ###

import numpy as np
H,N=map(int,input().split())
AB=np.zeros([N,2]).astype(int)
for i in range(N):AB[i,:] = list(map(int,input().split()))

dp = np.zeros([H+AB[:,0].max()+1, N+1]).astype(int)
for j in range(1,H+AB[:,0].max()+1):
  for i in range(1,N+1):
    if AB[i-1,0] < j:
      dp[j,i] = dp[j - AB[i-1,0], 1:].min() + AB[i-1,1]
    else:
      dp[j,i] = AB[i-1,1]

print(dp[H,1:].min())

### FIXED CODE ###

H,N=map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]
dp = [[0]*(N+1) for _ in range(2*10**4+5)]

for j in range(1,H+1):
  for i in range(1,N+1):
    if AB[i-1][0] < j:
      dp[j][i] = dp[j - AB[i-1][0]][i] + AB[i-1][1]
    else:
      dp[j][i] = AB[i-1][1]
  MIN = min(dp[j][1:])
  dp[j][1:] = [MIN]*(len(dp[j])-1)

print(min(dp[H][1:]))
### BUGGY CODE ###

n, k, c = map(int, input().split())
s = input()
s2 = s
s += "x"*c
s2 = "x"*c+s2
k2 = k
left = []
i = 0
while i < n:
  if k == 0:
    break
  if s[i] == "o":
    left.append(i+1)
    s = "x"*(i+c+1)+s[i+c+1:]
    #print(s)
    k -= 1
    i += c
  i += 1

right = []
i = len(s2)-1
while i >= 0:
  if k2 == 0:
    break
  if s2[i] == "o":
    right.append(i+1-c)
    s2 = s2[:i-c]+"x"*(len(s2)-i+c)
    #print(s2)
    k2 -= 1
    i -= c
  i -= 1
#print(left, right)
 
ans = sorted(list(set(left) & set(right)))
for i in ans:
  print(i)

### FIXED CODE ###

n, k, c = map(int, input().split())
s = input()
s2 = s
s += "x"*c
s2 = "x"*c+s2
k2 = k
kans = k
left = []
i = 0
while i < n:
  if s[i] == "o":
    left.append(i+1)
    i += c
  i += 1

right = []
i = len(s2)-1
while i >= c:
  if k2 == 0:
    break
  if s2[i] == "o":
    right.append(i+1-c)
    k2 -= 1
    i -= c
  i -= 1
if len(left) == kans:
  ans = sorted(list(set(left) & set(right)))
  for i in ans:
    print(i)
else:
  exit()
### BUGGY CODE ###

from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

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

def main():
    N = i_input()
    ans = 0
    for c in range(1, N):
        ab = make_divisors(N - c)
        ans += len(ab)
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin
from collections import defaultdict
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())


def main():
    N = i_input()
    d = defaultdict(lambda: 1)
    ans = 0
    for i in range(2, N):
        for j in range(i, N, i):
            d[j] += 1
    for c in range(1, N):
        ans += d[c]
    print(ans)

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

def combi(n, r) :
    ret = 1
    for i in range(n, n-r, -1) :
        ret *= i
    for i in range(r, 0, -1) :
        ret //= i
    return ret

MOD = 10 ** 9 + 7
N, M, K = map(int, input().split(' '))

n, r = N * M - 2, K - 2
P = combi(n, r) % MOD

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt * P
        ans %= MOD

print(ans)


### FIXED CODE ###

from math import factorial

MOD = 10 ** 9 + 7
N, M, K = map(int, input().split(' '))

n, r = N * M - 2, K - 2
#P = factorial(n) // factorial(n-r) // factorial(r) % MOD
P = factorial(n) * pow(factorial(n-r) % MOD, MOD - 2, MOD) * pow(factorial(r) % MOD, MOD - 2, MOD)

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt

ans = (ans * P) % MOD
print(ans)
### BUGGY CODE ###

from bisect import bisect_left


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)

    min_score = float('inf')
    count = 0
    for a in reversed(A):
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += sum(A[index:]) + (N-index) * a
            count += N-index
        else:
            break
    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left
import numpy


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    ans = 0

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)
    C = [0,] + A
    C = numpy.cumsum(C[::-1])
    #print(C)
    min_score = float('inf')
    count = 0
    for a in reversed(A):
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += C[N-index-1] + (N-index) * a
            count += N-index

    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()