Harryxun/stf_run huggingface dataset:
import math

str=input()
n,k=int(str.split()[0]),int(str.split()[1])

def place(n,x):
    if n<1:
        return 0
    if n==1:
        return 1
    return int( math.factorial(n+x-1)/math.factorial(n-1)/math.factorial(x) % 1000000007)

for i in range (1,k+1):
    cb=place(  i,  k-i  )
    cr=place(i+1,n-k-i+1)
    cr=cr%1000000007
    print(cb*cr%1000000007)


### FIXED CODE ###

import math

str=input()
n,k=int(str.split()[0]),int(str.split()[1])

def place(n,x):
    if n==1:
        return 1
    ans=1
    if n-1 < x:
        for i in range(x+1,n+x):
            ans*=i
        ans//=math.factorial(n-1)
    else:
        for i in range(n, n+x):
            ans*=i
        ans//=math.factorial(x)
    return ans%1000000007


for i in range (1,k+1):
    if n-k < i-1:
        print(0)
    else:
        cb=place(  i,  k-i  )
        cr=place(i+1,n-k-i+1)
        cr=cr%1000000007
        print(cb*cr%1000000007)
mod=10**9+7
def dfs(v):
  if checked[v]==1:
    return
  checked[v]=1
  dp[v][0]=1
  dp[v][1]=1
  for u in g[v]:
    if checked[u]==0:
      dfs(u)
      dp[v][0]*=dp[u][0]+dp[u][1]
      dp[v][0]%=mod
      dp[v][1]*=dp[u][0]
      dp[v][1]%=mod      

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
dp=[[0,0] for _ in range(n+1)]
checked=[0]*(n+1)
dfs(1)
print((dp[1][0]+dp[1][1])%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

mod=10**9+7
def dfs(v):
  if checked[v]==1:
    return
  checked[v]=1
  dp[v][0]=1
  dp[v][1]=1
  for u in g[v]:
    if checked[u]==0:
      dfs(u)
      dp[v][0]=(dp[v][0]*(dp[u][0]+dp[u][1]))%mod
      dp[v][1]=(dp[v][1]*dp[u][0])%mod

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
dp=[[0,0] for _ in range(n+1)]
checked=[0]*(n+1)
dfs(1)
print((dp[1][0]+dp[1][1])%mod)
a,b=int(input())

print(a*b)
print(a*2+b*2)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,(a+b)*2)
import math
import numpy as np
from functools import reduce


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


def _gcd(*numbers):
    return reduce(math.gcd, numbers)

#def gcd(numbers):
#    return reduce(np.gcd, numbers)



N,X=spaceinput()

x=spaceinput()

x.append(X)
x=sorted(x)
d=[]
for i,xx in enumerate(x[:-1]):
    d.append(x[i+1]-x[i])

#print(d)

#print( np.gcd(12, 20))
print(np.gcd.reduce(d))


### FIXED CODE ###

import math
import numpy as np
from functools import reduce


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


def _gcd(*numbers):
    return reduce(math.gcd, numbers)

#def gcd(numbers):
#    return reduce(np.gcd, numbers)

def gcd(a, b):
    if not b:
        return a
    else:
        return gcd(b, a % b)


def gcd_n(numbers):
  '''Returns GCD of given n numbers.
  Argument: numbers - List of given numbers
  '''
  return reduce(lambda x, y: gcd(x, y), numbers)



N,X=spaceinput()

x=spaceinput()

x.append(X)
x=sorted(x)
d=[]
for i,xx in enumerate(x[:-1]):
    d.append(x[i+1]-x[i])

#print(d)

#print( np.gcd(12, 20))
print(gcd_n(d))
N,K = map(int,input().split())
p = list(map(int,input().split()))
max = 0
for i in range(N-K+1):
    s = 0
    for j in range(i,i+K):
        s += p[j]
    if s > max:
        max = s
print((max+K)/2)

### FIXED CODE ###

