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:
# ----------- gcd ----------- #
def gcd(x, y):
    k, l = x, y
    if y < 0:
        k, l = -k, -l
    while l:
        k, l = l, k % l
    return k

# --------- IsPrime --------- #
def IsPrime(n):
    if n == 1:
        return False
    p = 2
    while p * p <= n:
        if n % p == 0:
            return False
        p += 1
    return True

# --- fraction calculator --- #
def fracsum(f1, f2, sign = 1):
    fs = [f1[0]*f2[1]+sign*f1[1]*f2[0], f1[1]*f2[1]]
    g = gcd(fs[0], fs[1])
    fs[0] //= g
    fs[1] //= g
    return fs
def fracprod(f1, f2):
    fs = [f1[0]*f2[0], f1[1]*f2[1]]
    g = gcd(fs[0], fs[1])
    fs[0] //= g
    fs[1] //= g
    return fs

# ------ factorization ------ #
def factorization(n):
    D = {}
    a = n
    p = 2
    while a != 1:
        cnt = 0
        while a % p == 0:
            cnt += 1
            a //= p
        if cnt != 0:
            D[p] = cnt
        p += 1
        if p * p > n and a != 1:
            D[a] = 1
            break
    return D
# --------------fact. calculator-------------- #
mod = 0 # <-- input modulo
maxf = 0           # <-- input factional limitation

def doubling(n, m, modulo=0):
    y = 1
    base = n
    tmp = m
    while tmp:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y
def Vanilla(D):
    F = [1]
    for i in D:
        mL = F[:]
        dp = i
        for j in range(D[i]):
            for k in mL:
                F.append(dp*k)
            dp *= i
    return F
def bic(n):
    cnt = 0
    while n % 2 == 0:
        cnt += 1
        n //= 2
    return cnt
mod = 2013265921
def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo
"""D = {i: [] for i in range(39, 40)}
for i in range(39, 40):
    j = 1
    bas = 2**i
    while len(D[i]) < 1:
        if IsPrime(j*bas+1):
            D[i].append(j*bas+1)
        j += 2
print(D)"""
#mod = 40961
#mod = 998244353, primod = 50475, invmod = 305218526
mod = 2013265921 # 998244353 = 2^23 * (odd number)
primod = 137
"""S = factorization(mod - 1)
S = {2: S[2]}
LL = Vanilla(S)
print(LL)
LL.sort(reverse=True)
for i in range(1, 500):
    flg = (doubling(i, doubling(2, S[2]), mod) == 1)
    for j in range(1, len(LL)):
        flg *= (doubling(i, LL[j], mod) != 1)
    if flg:
        print(i)"""
def powlimit(n):
    y = 1
    cnt = 0
    while y < n:
        y *= 2
        cnt += 1
    return y, cnt

N, M = map(int, input().split())
A = list(map(int, input().split()))
mm = max(A)
F = [0 for _ in range(mm+1)]
for i in range(N):
    F[A[i]] += 1
"""N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
F = [0] + [AB[i][0] for i in range(N)]
G = [0] + [AB[i][1] for i in range(N)]"""
pl, c = powlimit(2*mm+2)
#pl, c = powlimit(2*N+2)
F = F[:] + [0]*(pl-mm-1)
prim = [doubling(primod, doubling(2, 27-i), mod) for i in range(27)]
invp = [inved(prim[i]) for i in range(27)]
def NTT(f, n, cn, inverse=False):
    if n == 1:
        return f
    if n == 2:
        return [(f[0]+f[1])%mod, (f[0]-f[1])%mod]
    dn = n // 2
    fe = [f[2*i+0] for i in range(dn)]
    fo = [f[2*i+1] for i in range(dn)]
    fe = NTT(fe, dn, cn-1, inverse)
    fo = NTT(fo, dn, cn-1, inverse)
    seed = inverse * prim[cn] + (1 - inverse) * invp[cn]
    grow = 1
    for i in range(dn):
        right = fo[i] * grow % mod
        f[i+0*dn] = (fe[i] + right) % mod
        f[i+1*dn] = (fe[i] - right) % mod
        grow *= seed
        grow %= mod
    return f

