output_description: Print the maximum possible happiness after M handshakes.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 A_2 ... A_N
attempt: N, M = map(int, input().split())
  A = list(map(int, input().split()))
  # A=[1,3,5,8]
  
  B = sorted(A, reverse=True)
  A = sorted(A)
  print(A)
  print(B)
  
  
  def sumc(X, A, B):
      w = 0
      s = 0
      k = 0
      ans = 0
      a = len(A)
      b = len(B)
      for i in range(a):
          r = X - A[i]
          for j in range(s, b):
  
              if B[j] >= r:
                  w = j + 1
                  k = j
              else:
                  k = j
                  break
              # if(B[b-1]>=r):
              # k=b-1
          s = k
          ans += w
          # print(w)
          # print(ans)
      return ans
  
  
  def suml(X, A, B):
      w = 0
      s = 0
      k = 0
      ans = 0
      a = len(A)
      b = len(B)
      # D=[0]*a
      # L=[0]*b
      for i in range(a):
          r = X - A[i]
          # D[i]=s
          for j in range(s, b):
              if B[j] >= r:
                  w = j + 1
                  k = j
  
                  # D[i]+=1
                  # L[j]=a-i]
                  ans += B[j] * (a - i)
              else:
                  k = j
                  break
  
          s = k
          ans += w * A[i]
  
          """
          for i in range(a):
              ans+=A[i]*D[i]
          for i in range(b):
              ans+=B[i]*L[i]
          """
      return ans
  
  
  # ans=sum(8,A,B)
  # print(ans)
  def binary(S, E, M, K):
      X = int((S + E) / 2)
      n = sum(X, A, B)
      if n > M:
          binary(X, E, M, K)
  
      if n < M:
          binary(S, X, M, K)
  
      if n == M:
          K = X
  
  
  S = 2 * A[0]
  E = 2 * A[N - 1]
  X = int((S + E) / 2)
  while 1:
      n = sumc(X, A, B)
      m = sumc(X + 1, A, B)
      if n >= M and M > m:
          break
      if n >= M:
          S = X
          X = int((E + X) / 2)
  
      if n < M:
          E = X
          X = int((S + X) / 2)
  
  
  print(X)
  # binary(S,E,M,K)
  k = sumc(X, A, B)
  print(k)
  s = 0
  ans = 0
  w = 0
  if k == M:
      """
      for i in range(N):
          r=X-A[i]
          for j in range(s,N):
              if(B[j]>=r):
                  w=j+1
                  ans+=B[j]*(N-i)
              else:
                  k=j
                  break
              if(B[N-1]>=r):
                  k=N-1
          s=k
          ans+=A[i]*w
      """
      ans = suml(X, A, B)
  else:
      print("a")
      X = X + 1
  
      t = sumc(X, A, B)
      # print(t)
      # print(X-1)
      ans = suml(X, A, B)
      ans += (M - t) * (X - 1)
  
  print(ans)
  
problem_description: 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?
samples: [{"input": "5 3\n    10 14 19 34 33", "output": "202\n    \n\nLet us say that Takahashi performs the following handshakes:\n\n  * In the first handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 4.\n  * In the second handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 5.\n  * In the third handshake, Takahashi shakes the left hand of Guest 5 and the right hand of Guest 4.\n\nThen, we will have the happiness of (34+34)+(34+33)+(33+34)=202.\n\nWe cannot achieve the happiness of 203 or greater, so the answer is 202.\n\n* * *"}, {"input": "9 14\n    1 3 5 110 24 21 34 5 3", "output": "1837\n    \n\n* * *"}, {"input": "9 73\n    67597 52981 5828 66249 75177 64141 40773 79105 16076", "output": "8128170"}]