N = int(input())
c = 0
A = list(map(int,input().split()))
ans = {}
for i in range(N):
    a = A[i]
    if a not in ans:
        ans[a] = 1
    else:
        c = 1
        break
if c == 0:
    print("YES")
else:
    print("NO")
N, M = map(int,input().split())
print((1900*M + 100(N-M))*2**M)

### FIXED CODE ###

N, M = map(int, input().split())
print((1900*M + 100*(N-M))*2**M)
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        if (head_num+1)//2 in prime_list:
            prime_2007.append(head_num)
            lr+=[cnt]*(head_num - j-1)
            cnt+=1
            j=head_num
            lr.append(cnt)


        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+1)

n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    l=min(l,len(lrlr))
    r=min(r,len(lrlr))
    #print(l,r)
    #print(lrlr)

    print(lrlr[r]-lrlr[l-1])


### FIXED CODE ###

import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    prime_2007=[]
    j=0
    lr=[0]
    cnt=0

    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)

        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    
    for item in prime_list:
        if (item+1)//2 in prime_list:
            prime_2007.append(item)

    for item in prime_2007:
        lr+=[cnt]*(item - j-1)
        cnt+=1
        j=item
        lr.append(cnt)
    lr+=[cnt]*(10**5-j)
    #print(prime_2007)
    #print(lr)
    #return prime_list
    return(lr)


lrlr=get_primenumber(10**5+10)

result=[]
n=int(input())
for i in range(n):
    l,r=map(int,input().split())
    #l=min(l,len(lrlr)-1)
    #r=min(r,len(lrlr)-1)
    #print(l,r)
    #print(len(lrlr))

    result.append(lrlr[r]-lrlr[l-1])

for item in result:
    print(item)
def divide(x, y):
	s = 1
	if(x < 0):s *= -1
	if(y < 0):s *= -1
	return abs(x) / abs(y) * s
	

def _split(_src):
	c = 0
	l = len(_src)
	if l == 0:
		return []
	while c < l and ord('0') <= ord(_src[c]) <= ord('9'):
		c += 1
	if c == 0:
		tmp = _split(_src[1:])
		if tmp != [] and tmp[0] == "-":
			tmp = ["+" , "(", 0 , "-", 1, ")", "*"] + tmp[1:]
		return [_src[0]] + tmp
	else:
		return [int(_src[:c])] + _split(_src[c:])
		

def evaluate(src):
	if len(src) == 1:
		return src[0]
		
	if "(" in src:
		l = src.index("(")
		r = src.index(")")
		mid = evaluate(src[l + 1:r])
		return evaluate( src[:l] + [mid] + src[r + 1:])
	
	operators = [("+", lambda x,y:x + y),
				 ("-", lambda x,y:x - y),
				 ("*", lambda x,y:x * y),
				 ("/", divide)
				]	
	
	for (op,func) in operators:
		if op in src:
			p = src.index(op)
			l = evaluate(src[:p])
			r = evaluate(src[p + 1:])
			return func(l, r)
	
	
for t in xrange(input()):
	_src = raw_input()[:-1]
	src = _split(_src)
	print evaluate(src)

### FIXED CODE ###

def divide(x, y):
    s = 1
    if(x < 0):s *= -1
    if(y < 0):s *= -1
    return abs(x) / abs(y) * s     

operator = {"+":(lambda x,y: x+y),
            "-":(lambda x,y: x-y),
            "*":(lambda x,y: x*y),
            "/":divide
            }

def ind(src, x):
    if x not in src:return 1<<30
    return src.index(x)
 
def _split(_src):
    c = 0
    l = len(_src)
    if l == 0:
        return []
    while c < l and ord('0') <= ord(_src[c]) <= ord('9'):
        c += 1

    if c == 0:
        return [_src[0]] + _split(_src[1:])
    else:
        return [int(_src[:c])] + _split(_src[c:])
         
 