X = NTT(F, pl, c)
#Y = NTT(G, pl, c)
#print(X)
#print(Y)
Z = [X[i]*X[i]%mod for i in range(pl)]
Z = NTT(Z, pl, c, 1)
#print(NTT(Z, pl, c, 1))
ipl = inved(pl)
for i in range(pl):
    Z[i] *= ipl
    Z[i] %= mod
S = 2*max(A)
hp = 0
ccnt = 0
while ccnt < M:
    if ccnt + Z[S] < M:
        ccnt += Z[S]
        hp += S * Z[S]
    else:
        hp += S * (M - ccnt)
        ccnt += M - ccnt
    S -= 1
print(hp)
#for i in range(1, max(A)+1):
#    print(Z[i]*ipl%mod)

Submission status: Runtime Error

Solution code:
# ----------- gcd ----------- #
def gcd(x, y):
    k, l = x, y
    if y < 0:
        k, l = -k, -l
    while l:
        k, l = l, k % l
    return k

# --------- IsPrime --------- #
def IsPrime(n):
    if n == 1:
        return False
    p = 2
    while p * p <= n:
        if n % p == 0:
            return False
        p += 1
    return True

# --- fraction calculator --- #
def fracsum(f1, f2, sign = 1):
    fs = [f1[0]*f2[1]+sign*f1[1]*f2[0], f1[1]*f2[1]]
    g = gcd(fs[0], fs[1])
    fs[0] //= g
    fs[1] //= g
    return fs
def fracprod(f1, f2):
    fs = [f1[0]*f2[0], f1[1]*f2[1]]
    g = gcd(fs[0], fs[1])
    fs[0] //= g
    fs[1] //= g
    return fs

# ------ factorization ------ #
def factorization(n):
    D = {}
    a = n
    p = 2
    while a != 1:
        cnt = 0
        while a % p == 0:
            cnt += 1
            a //= p
        if cnt != 0:
            D[p] = cnt
        p += 1
        if p * p > n and a != 1:
            D[a] = 1
            break
    return D
# --------------fact. calculator-------------- #
mod = 0 # <-- input modulo
maxf = 0           # <-- input factional limitation

def doubling(n, m, modulo=0):
    y = 1
    base = n
    tmp = m
    while tmp:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y
def Vanilla(D):
    F = [1]
    for i in D:
        mL = F[:]
        dp = i
        for j in range(D[i]):
            for k in mL:
                F.append(dp*k)
            dp *= i
    return F
def bic(n):
    cnt = 0
    while n % 2 == 0:
        cnt += 1
        n //= 2
    return cnt
mod = 2013265921
def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo
"""D = {i: [] for i in range(39, 40)}
for i in range(39, 40):
    j = 1
    bas = 2**i
    while len(D[i]) < 1:
        if IsPrime(j*bas+1):
            D[i].append(j*bas+1)
        j += 2
print(D)"""
#mod = 40961
#mod = 998244353, primod = 50475, invmod = 305218526
mod = 2013265921 # 998244353 = 2^23 * (odd number)
primod = 137
"""S = factorization(mod - 1)
S = {2: S[2]}
LL = Vanilla(S)
print(LL)
LL.sort(reverse=True)
for i in range(1, 500):
    flg = (doubling(i, doubling(2, S[2]), mod) == 1)
    for j in range(1, len(LL)):
        flg *= (doubling(i, LL[j], mod) != 1)
    if flg:
        print(i)"""
def powlimit(n):
    y = 1
    cnt = 0
    while y < n:
        y *= 2
        cnt += 1
    return y, cnt

N, M = map(int, input().split())
A = list(map(int, input().split()))
F = [0 for _ in range(max(A)+1)]
for i in range(N):
    F[A[i]] += 1
