Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import re

s = input()

def trans_word(text):
    replacements = {'01': '', '10': ''}
    return re.sub('({})'.format('|'.join(map(re.escape, replacements.keys()))), lambda m: replacements[m.group()], text)

ans = 0
flag = True

while flag:
    s_tmp = s
    s = trans_word(s)
    ans += (len(s_tmp) - len(s))
    flag = len(s_tmp) - len(s)

print(ans)

Fixed submission:
import re

s = input()

c0, c1 = 0, 0
for i in s:
    if i=='0':
        c0 += 1
    else:
        c1 += 1

print(min(c0, c1)*2)

"""TLE
def trans_word(text):
    replacements = {'01': '', '10': ''}
    return re.sub('({})'.format('|'.join(map(re.escape, replacements.keys()))), lambda m: replacements[m.group()], text)

ans = 0
flag = True

while flag:
    s_tmp = s
    s = trans_word(s)
    ans += (len(s_tmp) - len(s))
    flag = len(s_tmp) - len(s)

print(ans)
"""

Buggy python submission (verdict: Time Limit Exceeded):
s = input()

ans = 0
flag = True
while flag:
    s_tmp = s
    s = s.replace('01', '')
    s = s.replace('10', '')
    ans += (len(s_tmp) - len(s))
    flag = len(s_tmp) - len(s)

print(ans)

Fixed submission:
import re

s = input()

c0, c1 = 0, 0
for i in s:
    if i=='0':
        c0 += 1
    else:
        c1 += 1

print(min(c0, c1)*2)

"""TLE
def trans_word(text):
    replacements = {'01': '', '10': ''}
    return re.sub('({})'.format('|'.join(map(re.escape, replacements.keys()))), lambda m: replacements[m.group()], text)

ans = 0
flag = True

while flag:
    s_tmp = s
    s = trans_word(s)
    ans += (len(s_tmp) - len(s))
    flag = len(s_tmp) - len(s)

print(ans)
"""
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> a(h);
    for (int i=0; i<h; i++) {
        cin >> a.at(i);
    }
    vector<bool> row(h, false);
    vector<bool> col(w, false);
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            if (a.at(i).at(j) == '#') {
				row[i] = true;
				col[j] = true;
            }
        }
    }

	for (int i = 0; i < h; i++) {
		if (row[i]) {
			for (int j = 0; j < w; j++) {
				if (col[j]) {
					cout << a[i][j];
				}
			}
			cout << endl;
		}
	}    
}

Fixed submission:
h, w = map(int, input().split())
a = [''] * h
for i in range(h):
	a[i] = input()

row = [False] * h
col = [False] * w
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			row[i] = True
			col[j] = True

for i in range(h):
	if row[i]:
		for j in range(w):
			if col[j]:
				print(a[i][j], end = '')
		print()
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;

int main() {
  long long n, m;
  cin >> n >> m;

  if (n>=2 && m>=2) {
      cout << n*m - (n-2)*2 - (m-2)*2 - 4 << endl;
  }
  else if (n==1 && m==1) {
      cout << 1 << endl;
  }
  else if (n==1 && m>=2) {
      cout << m-2 << endl;
  }
  else {
      cout << n-2 << endl;
  }
  return 0;
}

Fixed submission:
n, m = map(int, input().split())

if n>=2 and m>=2:
    print(n*m - (n-2)*2 - (m-2)*2 - 4)
elif n==1 and m==1:
    print(1)
elif n==1 and m>=2:
    print(m-2)
else:
    print(n-2)

Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  if (n>=2 && m>=2) {
      cout << n*m - (n-2)*2 - (m-2)*2 - 4 << endl;
  }
  else if (n==1 && m==1) {
      cout << 1 << endl;
  }
  else if (n==1 && m>=2) {
      cout << m-2 << endl;
  }
  else {
      cout << n-2 << endl;
  }
  return 0;
}

Fixed submission:
n, m = map(int, input().split())

if n>=2 and m>=2:
    print(n*m - (n-2)*2 - (m-2)*2 - 4)
elif n==1 and m==1:
    print(1)
elif n==1 and m>=2:
    print(m-2)
else:
    print(n-2)

Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;

  if (n>=2 && m>=2) {
      cout << n*m - (n-2)*2 - (m-2)*2 - 4 << endl;
  }
  else if (n==1 && m==1) {
      cout << 1 << endl;
  }
  else if (n==1 && m>=2) {
      cout << m-2 << endl;
  }
  else {
      cout << n-2 << endl;
  }
}

