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: #!/usr/bin/env python3
  import sys
  
  input = sys.stdin.readline
  import cmath
  
  pi = cmath.pi
  exp = cmath.exp
  
  
  def fft(a, inverse=False):
      n = len(a)
      h = n.bit_length() - 1
  
      # Swap
      for i in range(n):
          j = 0
          for k in range(h):
              j |= (i >> k & 1) << (h - 1 - k)
          if i < j:
              a[i], a[j] = a[j], a[i]
  
      # Butterfly calculation
      if inverse:
          sign = 1.0
      else:
          sign = -1.0
      b = 1
      while b < n:
          for j in range(b):
              w = exp(sign * 2.0j * pi / (2.0 * b) * j)
              for k in range(0, n, b * 2):
                  s = a[j + k]
                  t = a[j + k + b] * w
                  a[j + k] = s + t
                  a[j + k + b] = s - t
          b *= 2
  
      if inverse:
          for i in range(n):
              a[i] /= n
  
      return a
  
  
  def ifft(a):
      return fft(a, inverse=True)
  
  
  def convolve(f, g):
      n = 2 ** ((len(f) + len(g) - 1).bit_length())
      f += [0] * (n - len(f))
      g += [0] * (n - len(g))
      F = fft(f)
      G = fft(g)
      FG = [Fi * Gi for Fi, Gi in zip(F, G)]
      fg = [int(item.real + 0.5) for item in ifft(FG)]
      return fg
  
  
  if __name__ == "__main__":
      n, m = map(int, input().split())
      a = [int(item) for item in input().split()]
      max_a = max(a)
      freq = [0] * (max_a + 1)
      for item in a:
          freq[item] += 1
      f = freq[:]
      g = freq[:]
      fg = convolve(f, g)
      total = sum(a) * n * 2
      cnt = n * n - m
      for i, item in enumerate(fg):
          use = min(cnt, item)
          total -= i * use
          cnt -= use
          if cnt == 0:
              break
      print(total)
  
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"}]