def evaluate(src):
    if len(src) == 1:
        return src[0]
         
    if "(" in src:
        l = src.index("(")
        r = l
        st = 1
        while st:
            r += 1
            if src[r] == "(": st += 1
            if src[r] == ")": st -= 1
        
        mid = evaluate(src[l + 1:r])
        return evaluate( src[:l] + [mid] + src[r + 1:])
    
    pos = min(ind(src, "*"), ind(src,"/"))
    if(pos == 1<<30):
        pos = min(ind(src, "+"), ind(src, "-"))
    op = src[pos]
    l, r = src[pos - 1], src[pos + 1]
    mid = operator[op](l, r)
    return evaluate(src[:pos - 1] + [mid] + src[pos + 2:])

     
for t in xrange(input()):
    _src = raw_input().strip("=")
    src = _split(_src)
    print evaluate(src)
inp = input()
inpLi = inp.split("")
A1 = int(inpLi[0])
A2 = int(inpLi[1])
A3 = int(inpLi[2])
result = A1+A2+A3
if result >= 22:
  print("bust")
else:
  print("win")


### FIXED CODE ###

inp = input()
inpLi = inp.split()
A1 = int(inpLi[0])
A2 = int(inpLi[1])
A3 = int(inpLi[2])

if (A1+A2+A3) >= 22:
  print("bust")
else:
  print("win")
N = int(input())
A = list(map(int, input().split()))
res = 0
for i in range(1, len(A)+1, 2):
    res += A[i] % 2
print(res)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
res = 0
for i in range(0, len(A), 2):
    res += A[i] % 2
print(res)
n,m=map(int,input().split())
potion=[]
for i in range(n):
    potion_R = list(map(int,input().split())
    potion.append(potion_R)
potion.sort()
ans=0
number=m
for i in potion:
    if i[1]<=number:
        number-= i[1]
        ans+= i[0]*i[1]
    else:
        ans+= i[0]*number
        break
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
potion=[]
for i in range(n):
    potion_R = list(map(int,input().split()))
    potion.append(potion_R)
potion.sort()
ans=0
number=m
for i in potion:
    if i[1]<=number:
        number-= i[1]
        ans+= i[0]*i[1]
    else:
        ans+= i[0]*number
        break
print(ans)
n = int(input())
a=[]
for i in range(n):
  x,y = input().split()
  a.append([x,-int(y),i+1])
a.sort()
for i in range(n):
  print(a[i][2])



### FIXED CODE ###

A,N = map(int,input().split())
print((3*A+N)//2)
h, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(k)]
dp = [0 for i in range(h+1)]
for i in range(1, h+1):
    dp[i] = min(dp[i - a]+b for a,b in ab)
print(min(dp[h:]))

### FIXED CODE ###

h, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(k)]
maxa = max(a for a,b in ab)
dp = [0 for i in range(h+maxa)]
for i in range(1, h+maxa):
    dp[i] = min(dp[i - a]+b for a,b in ab)
print(min(dp[h:]))
def triple(n):
    n = n * 3
    return n
    
print(triple(x))


### FIXED CODE ###

x = int(input())
print(x*x*x)
ans = 0
k, s = map(int, input().split())
for x in range(k):
  for y in range(k):
    int z = s - x - y
    if 0 <= z and z <= k:
      ans += 1



print(ans)

### FIXED CODE ###

ans = 0
k, s = map(int, input().split())
for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z and z <= k:
      ans += 1
 
 
 
print(ans)
import collections 

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

counter = collections.Counter(input_list)


unique_list = list(counter.keys())
counts = list(counter.values())

if (all(num == 0 for num in unique_list)):
    print('Yes')
else:
    if n % 3 == 0:
        zero_count = counter[0] 
        if zero_count == n / 3 and len(unique_list) == 2:
            print('Yes')
        else: 
            if len(unique_list) != 3:
                print('No')
            else if (unique_list[0] ^ unique_list[1] == unique_list[2]):
                if (all(counts[0] == num for num in counts)):
                    print('Yes')
                else:
                    print('No')
            else:
                print('No')
    else:
        print('No')