Fixed submission:
n, m = map(int, input().split())

if n>=2 and m>=2:
    print(n*m - (n-2)*2 - (m-2)*2 - 4)
elif n==1 and m==1:
    print(1)
elif n==1 and m>=2:
    print(m-2)
else:
    print(n-2)
Buggy python submission (verdict: Runtime Error):
input()
S = input()
K = int(input())

c = S[K]

print("".join([v if v == c else "*" for v in S]))


Fixed submission:
input()
S = input()
K = int(input())

c = S[K-1]

print("".join([v if v == c else "*" for v in S]))
Buggy python submission (verdict: Time Limit Exceeded):
A, B, M = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
discountDic = {}
for i in range(M):
    x, y, c = map(int, input().split(' '))
    key = (x-1)*B+(y-1)
    if key not in discountDic or discountDic[key] < c:
        discountDic[key] = c
priceList = []
for i in range(A):
    for j in range(B):
        price = a[i] + b[j]
        if i*B+j in discountDic:
            price -= discountDic[i*B+j]
        priceList.append(price)
print(min(priceList))

Fixed submission:
A, B, M = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
discountDic = {}
for i in range(M):
    x, y, c = map(int, input().split(' '))
    key = (x-1)*B+(y-1)
    if key not in discountDic or discountDic[key] > a[x-1] + b[y-1] - c:
        discountDic[key] = a[x-1] + b[y-1] - c
discount_min_price = min(discountDic.values())
all_low_price = min(a) + min(b)
if discount_min_price < all_low_price:
    print(discount_min_price)
else:
    print(all_low_price)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
reverseFlag = False
for i in range(Q):
    tmp = input()
    if tmp[0] == '1':
        reverseFlag = not reverseFlag
    else:
        tmpt, tmpf, tmpc = tmp.split(' ')
        if tmpf == '1' and reverseFlag == False or tmpf == '2' and reverseFlag == True:
            S = ''.join([tmpc, S]) 
        else:
            S = ''.join([S, tmpc])

if reverseFlag == True:
    S = S[::-1]
print(S)

Fixed submission:
S = input()
Q = int(input())
reverseFlag = False
forwardList = []
backwardList = []
for i in range(Q):
    tmp = input()
    if tmp[0] == '1':
        reverseFlag = not reverseFlag
    else:
        tmpt, tmpf, tmpc = tmp.split(' ')
        if tmpf == '1' and reverseFlag == False or tmpf == '2' and reverseFlag == True:
            forwardList.append(tmpc) 
        else:
            backwardList.append(tmpc)

if reverseFlag == True:
    S = ''.join(reversed(backwardList)) + S[::-1] + ''.join(forwardList)
else:
    S = ''.join(reversed(forwardList)) + S + ''.join(backwardList)
print(S)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
reverseFlag = False
for i in range(Q):
    tmp = input()
    if tmp[0] == '1':
        reverseFlag = not reverseFlag
    else:
        tmpt, tmpf, tmpc = tmp.split(' ')
        if tmpf == '1' and reverseFlag == False or tmpf == '2' and reverseFlag == True:
            S = tmpc + S
        else:
            S = S + tmpc

if reverseFlag == True:
    S = S[::-1]
print(S)

Fixed submission:
S = input()
Q = int(input())
reverseFlag = False
forwardList = []
backwardList = []
for i in range(Q):
    tmp = input()
    if tmp[0] == '1':
        reverseFlag = not reverseFlag
    else:
        tmpt, tmpf, tmpc = tmp.split(' ')
        if tmpf == '1' and reverseFlag == False or tmpf == '2' and reverseFlag == True:
            forwardList.append(tmpc) 
        else:
            backwardList.append(tmpc)

if reverseFlag == True:
    S = ''.join(reversed(backwardList)) + S[::-1] + ''.join(forwardList)
else:
    S = ''.join(reversed(forwardList)) + S + ''.join(backwardList)
print(S)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
Q = int(input())
for i in range(Q):
    tmp = input()
    if tmp[0] == '1':
        S = S[::-1]
    else:
        tmpt, tmpf, tmpc = tmp.split(' ')
        if tmpf == '1':
            S = tmpc + S
        else:
            S = S + tmpc
print(S)

Fixed submission:
S = input()
Q = int(input())
reverseFlag = False
forwardList = []
backwardList = []
for i in range(Q):
    tmp = input()
    if tmp[0] == '1':
        reverseFlag = not reverseFlag
    else:
        tmpt, tmpf, tmpc = tmp.split(' ')
        if tmpf == '1' and reverseFlag == False or tmpf == '2' and reverseFlag == True:
            forwardList.append(tmpc) 
        else:
            backwardList.append(tmpc)