"""N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]
F = [0] + [AB[i][0] for i in range(N)]
G = [0] + [AB[i][1] for i in range(N)]"""
pl, c = powlimit(2*max(A)+2)
#pl, c = powlimit(2*N+2)
F = F[:] + [0]*(pl-N-1)
prim = [doubling(primod, doubling(2, 27-i), mod) for i in range(27)]
invp = [inved(prim[i]) for i in range(27)]
def NTT(f, n, cn, inverse=False):
    if n == 1:
        return f
    if n == 2:
        return [(f[0]+f[1])%mod, (f[0]-f[1])%mod]
    dn = n // 2
    fe = [f[2*i+0] for i in range(dn)]
    fo = [f[2*i+1] for i in range(dn)]
    fe = NTT(fe, dn, cn-1, inverse)
    fo = NTT(fo, dn, cn-1, inverse)
    seed = inverse * prim[cn] + (1 - inverse) * invp[cn]
    grow = 1
    for i in range(dn):
        right = fo[i] * grow % mod
        f[i+0*dn] = (fe[i] + right) % mod
        f[i+1*dn] = (fe[i] - right) % mod
        grow *= seed
        grow %= mod
    return f

X = NTT(F, pl, c)
#Y = NTT(G, pl, c)
#print(X)
#print(Y)
Z = [X[i]*X[i]%mod for i in range(pl)]
Z = NTT(Z, pl, c, 1)
#print(NTT(Z, pl, c, 1))
ipl = inved(pl)
for i in range(pl):
    Z[i] *= ipl
    Z[i] %= mod
S = 2*max(A)
hp = 0
ccnt = 0
while ccnt < M:
    if ccnt + Z[S] < M:
        ccnt += Z[S]
        hp += S * Z[S]
    else:
        hp += S * (M - ccnt)
        ccnt += M - ccnt
    S -= 1
print(hp)
#for i in range(1, max(A)+1):
#    print(Z[i]*ipl%mod)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)

Pair=[0 for i in range(N)]
for i in range(N-1):
    Pair[i]=A[i]+A[i+1]

print(A)

ans=0
cnt=0
mode=0
Next=[]
i=0
while i<M:
    if mode==0:
        ans+=2*A[cnt]
        mode=1
        Next.append([cnt,cnt+1])
        cnt+=1
        i+=1
    else:
        Max=0
        for j in Next:
            if Max<=A[j[0]]+A[j[1]]:
                Max=A[j[0]]+A[j[1]]
                p_cnt=j
        ans+=A[p_cnt[0]]+A[p_cnt[1]]
        i+=1
        
        if i<=M-1:
            ans+=A[p_cnt[0]]+A[p_cnt[1]]
            i+=1
        Next.remove(p_cnt)
        if p_cnt[1]+1<N:
            p_cnt[1]+=1
            Next.append(p_cnt)
            
        Max=max(Max,A[p_cnt[0]]+A[p_cnt[1]])
        if Max<=A[cnt]*2:
            mode=0
        
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

n, m = map(int, input().split())
a = list(map(int, input().split()))
MAX = 10 ** 5

scores = [0] * (MAX + 1)
for e in a:
    scores[e] += 1

acc = list(accumulate(scores))


def f(x):
    cnt = 0
    for e in a:
        cnt += n - acc[max(0, x - e - 1)]

    return cnt


l = 0
r = 2 * MAX
while r - l > 1:
    mid = (l + r) // 2
    if f(mid) >= m:
        l = mid
    else:
        r = mid

scores_sum = [i * e for i, e in enumerate(scores)]
acc_sum = list(accumulate(scores_sum))
sm = sum(a)
ans = 0
cnt_sum = 0
for e in sorted(a, reverse=True):
    i = max(0, l - e - 1)
    cnt = n - acc[i]
    ans += e * cnt + sm - acc_sum[i]
    cnt_sum += cnt

