Problem:


Score : 500 points

Problem Statement

Takahashi has come to a party as a special guest.
There are N ordinary guests at the party. The i-th ordinary guest has a power of A_i.

Takahashi has decided to perform M handshakes to increase the happiness of the party (let the current happiness be 0).
A handshake will be performed as follows:

Takahashi chooses one (ordinary) guest x for his left hand and another guest y for his right hand (x and y can be the same).

Then, he shakes the left hand of Guest x and the right hand of Guest y simultaneously to increase the happiness by A_x+A_y.

However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:

Assume that, in the k-th handshake, Takahashi shakes the left hand of Guest x_k and the right hand of Guest y_k. Then, there is no pair p, q (1 \leq p < q \leq M) such that (x_p,y_p)=(x_q,y_q).

What is the maximum possible happiness after M handshakes?

Constraints

1 \leq N \leq 10^5

1 \leq M \leq N^2

1 \leq A_i \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

Print the maximum possible happiness after M handshakes.

Sample Input 1

5 3
10 14 19 34 33

Sample Output 1

202

Let us say that Takahashi performs the following handshakes:

In the first handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 4.

In the second handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 5.

In the third handshake, Takahashi shakes the left hand of Guest 5 and the right hand of Guest 4.

Then, we will have the happiness of (34+34)+(34+33)+(33+34)=202.

We cannot achieve the happiness of 203 or greater, so the answer is 202.

Sample Input 2

9 14
1 3 5 110 24 21 34 5 3

Sample Output 2

1837

Sample Input 3

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

Sample Output 3

8128170



Sample input:
5 3
10 14 19 34 33


Sample output:
202

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):

    while True:
        if p<n:
            if a[i]+a[p]<=md: p+=1
            else: break
        else: break



    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        try:
            p+=1
        except:
            b=1
            while True:
                b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
try:
    for q in range(n-1,-1,-1):

        while p<n and a[q]+a[p]<=md:
            p+=1

        if p==n: break
        cnt+=n-p
        ans+=a[q]*(n-p)*2

except IndexError:
    b=1
    while True:
        b+=1

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and q>-1:
            if a[q]+a[p]<=md: p+=1
            else: break
    except IndexError:
        b=0
        while True:
            b+=0

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=n-1
cnt=0
ans=0

for i in range(n):
    if p>-1:
        while p>-1 and a[i]+a[p]>md:
            p-=1
            if p==-1: break
    cnt+=n-1-p
    ans+=a[i]*(n-1-p)*2

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=n-1
cnt=0
ans=0

for i in range(n):
    while p>-1 and a[i]+a[p]>md:
        p-=1
        if p==-1: break
    cnt+=n-1-p
    ans+=a[i]*(n-1-p)*2

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    while p<n:
        if a[i]+a[p]>md: break 
        p+=1
    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md: 
        p+=1
    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    while p<n and p>-1 and q<n and q>-1: 
        if a[q]+a[p]<=md: p+=1
        else: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n:
            if a[q]+a[p]<=md: p+=1
            else: break
    except:
        p=n

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and q>-1 and a[q]+a[p]<=md:
            p+=1
    except:
        p=n

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and q>0 and a[q]+a[p]<=md:
            p+=1
    except:
        p=n

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md


p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        p=n

    cnt+=n-p
    ans+=a[q]*(n-p)*2
    if p==n: break


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while (p<n and a[q]+a[p]<=md):
            p+=1
    except:
        p=n

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        p=n

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    while p<n and a[q]+a[p]<=md:
            p+=1
    if p==n: break
    try:
        cnt+=n-p
        ans+=int(a[q])*(n-p)*2
    except:
        ans=ans


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        p=n
    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    while p<n and a[q]+a[p]<=md:
        try:
            p+=1
            if p==n:
                break
            cnt+=n-p
            ans+=a[q]*(n-p)*2
        except:
            ans=ans


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2



try:
    ans+=(m-cnt)*md
    print(ans)
except:
    print(0)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[q]*(n-p)*2
    except:
        print(0)

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    try:
        while p<n and a[i]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[i]*(n-p)*2
    except:
        ans+=0




ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

try:
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[i]*(n-p)*2
    


except:
    print(0)

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

try:

    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[i]*(n-p)*2
except:
    ans=0

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