if reverseFlag == True:
    S = ''.join(reversed(backwardList)) + S[::-1] + ''.join(forwardList)
else:
    S = ''.join(reversed(forwardList)) + S + ''.join(backwardList)
print(S)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split(' ')))

answer = 'YES'
max_val = max(A) + 1
check = [False] * max_val
for a in A:
    if check[a] == True:
        answer = 'NO'
        break
    else:
        check[a] = True
print(answer)

Fixed submission:
N = int(input())
A = list(map(int, input().split(' ')))

answer = 'YES'
check_dic = {}
for a in A:
    if a in check_dic:
        answer = 'NO'
        break
    else:
        check_dic[a] = True
print(answer)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split(' ')))

answer = 'YES'
check = [False] * max(A)
for a in A:
    if check[a-1] == True:
        answer = 'NO'
        break
    else:
        check[a-1] = True
print(answer)

Fixed submission:
N = int(input())
A = list(map(int, input().split(' ')))

answer = 'YES'
check_dic = {}
for a in A:
    if a in check_dic:
        answer = 'NO'
        break
    else:
        check_dic[a] = True
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split(' '))
p = list(map(int, input().split()))

psum = []
for i in range(N-K+1):
    psum.append(sum(p[i:i+K]))
print((max(psum)+K)/2)

Fixed submission:
N, K = map(int, input().split(' '))
p = list(map(int, input().split()))

psum = []
pini = sum(p[:K])
psum.append(pini)
for i in range(1, N-K+1):
    pini = pini - p[i-1] + p[i+K-1]
    psum.append(pini)
print((max(psum)+K)/2)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split(' '))
p = list(map(int, input().split()))

exp_val = [n/2+0.5 for n in p]
ksum = []
for i in range(N-K+1):
    ksum.append(sum(exp_val[i:i+K]))
print(max(ksum))

Fixed submission:
N, K = map(int, input().split(' '))
p = list(map(int, input().split()))

psum = []
pini = sum(p[:K])
psum.append(pini)
for i in range(1, N-K+1):
    pini = pini - p[i-1] + p[i+K-1]
    psum.append(pini)
print((max(psum)+K)/2)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(int, input().split(' ')))
count = 0
for i, value in enumerate(P):
    if min(P[:i+1]) == value:
        count += 1
print(count)

Fixed submission:
N = int(input())
P = list(map(int, input().split(' ')))
count = 1
min_value = P[0]
for i in range(1, N):
    if P[i] <= min_value:
        min_value = P[i]
        count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
N=input()
A=list(map(int, input().split()))
B=list(map(int, input().split()))

if sum(A) < sum(B) : 
    print(-1)
else :
    diff=[A[i] - B[i] for i in range(len(A))]
    pos=sorted([x for x in diff if x > 0])
    neg=[x for x in diff if x < 0]
    nes=sum(neg)
    if nes >= 0 :
        print(0)
    else:
        items = 0
        total_pos = 0
        for p in reversed(pos):
            items += 1
            total_pos += p
            if(total_pos + nes >= 0) :
                print(items + len(neg))
                break


Fixed submission:
print("YES" if "".join(sorted(input().split())) == "1479" else "NO")
Buggy python submission (verdict: Time Limit Exceeded):
[N, K] = map(int, input().split())
A = list(map(int, input().split()))
count = 0
while len(A) != 1:
  A = A[K:] + [0]
  count = count + 1 
print(count)