ans -= (cnt_sum - m) * l

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np 
# 初期入力
N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A =np.array(A)

#
ans =np.zeros((N,N),dtype=np.int64)
for i in range(N):
    ans[i] =A +A[i]

ans = np.reshape(ans,N*N)
ans = np.sort(ans)
print(np.sum(ans[-M:]))

Submission status: Runtime Error

Solution code:
あー０

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import bisect
import itertools
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


import numpy as np


def main():
    N, M = geta(int)
    A = np.array(list(geta(int)))
    A.sort()

    def c(x):
        """
        @return  # of handshake where hapiness >= x
        """
        X = np.searchsorted(A, x - A)
        return N * N - X.sum()

    left, right = 0, 2 * A[-1] + 1

    while left + 1 < right:
        middle = (left + right) // 2
        if c(middle) >= M:
            left = middle
        else:
            right = middle

    ans = 0
    Acum = np.zeros(N + 1, np.int64)
    Acum[:-1] = np.cumsum(A[::-1])[::-1]
    X = np.searchsorted(A, right - A)

    ans = Acum[X].sum() + (A * (N - X)).sum()

    ans += left * (M - (N * N - X.sum()))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

A = np.array(A)
a1 = A.reshape(1,N) * np.ones((N,N))
a2 = A.reshape(N,1) * np.ones((N,N))

A_sum = np.sort( (a1+a2).flatten() )[::-1]

ans = A_sum[:M].sum()