### FIXED CODE ###

import collections 

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

counter = collections.Counter(input_list)


unique_list = list(counter.keys())
counts = list(counter.values())

if (all(num == 0 for num in unique_list)):
    print('Yes')
else:
    if n % 3 == 0:
        zero_count = counter[0] 
        if zero_count == n / 3 and len(unique_list) == 2:
            print('Yes')
        else: 
            if len(unique_list) != 3:
                print('No')
            elif (unique_list[0] ^ unique_list[1] == unique_list[2]):
                if (all(counts[0] == num for num in counts)):
                    print('Yes')
                else:
                    print('No')
            else:
                print('No')
    else:
        print('No')
list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

val = input()

print(list[int(val)])

### FIXED CODE ###

list = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

val = input()
vala = int(val) - 1
print(list[vala])
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = p.sort()
print(sum(p[:k]))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
p.sort()
print(sum(p[:k]))
import numpy as np
import copy

N= int(input())
S=input()
SS= copy.copy(S)
S = list(S)
#N, A, B = map(int, input().split())

flag = 1
#print(len(S))
while flag == 1:
    flag = 0
    flag2 = 1
    i = 0
    while flag2:
    # for i in range(len(S)-1):
        #print(S)
        #print(i)
        if S[i]=="(" and S[i+1] ==")":
            flag = 1
            del S[i] 
            del S[i+1]
            i -= 2
        i += 1
        i = max(0,i)
        #print(i, len(S))
        if i+1>=len(S):
            flag2 = 0
a=0
b=0
for i in range(len(S)):
    if S[i]=="(":
        b+=1
    elif S[i]==")":
        a+=1
#print(S)
# initialization of string to ""
A = ""
B = ""

# traverse in the string
for x in range(a):
    
    A += "("   
for x in range(b):    
    B += ")"   

        
#print(str(A)+SS+str(B))
print(A+SS+B)
    



### FIXED CODE ###

import numpy as np
import copy

N= int(input())
S=input()
SS= copy.copy(S)
S = list(S)
#N, A, B = map(int, input().split())

flag = 1
#print(len(S))
while flag == 1:
    flag = 0
    flag2 = 1
    i = 0
    while flag2 and len(S)>1:
    # for i in range(len(S)-1):
        #print(S)
        if S[i]=="(" and S[i+1] ==")":
            # print(S, i)
            flag = 1
            del S[i] 
            del S[i]
            i -= 1
            # print(S, i)
        i += 1
        i = max(0,i)
        if i+1>=len(S):
            flag2 = 0
a=0
b=0
for i in range(len(S)):
    if S[i]=="(":
        b+=1
    elif S[i]==")":
        a+=1
#print(S)
# initialization of string to ""
A = ""
B = ""

# traverse in the string
for x in range(a):
    
    A += "("   
for x in range(b):    
    B += ")"   

        
#print(str(A)+SS+str(B))
print(A+SS+B)
S = str(input())

num = 0
for i in range(len(S)):
    if i % 2 == 0:
        if S[i] == "L":
            num += 1
    else:
        if s[i] == "R":
            num += 1

if num == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = str(input())

num = 0
for i in range(len(S)):
    if i % 2 == 0:
        if S[i] == "L":
            num += 1
    else:
        if S[i] == "R":
            num += 1

if num == 0:
    print("Yes")
else:
    print("No")
import numpy as np
N = int(input())
h = list(map(int, input().split()))
defa = np.inf
dp = [defa] * N

def rec(i):
  if dp[i] != defa:
    return dp[i]
  if i == 0:
    dp[i] = 0
    return 0
  res = defa
  res = min(res, rec(i-1)+np.abs(h[i] - h[i-1]))
  if i >= 2:
    res = min(res, rec(i-2)+np.abs(h[i] - h[i-2]))
  dp[i] = res
  return dp[i]
n = int(rec(N-1))
print(n)

### FIXED CODE ###