try:
    p=0
    cnt=0
    ans=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<=md:
            p+=1
        if p==n: break
        cnt+=n-p
        ans+=a[i]*(n-p)*2
except:
    ans=0

ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1: md=l;break
    md=int((r+l)//2)
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while a[i]+a[p]<x:
            p+=1
            if p==n: return cnt
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while a[i]+a[p]<x:
            p+=1
            if p==n: return cnt
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while a[i]+a[p]<x:
            p+=1
            if p==n: return cnt
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while a[i]+a[p]<=md:
        p+=1
    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
            if p==n: return cnt
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
            if p==n: return cnt
        cnt+=n-p
    return cnt

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l,r=a[0]*2,a[-1]*2

while r-l>0:
    if r-l==1:
        md=l
        break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    cnt+=n-p
    ans+=a[i]*(n-p)*2

ans+=(m-cnt)*md

print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
            if p==n: return cnt
        cnt+=n-p
    return cnt

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l,r=a[0]*2,a[-1]*2

while r-l>1:
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    cnt+=n-p
    ans+=a[i]*(n-p)*2

ans+=(m-cnt)*md

print(ans)

Submission status: Runtime Error

Solution code:
def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):

        while a[i]+a[p]<x:
            p+=1
            if p==n: return cnt
        cnt+=n-p
    return cnt

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l,r=a[0]*2,a[-1]*2

while r-l>1:
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
for i in range(n-1,-1,-1):
    while p<n and a[i]+a[p]<=md:
        p+=1
    cnt+=n-p
    ans+=a[i]*(n-p)*2

ans+=(m-cnt)*md

print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <complex>
using namespace std;
const double pi = 3.14159265358979323846264338;
long long easy_factor(long long n){
  if (n == 1){
    return 1;
  }
  else{
    long long p = 2;
    long long f = 2;
    while (n % p != 0){
      p += 1;
      if (n % p == 0){
        f = p;
        break;
      }
      if (p * p > n){
        f = n;
        break;
      }
    }
    return f;
  }
}

template <typename T>
T vecout(T A){
  for (int i=0;i<A.size();i++){
    cout << A.at(i) << endl;
  }
}

vector<complex<long double>> simply_fft(vector<complex<long double>> f, long long n){
  if (n == 1){
    return f;
  }
  else{
    long long dn = n / 2;
    vector<complex<long double>> fe(dn);
    vector<complex<long double>> fo(dn);
    for (long long j=0;j<dn;j++){
      fe.at(j) = f.at(2*j+0);
      fo.at(j) = f.at(2*j+1);
    }
    vector<complex<long double>> tmp0 = simply_fft(fe, dn);
    vector<complex<long double>> tmp1 = simply_fft(fo, dn);
    complex<long double> grow = 1.0 + 0.0i;
    complex<long double> seed = cos((2.0*pi)/n) - 1i*sin((2.0*pi)/n);
    complex<long double> right = 0;
    for (long long i=0;i<dn;i++){
      right = tmp1.at(i) * grow;
      f.at(i) = tmp0.at(i) + right;
      f.at(i+dn) = tmp0.at(i) - right;
      grow *= seed;
    }
    return f;
  }
}

vector<complex<long double>> simply_ifft(vector<complex<long double>> f, long long n){
  if (n == 1){
    return f;
  }
  else{
    long long dn = n / 2;
    vector<complex<long double>> fe(dn);
    vector<complex<long double>> fo(dn);
    for (long long j=0;j<dn;j++){
      fe.at(j) = f.at(2*j+0);
      fo.at(j) = f.at(2*j+1);
    }
    vector<complex<long double>> tmp0 = simply_ifft(fe, dn);
    vector<complex<long double>> tmp1 = simply_ifft(fo, dn);
    complex<long double> grow = 1.0 + 0.0i;
    complex<long double> seed = cos((2.0*pi)/n) + 1i*sin((2.0*pi)/n);
    complex<long double> right = 0;
    for (long long i=0;i<dn;i++){
      right = tmp1.at(i) * grow;
      f.at(i) = tmp0.at(i) + right;
      f.at(i+dn) = tmp0.at(i) - right;
      grow *= seed;
    }
    return f;
  }
}
vector<long long> vecmachine(){
  vector<long long> A(100000);
  for (int i=0;i<100000;i++){
    A.at(i) = 100000;
  }
  return A;
}
long long powlimit(long long x){
  long long y = 1;
  while (y < x){
    y *= 2;
  }
  return y;
}