print(int(ans))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[int(i) for i in input().split()]
k=int(m**(1/2)//1)-1
l=sorted(l,reverse=True)
suml=sum(l[:k+1])*2*(k+1)
kk=(k+1)**2
if (m-kk)%2==0:
    suml+=2*sum(l[:int((m-kk)//2)])+(m-kk)*l[k+1]
else:
    suml+=2*sum(l[:int((m-kk)//2)])+l[int((m-kk)//2+1)]+(m-kk)*l[k+1]
print(suml)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    summary = [a[i] + a[j] for i in range(n) for j in range(n)]
    summary.sort(reverse=True)
    ans = 0
    for i in range(m):
      	ans += summary[m]
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    summary = [a[i] + a[j] for i in range(n) for j in range(n)]
    summary.sort(reverse=True)
    ans = 0
    for i in range(m):
      	ans += summary(m)
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
N,M,*A = map(int, open('0').read().split())
A = np.sort(A)
B = np.cumsum(np.concatenate([[0],A[::-1]]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = np.sum(N-np.searchsorted(A,s-A))
  if cnt>=M:
    l = s
  else:
    r = s
ind = np.searchsorted(A,r-A)
M -= np.sum(N-ind)
ans = np.sum(B[N-ind]+A*(N-ind))+M*l
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from itertools import accumulate
N,M,*A = map(int, open('0').read().split())
A.sort()
B = list(accumulate(A[::-1]))
l = -1
r = 10**9
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for c in A:
    i = bisect_left(A,s-c)
    cnt += N-i
  if cnt>=M:
    l = s
  else:
    r = s
ans = 0
for c in A:
  i = bisect_left(A,r-c)
  M -= N-i
  if i<N:
    ans += B[N-1-i]+c*(N-i)
ans += M*l
print(ans)

Submission status: Runtime Error

Solution code:
def isok(arg):
    x = 0
    for i in a:
        if arg - i >= 0:
            if arg-i <= 10**5:
                x += cs[arg-i]
        else:
            x += n
    if x >= m:
        return True
    else:
        return False

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if isok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n,m = map(int,input().split())
a = list(map(int,input().split()))
cs = [0]*(10**5+1)
for i in a:
    cs[i] += 1
for i in range(10**5):
    cs[10**5-i-1] += cs[10**5-i]
h = bisect(10**5*2+1,0)
count = 0
ans = 0
for i in a:
    num = max(0,h-i)
    if num <= 10**5:
        ans += 2*i*cs[num]
    count += cs[num]
ans -= (count-m)*h
print(ans)

Submission status: Runtime Error

Solution code:
def isok(arg):
    x = 0
    for i in a:
        if arg - i >= 0 and arg-i <= 10**5:
            x += cs[arg-i]
        else:
            x += n
    if x >= m:
        return True
    else:
        return False

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if isok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n,m = map(int,input().split())
a = list(map(int,input().split()))
cs = [0]*(10**5+1)
for i in a:
    cs[i] += 1
for i in range(10**5):
    cs[10**5-i-1] += cs[10**5-i]
h = bisect(10**5*2+1,0)
count = 0
ans = 0
for i in a:
    num = max(0,h-i)
    ans += 2*i*cs[num]
    count += cs[num]
ans -= (count-m)*h
print(ans)

Submission status: Runtime Error

Solution code:
def isok(arg):
    x = 0
    for i in a:
        if arg - i >= 0 and arg-i <= 10**5
            x += cs[arg-i]
        else:
            x += n
    if x >= m:
        return True
    else:
        return False

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if isok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n,m = map(int,input().split())
a = list(map(int,input().split()))
cs = [0]*(10**5+1)
for i in a:
    cs[i] += 1
for i in range(10**5):
    cs[10**5-i-1] += cs[10**5-i]
h = bisect(10**5*2+1,0)
count = 0
ans = 0
for i in a:
    num = max(0,h-i)
    ans += 2*i*cs[num]
    count += cs[num]
ans -= (count-m)*h
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate as ac
def isok(arg):
    x = 0
    for i in a:
        if arg - i >= 0:
            x += cs[arg-i]
        else:
            x += n
    if x >= m:
        return True
    else:
        return False

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if isok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n,m = map(int,input().split())
a = list(map(int,input().split()))
cs = [0]*(10**5+1)
for i in a:
    cs[i] += 1
for i in range(10**5):
    cs[10**5-i-1] += cs[10**5-i]
h = bisect(10**5*2+1,0)
count = 0
ans = 0
for i in a:
    num = max(0,h-i)
    ans += 2*i*cs[num]
    count += cs[num]
ans += (m-count)*h
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate as ac
def isok(arg):
    x = 0
    for i in a:
        if arg - i >= 0:
            x += cs[arg-i]
        else:
            x += n
    if x >= m:
        return True
    else:
        return False

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if isok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n,m = map(int,input().split())
a = list(map(int,input().split()))
cs = [0]*(10**5+1)
for i in a:
    cs[i] += 1
for i in range(10**5):
    cs[10**5-i-1] += cs[10**5-i]
h = bisect(10**5*2,0)
count = 0
ans = 0
for i in a:
    num = max(0,h-i+1)
    ans += 2*i*cs[num]
    count += cs[num]
ans += (m-count)*h
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
import bisect

def hantei(now):
    num=0
    for ax in a:
        bi = bisect.bisect_left(a,now-ax)
        num+= bi
#         print(now,ax,bi)
    return n**2-num

mi = a[0]*2-1
ma = a[-1]*2+1
while mi<ma:
    now=(mi+ma)//2
    which = hantei(now)<=m#なんか判定
    if which:
        ma=now
        kotae=now
    else:
        mi=now+1
kotae-=1

suma=[0]*(n+1)
suma[-2]=a[-1]
for i in range(n-2,-1,-1):
    suma[i] = suma[i+1]+a[i]
    
ans=0
kazu=0
for ax in a:
    bi = bisect.bisect_left(a,kotae-ax)
    ans+= (n-bi)*ax+suma[bi]
    kazu+=n-bi
print(ans-(kazu-m)*kotae)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

mod = 10**9+7 #出力の制限

# a = cmb(n,r)
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def ans():
    H,W = m()

    a = []

    for i in range(H):
        a.append(l())

    ma = 0
    b = []
    for i in range(H):
        b.append(l())
        for j in range(W):
            ma = max(ma,abs(a[i][j]-b[i][j]))
    ma += 1
    dp = [[[0 for i in range(ma*(min(H,W)))]for j in range(W)] for k in range(H)]

    for i in range(H):
        for j in range(W):
            if i == 0 and j == 0:
                dp[0][0][abs(a[0][0] - b[0][0])] = 1
            elif i == 0:
                for k in range(ma*(min(H,W))):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
            elif j == 0:
                for k in range(ma*(min(H,W))):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])
            else:
                for k in range(ma*(min(H,W))):
                    if abs(k + abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k + abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k + abs(a[i][j] - b[i][j]))])
                    if abs(k - abs(a[i][j] - b[i][j])) < ma*min(H,W):
                        dp[i][j][abs(k - abs(a[i][j] - b[i][j]))] = max(dp[i][j-1][k],dp[i-1][j][k],dp[i][j][abs(k - abs(a[i][j] - b[i][j]))])

    for i in range(ma*min(H,W)):
        if dp[-1][-1][i] == 1:
            print(i)
            exit()




if __name__ == "__main__":
    ans()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

""" どのパワー以上の組み合わせまで握手するのか二分探索で調べる
    同じパワーとなる組み合わせに注意 """
N, M = lr()
A = np.array(lr(), np.int64)
B = A[:, None] + A[None, :]
B = B.ravel()
B.sort() # 昇順
N = N ** 2
if M == N:
    print(B.sum()); exit()

def check(x):
    # x以上の幸福度と握手した場合、M回以下になる場合、Trueを返す
    i = np.searchsorted(B, x, side='l')
    return (N - i) <= M

ok = 10 ** 5 * 2 + 1; ng = 0
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

i = np.searchsorted(B, ok, side='l')
if i == N:
    answer = B[-1] * M
else:
    time = N - i
    answer = B[i:].sum() + B[i-1] * (M-time)
print(answer)
#

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

""" どのパワー以上の組み合わせまで握手するのか二分探索で調べる
    同じパワーとなる組み合わせに注意 """
N, M = lr()
A = np.array(lr())
B = A[:, None] + A[None, :]
B = B.ravel()
B.sort() # 昇順
N = N ** 2
if M == N:
    print(B.sum()); exit()

def check(x):
    # x以上の幸福度と握手した場合、M回以下になる場合、Trueを返す
    i = B.searchsorted(x, side='l')
    return (N - i) <= M

ok = 10 ** 5 * 2 + 1; ng = 0
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

i = B.searchsorted(ok, side='l')
if i == N:
    answer = B[-1] * M
else:
    time = N - i
    answer = B[i:].sum() + B[i-1] * (M-time)
print(answer)
# 01

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

""" どのパワー以上の組み合わせまで握手するのか二分探索で調べる
    同じパワーとなる組み合わせに注意 """
N, M = lr()
A = np.array(lr())
B = A[:, None] + A[None, :]
B = B.ravel()
B.sort() # 昇順
N = N ** 2
if M == N:
    print(B.sum()); exit()

def check(x):
    # x以上の幸福度と握手した場合、M回以下になる場合、Trueを返す
    i = B.searchsorted(x, side='l')
    return (N - i) <= M

ok = 10 ** 5 + 1; ng = 0
while abs(ng-ok) > 1:
    mid = (ok+ng) // 2
    if check(mid):
        ok = mid
    else:
        ng = mid

i = B.searchsorted(ok, side='l')
time = N - i
answer = B[i:].sum() + B[i-1] * (M-time)
print(answer)
# 01

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import heapq
n,M = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
m = [0]*M
heapq.heapify(m)
# naiveに考えると、max(a)から順番に握手すればいい
# 同じ握手パターンは二度使えないので、aの要素を二度まで使える、という条件の元でソートして上から使っていく
# O(n**2)でTLEだが、sortして、上位Mをとるという操作はしないとどれが何回使われるかはわからない
# heapを使って、毎回minと比較して、minを更新する形にすればいけそう
for i in range(n):
    for j in range(i,n):
        if i == j:
            if m[0] < a[-i-1]*2:
                heapq.heappop(m)
                heapq.heappush(m,a[-i-1]*2)
            else: break
        else:
            if m[0] < a[-i-1]+a[-j-1]:
                heapq.heappop(m)
                heapq.heappush(m,a[-i-1]+a[-j-1])
            else: break
            if m[0] < a[-i-1]+a[-j-1]:
                heapq.heappop(m)
                heapq.heappush(m,a[-i-1]+a[-j-1])
            else: break
print(sum(m))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import heapq
n,M = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
m = []
cnt = 0
# naiveに考えると、max(a)から順番に握手すればいい
# 同じ握手パターンは二度使えないので、aの要素を二度まで使える、という条件の元でソートして上から使っていく
# O(n**2)でTLEだが、sortして、上位Mをとるという操作はしないとどれが何回使われるかはわからない
# heapを使って、毎回minと比較して、minを更新する形にすればいけそう
for i in range(n):
    for j in range(i,n):
        if cnt < M:
            if i == j :
                m.append(a[-i-1]*2)
                cnt += 1
            else: 
                m.append(a[-i-1]+a[-j-1])
                cnt += 1
                if M > cnt:
                    m.append(a[-i-1]+a[-j-1])
                    cnt += 1
            if M == cnt: heapq.heapify(m)
        else:
            if i == j:
                if m[0] < a[-i-1]*2:
                    heapq.heappush(m)
                    heapq.heappop(a[-i-1]*2)
                else: break
            else:
                if m[0] < a[-i-1]+a[-j-1]:
                    heapq.heappush(m)
                    heapq.heappop(a[-i-1]+a[-j-1])
                else: break
                if m[0] < a[-i-1]+a[-j-1]:
                    heapq.heappush(m)
                    heapq.heappop(a[-i-1]+a[-j-1])
                else: break
print(sum(m))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

ans = 0
double = 0
pair = [0, 1, 0]
used_all_pair = False
used_all_double = False

for i in range(M):
    if used_all_double:
        ans += A[pair[0]] +A[pair[1]]
        if pair[0] == N-2 and pair[1] == N-1:
            used_all_pair = True
        elif pair[2] == 1:
            pair[2] = 0
            if pair[1] >= N-1:
                pair[0] +=1
                pair[1] = pair[0] +1
            else:
                pair[1] += 1
        else:
            pair[2] += 1
    elif used_all_pair:
        ans += 2*A[double]
        if double >= N-1:
            used_all_double = True
        double += 1
    elif 2*A[double] >= A[pair[0]] +A[pair[1]]:
        ans += 2*A[double]
        if double >= N-1:
            used_all_double = True
        double += 1
    else:
        ans += A[pair[0]] +A[pair[1]]
        if pair[0] == N-2 and pair[1] == N-1:
            used_all_pair = True
        elif pair[2] == 1:
            pair[2] = 0
            if pair[1] >= N-1:
                pair[0] +=1
                pair[1] = pair[0] +1
            else:
                pair[1] += 1
        else:
            pair[2] += 1
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

ans = 0
double = 0
single = [0, 1, 0]

for i in range(M):
    if 2*A[double] > A[single[0]] +A[single[1]]:
        ans += 2*A[double]
        double += 1
    else:
        ans += A[single[0]] +A[single[1]]
        if single[2] == 1:
            single[2] = 0
            if single[1] >= N-1:
                single[0] +=1
                single[1] = single[0] +1
            else:
                single[1] += 1
        else:
            single[2] += 1
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):
    if q<0 or q>=n or len(a)!=n:
        b=1
        while True:
            b+=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


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):
    if q<0 or q>=n:
        b=1
        while True:
            b+=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


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