import numpy as np
N = int(input())
h = list(map(int, input().split()))
dp = [9999] * N
dp[0] = 0
for i in range(1,N):
  if i<2:
    dp[i] = dp[i-1] + np.abs(h[i] - h[i-1])
  else:
    min1 = dp[i-2] + np.abs(h[i] - h[i-2])
    min2 = dp[i-1] + np.abs(h[i] - h[i-1])
    dp[i] = min(min1, min2)
print(dp[N-1])
a, b = map(int, input().split())
if a*b % 2 = 0:
  print('Even')
else:
  print('Odd')


### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 == 0:
  print('Even')
else:
  print('Odd')
#! -*- coding:utf-8 -*-

def search(values,hp=0,vp=0,stamp=0,fruit):
	if not (0<=hp<len(values)): return
	if not (0<=vp<len(values[0])): return
	if fruit!=values[hp][vp]: return
	fruit,values[hp][vp]=values[hp][vp],stamp
	search(values,hp-1,vp,stamp,fruit)
	search(values,hp+1,vp,stamp,fruit)
	search(values,hp,vp-1,stamp,fruit)
	search(values,hp,vp+1,stamp,fruit)

def solve(values):
	stamp=0
	for i in range(len(values)):
		for j in range(len(values[i])):
			if values[i][j] in ['@','#','*']:
				search(values,i,j,stamp+1,values[i][j])
				stamp+=1
	return stamp


H,W = list(map(int,input().split(' ')))
values = list()
for _ in range(H):
	values.append([x for x in input().strip()])
print(solve(values))

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**6)

def search(field,hp,vp,item):
	if not (0<=hp<len(field)): return
	if not (0<=vp<len(field[hp])): return
	if item!=field[hp][vp]: return
	field[hp][vp]=True
	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
		search(field,hp+dh,vp+dv,item)
#	search(field,hp-1,vp,item)
#	search(field,hp+1,vp,item)
#	search(field,hp,vp-1,item)
#	search(field,hp,vp+1,item)