// ------------------------------------------

int main(){
  long long N, M;
  cin >> N >> M;
  long long m = 0;
  vector<long long> A = vecmachine();
  for (int i=0;i<N;i++){
    //cin >> A.at(i);
    if (m < A.at(i)){
      m = A.at(i);
    }
  }
  long long pl = powlimit(2*m+2);
  vector<complex<long double>> X(pl, 0);
  for (int i=0;i<N;i++){
    X.at(A.at(i)) += 1.0;
  }
  vector<complex<long double>> F = simply_fft(X, pl);
  vector<complex<long double>> Y(pl, 0);
  for (int i=0;i<pl;i++){
    Y.at(i) = F.at(i) * F.at(i);
  }
  vector<complex<long double>> Z = simply_ifft(Y, pl);
  vector<long long> sol(pl, 0);
  for (long long i=0;i<pl;i++){
    sol.at(i) = floor(0.5+real(Z.at(i))/pl);
  }
  long long S = 0, i = pl - 1, pat = 0;
  while (pat < M){
    if (pat + sol.at(i) > M){
      S += (M - pat) * i;
      pat = M;
    }
    else{
      S += sol.at(i) * i;
      pat += sol.at(i);
    }
    i -= 1;
    if (i < 0){
      break;
    }
  }
  cout << S << endl;
}

Submission status: Runtime Error

Solution code:
#handshake
from scipy.fft import rfft, irfft
import numpy as np
N, M = map(int, input().split())
A = np.array(input().split(), dtype=np.int32)

x = np.bincount(A)
fft_size = 1 << (2 * x.size + 10).bit_length()

fx = rfft(x, fft_size)
conv = irfft(fx * fx, fft_size)
conv = (conv + 0.5).astype(int)

tmp = np.arange(conv.size, dtype=int)
happy = tmp[np.nonzero(conv)].tolist()
cnt = conv[np.nonzero(conv)].tolist()


ans = 0
while M > 0:
    h = happy.pop()
    num = cnt.pop()
    num = min(M, num)

    M -= num
    ans += num * h

print(ans)

Submission status: Runtime Error

Solution code:
#handshake
from scipy.fft import rfft, irfft
import numpy as np
N, M = map(int, input().split())
A = np.array(input().split(), dtype=np.int32)

x = np.bincount(A)
fft_size = 1 << (2 * x.size + 10).bit_length()

fx = rfft(x, fft_size)
conv = irfft(fx * fx, fft_size)
conv = (conv + 0.5).astype(int)

tmp = np.arange(conv.size, dtype=int)
happy = tmp[np.nonzero(conv)].tolist()
cnt = conv[np.nonzero(conv)].tolist()


ans = 0
while M > 0:
    h = happy.pop()
    num = cnt.pop()
    num = min(M, num)

M -= num
ans += num * h

print(ans)

Submission status: Runtime Error

Solution code:
#handshake
from scipy.fft import rfft, irfft
import numpy as np
N, M = map(int, input().split())
A = np.array(input().split(), dtype=np.int32)

x = np.bincount(A)
fft_size = 1 << (2 * x.size + 10).bit_length()

fx = rfft(x, fft_size)
conv = irfft(fx * fx, fft_size)
conv = (conv + 0.5).astype(int)

tmp = np.arange(conv.size, dtype=int)
happy = tmp[np.nonzero(conv)].tolist()
cnt = conv[np.nonzero(conv)].tolist()


ans = 0
while M > 0:
h = happy.pop()
num = cnt.pop()
num = min(M, num)

M -= num
ans += num * h

print(ans)

Submission status: Runtime Error

Solution code:
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))

Submission status: Runtime Error

Solution code:
import numpy as np

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

A.sort(reverse=True)
if M<=N:
  A_sorted_trunc = A[:M]
else:
  A_sorted_trunc = A 
num_idx = len(A_sorted_trunc)

A_sum = np.zeros((num_idx, num_idx))
for i in range(num_idx):
  for j in range(num_idx):
    A_sum[i,j] = int(A_sorted_trunc[i]) + int(A_sorted_trunc[j])

A_sum = A_sum.flatten()
A_sum = np.sort(A_sum)[::-1]
A_sum_can = A_sum[:M]

power_sum = np.sum(A_sum_can).astype(np.int)

print(power_sum)