Fixed submission:
[N, K] = map(int, input().split())
A = list(map(int, input().split()))
print(-(-(N - 1) // (K - 1)))
Buggy python submission (verdict: Runtime Error):
A, B, C, D, E, F = map(int, input().split())

W = sorted(list({a*100*A + b*100*B for a in range(F // 100 // A + 1) for b in range(F // 100 // B + 1) if a*100*A + b*100*B <= F}))
S = [max([c*C + d*D for c in range(int((E*w / 100) / C) + 1) for d in range(int((E*w / 100) / D) + 1) if ((c*C + d*D)*100 <= E*w) and (c*C + d*D + w <= F)]) for w in W]
I = sorted([i for i in range(len(W))], key=lambda i : W[i]/(W[i] + S[i]) if W[i] > 0 else 1)[0]
print(A[0] if W[I] == 0 else W[I] + S[I], S[I])

Fixed submission:
A, B, C, D, E, F = map(int, input().split())

W = sorted(list({a*100*A + b*100*B for a in range(F // 100 // A + 1) for b in range(F // 100 // B + 1) if a*100*A + b*100*B <= F}))
S = [max([c*C + d*D for c in range(int((E*w / 100) / C) + 1) for d in range(int((E*w / 100) / D) + 1) if ((c*C + d*D)*100 <= E*w) and (c*C + d*D + w <= F)]) for w in W]
I = sorted([i for i in range(len(W))], key=lambda i : W[i]/(W[i] + S[i]) if W[i] > 0 else 1)[0]
print(100*A if W[I] == 0 else W[I] + S[I], S[I])

Buggy python submission (verdict: Runtime Error):
A, B, C, D, E, F = map(int, input().split())

W = sorted(list({a*100*A + b*100*B for a in range(F // 100 // A + 1) for b in range(F // 100 // B + 1) if a*100*A + b*100*B <= F}))
S = [max([c*C + d*D for c in range((E*w / 100) / C + 1) for d in range((E*w / 100) / D + 1) if ((c*C + d*D)*100 <= E*w) and (c*C + d*D + w <= F)]) for w in W]
I = sorted([i for i in range(len(W))], key=lambda i : W[i]/(W[i] + S[i]) if W[i] > 0 else 1)[0]
print(W[I] + S[I], S[I])


Fixed submission:
A, B, C, D, E, F = map(int, input().split())

W = sorted(list({a*100*A + b*100*B for a in range(F // 100 // A + 1) for b in range(F // 100 // B + 1) if a*100*A + b*100*B <= F}))
S = [max([c*C + d*D for c in range(int((E*w / 100) / C) + 1) for d in range(int((E*w / 100) / D) + 1) if ((c*C + d*D)*100 <= E*w) and (c*C + d*D + w <= F)]) for w in W]
I = sorted([i for i in range(len(W))], key=lambda i : W[i]/(W[i] + S[i]) if W[i] > 0 else 1)[0]
print(100*A if W[I] == 0 else W[I] + S[I], S[I])
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a, b):
        while a != b:
                if a > b :
                        a -= b
                else:
                        b -= a
        return a

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

print(3*(N - gcd(N, X)))


Fixed submission:
def gcd(a, b):
        while a != b:
                if a == 0:
                        return b
                elif b == 0:
                        return a
                if a > b :
                        a %= b
                else:
                        b %= a
        return a

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

print(3*(N - gcd(N, X)))

Buggy python submission (verdict: Runtime Error):
from math import gcd

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

print(3*(N - gcd(N, X)))


Fixed submission:
def gcd(a, b):
        while a != b:
                if a == 0:
                        return b
                elif b == 0:
                        return a
                if a > b :
                        a %= b
                else:
                        b %= a
        return a

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

print(3*(N - gcd(N, X)))
Buggy python submission (verdict: Runtime Error):
N, M = [int(i) for i in input().split(" ")]
conds = []
for _ in range(M):
    conds.append([int(i) for i in input().split(" ")])

exists = True
A = [None for _ in range(N)]
for s, c in conds:
    idx = s-1
    if A[idx] != None and A[idx] != c:
        exists = False
        break
    A[idx] = c


def check():
    if not exists:
        return [-1]

    if N == 1:
        if A[0] == None:
            return [0]
        else:
            return A
    else:
        if A[0] == 0:
            return [-1]

    for i in range(N):
        if A[i] == None:
            A[i] = -float("infinity")

    base = [1] + [0] * (N-1)
    res = []
    for i in range(N):
        res[i] = max(A[i], base[i])
    return res


print("".join(str(x) for x in check()))


Fixed submission:
N, M = [int(i) for i in input().split(" ")]
conds = []
for _ in range(M):
    conds.append([int(i) for i in input().split(" ")])

exists = True
A = [None for _ in range(N)]
for s, c in conds:
    idx = s-1
    if A[idx] != None and A[idx] != c:
        exists = False
        break
    A[idx] = c


def check():
    if not exists:
        return [-1]

    if N == 1:
        if A[0] == None:
            return [0]
        else:
            return A
    else:
        if A[0] == 0:
            return [-1]

    for i in range(N):
        if A[i] == None:
            A[i] = -float("infinity")

    base = [1] + [0] * (N-1)
    res = []
    for i in range(N):
        res.append(max(A[i], base[i]))
    return res


print("".join(str(x) for x in check()))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = [input() for _ in range(N)]

count = dict()
for x in S:
    count[x] = count.get(x, 0) + 1

sorted_kv = list(sorted(count.items(), key=lambda x: (-x[1], x[0])))
max_val = sorted_kv[0][1]

res = []
for k, v in sorted_kv:
    if v == max_val:
        print(k)
    else:
        break


Fixed submission:
N = int(input())

count = dict()
for _ in range(N):
    x = input()
    count[x] = count.get(x, 0) + 1

max_val = -float("infinity")
for k, v in sorted(count.items(), key=lambda x: (-x[1], x[0])):
    max_val = max(v, max_val)
    if v == max_val:
        print(k)
    else:
        break
Buggy python submission (verdict: Runtime Error):
import math

X, Y = [int(x) for x in input().split(" ")]

N = (X + Y) / 3
i = (2 * X - Y) / 3
if N < 0 or N != int(N):
    print(0)
if i < 0 or i != int(i):
    print(0)

N = int(N)
i = int(i)

ans = math.factorial(N) / (math.factorial(i) * math.factorial(N-i))
print(ans)


Fixed submission:
MOD = 10**9+7
fact = [1, 1]
for i in range(2, 10**6+1):
    fact.append((fact[i-1] * i) % MOD)


def comb(n, k):
    return (fact[n] * pow(fact[k], MOD-2, MOD) * pow(fact[n-k], MOD-2, MOD)) % MOD


X, Y = [int(x) for x in input().split(" ")]

n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or n != int(n):
    print(0)
elif m < 0 or m != int(m):
    print(0)
else:
    n = int(n)
    m = int(m)
    ans = comb(n+m, n)
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    d = [0]*P
    d[0] = 1
    b = 0
    for i in range(N):
        a = int(S[N-1-i]) * power(10, i, P)
        l[i] = a%P
        b += (ls[i]+ l[i])
        b %= P
        d[b] += 1
    ans = 0
    for a in d:
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)

Fixed submission:
def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    po = [1]*N
    for i in range(N-1):
        po[i+1] = (po[i]*10)%P
    d = [0]*P
    d[0] = 1
    b = 0
    for i in range(N):
        a = int(S[N-1-i]) * po[i]
        l[i] = a%P
        b += l[i]
        b %= P
        d[b] += 1
    ans = 0
    for a in d:
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    for i in range(N):
        a = int(S[N-1-i]) * power(10, i, P)
        l[i] = a%P
        ls[i+1] = (ls[i]+ l[i])%P
    d = {}
    for i in range(N+1):
        if ls[i] not in d:
            d[ls[i]] = 0
        d[ls[i]] += 1
    ans = 0
    for k in d:
        a = d[k]
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)

Fixed submission:
def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    po = [1]*N
    for i in range(N-1):
        po[i+1] = (po[i]*10)%P
    d = [0]*P
    d[0] = 1
    b = 0
    for i in range(N):
        a = int(S[N-1-i]) * po[i]
        l[i] = a%P
        b += l[i]
        b %= P
        d[b] += 1
    ans = 0
    for a in d:
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
As = [0]*(N+1)
for i in range(N):
    As[i+1] = As[i] + A[i]
A.reverse()

import bisect

def flag(x):
    ans = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        ans += (N-res)
    return bool(ans >= M)

def an(x):
    ans = 0
    m = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        m += (N-res)
        ans += As[N-res]
        ans += A[i] * (N-res)
    ans -= (m - M) * x
    return ans


low = 0
high = 10**5 + 100

while low <= high:
    mid = (low + high) // 2
    if flag(mid):
        if not flag(mid+1):
            ans = mid
            break
        else:
            low = mid + 1
    else:
        high = mid - 1

print(an(ans))



Fixed submission:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
As = [0]*(N+1)
for i in range(N):
    As[i+1] = As[i] + A[i]
A.reverse()

import bisect

def flag(x):
    ans = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        ans += (N-res)
    return bool(ans >= M)

def an(x):
    ans = 0
    m = 0
    for i in range(N):
        a = x - A[i]
        res = bisect.bisect_left(A, a)
        m += (N-res)
        ans += As[N-res]
        ans += A[i] * (N-res)
    ans -= (m - M) * x
    return ans


low = 0
high = 10**6

while low <= high:
    mid = (low + high) // 2
    if flag(mid):
        if not flag(mid+1):
            ans = mid
            break
        else:
            low = mid + 1
    else:
        high = mid - 1

print(an(ans))