def solve(field):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(field)):
		for j in range(len(field[i])):
			if field[i][j] in valid_items:
				search(field,i,j,field[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		field = list()
		for _ in range(H):
			field.append(list(input().strip()))
		print(solve(field))
		line = input().strip()

if __name__=='__main__':
	main()
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-29 21:38:12 +0900
# LastModified: 2020-08-29 21:53:47 +0900
#


import os
import sys
sys.setrecursionlimit(100000)
# import numpy as np
# import pandas as pd
from collections import Counter


def dfs(u, color, path, n, d):
    color[u] = d
    for v in path[u]:
        if color[v] == -1:
            dfs(v, color, path, n, d)



def main():
    n, m = map(int, input().split())
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    color = [-1]*(n+1)
    d = 0
    for i in range(1, n+1):
        if color[i] == -1:
            dfs(i, color, path, n, d)
            d += 1
    color = color[1:]
    color_cnt = Counter(color).values()
    print(max(color_cnt))



if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-29 21:38:12 +0900
# LastModified: 2020-08-29 21:54:27 +0900
#


import os
import sys
sys.setrecursionlimit(900000)
# import numpy as np
# import pandas as pd
from collections import Counter


def dfs(u, color, path, n, d):
    color[u] = d
    for v in path[u]:
        if color[v] == -1:
            dfs(v, color, path, n, d)



def main():
    n, m = map(int, input().split())
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    color = [-1]*(n+1)
    d = 0
    for i in range(1, n+1):
        if color[i] == -1:
            dfs(i, color, path, n, d)
            d += 1
    color = color[1:]
    color_cnt = Counter(color).values()
    print(max(color_cnt))



if __name__ == "__main__":
    main()
L, R = map(int,input().split())
a = 10**10
for i in range(L,min(R,L+2019):
    for j in range(i+1,min(R,L+2019)+1):
        a = min(a,(i*j)%2019)
        if a == 1:
            print("1")
            exit()
print(a)

### FIXED CODE ###

L, R = map(int,input().split())
a = 10**10
for i in range(L,min(R,L+2019)+1):
    for j in range(i+1,min(R,L+2019)+1):
        a = min(a,(i*j)%2019)
print(a)
X=input()
A=input()
B=input()
X -= A
Y = X % B
print(Y)

### FIXED CODE ###

x,a,b = [int(input()) for i in range(3)]
print((x-a)%b)
n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1)
    s += 2 ** i * c1 * (n - c1)
    arr = arr >> 1

print(s % mod)

### FIXED CODE ###

import numpy as np

n = int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10 ** 9 + 7
s = 0

for i in range(60):
    c1 = np.count_nonzero(arr & 1)
    s += 2 ** i * c1 * (n - c1)
    arr = arr >> 1

print(s % mod)
n = int(raw_input())
for i in range(n):
	x, y, z = map(int, raw_input())
	if y*z >= 1000000:
		print x
	else:
		print "NA"

### FIXED CODE ###

while True:
	n = int(raw_input())
	if n == 0:
		break
	data = {}
	order = []
	for i in range(n):
		id,price,quant = map(int, raw_input().split())
		if id in data:
			data[id] += price*quant
		else:
			data[id] = price*quant 
			order.append(id)
	if max(data.values()) <  1000000:
		print "NA"
	else:
		for k in order:
			if data[k] >=  1000000:
				print k
import sys
from bisect import bisect, bisect_left
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    S = [0] * (N + 1)
    for i, a in enumerate(A): S[i + 1] = a + S[i]
 
    l, h = 1, A[N-1] * 2 + 1
    while h - l > 1: #最小値がｍ以上の要素をM個用意できるか
        m = (h + l) // 2
        count = 0
        for i, a in enumerate(A): count += N - bisect_left(A, m - a)
        if count >= M: l = m
        else: h = m

    total = 0
    count = 0
    Q = []
    heapq.heapify(Q)
    for i, a in enumerate(A):
        j = bisect_left(A, l - a)
        total += a * (N - j) + (S[N] - S[j])
        count += N - j
        for k in range(min(10, N - j)):
            heapq.heappush(Q, a + A[j + k])

    if count > M:
        for _ in range(count - M):
            minus = heapq.heappop(Q)
            total -= minus

    print(total)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from bisect import bisect, bisect_left
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    S = [0] * (N + 1)
    for i, a in enumerate(A): S[i + 1] = a + S[i]
 
    l, h = 1, A[N-1] * 2 + 1
    while h - l > 1: #最小値がｍ以上の要素をM個用意できるか
        m = (h + l) // 2
        count = 0
        for i, a in enumerate(A): count += N - bisect_left(A, m - a)
        if count >= M: 
            l = m
        else: h = m

    total = 0
    count = 0
    Q = []
    heapq.heapify(Q)
    min_out = 10000000
    for i, a in enumerate(A):
        j = bisect_left(A, l - a)  
        total += a * (N - j) + (S[N] - S[j])
        count += N - j
        if 0 <= j < N: min_out = min(min_out, a + A[j])

    if count > M:
        total -= min_out * (count - M)

    print(total)

    return 0

if __name__ == "__main__":
    solve()
from collections import Counter

k = input()
p = input()
d = len(k)
f = len(p)
g=""
diff = abs(d-f)

if d>f :
     d = d-diff
     g = k[d:len(k)]
   
else:
    f = f-diff
    g=p[f:len(p)]


r=""a
i = 0
for i in range(d):
    r += "".join(k[i]+p[i])
    #print(r)
    
print(r+g)

### FIXED CODE ###

#
from collections import Counter

k = input()
p = input()
d = len(k)
f = len(p)
g=""
diff = abs(d-f)

if d>f :
     d = d-diff
     g = k[d:len(k)]
   
else:
    f = f-diff
    g=p[f:len(p)]


r=""
i = 0
for i in range(d):
    r += "".join(k[i]+p[i])
    #print(r)
    
print(r+g)