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: import sys
  
  input_methods = ["clipboard", "file", "key"]
  using_method = 1
  input_method = input_methods[using_method]
  
  IN = lambda: map(int, input().split())
  mod = 1000000007
  
  # +++++
  
  
  def count_al(al, vv):
      """
      vvv以上を集めた場合、何要素選択されるか。
      """
      rui = 0
      for v in al:
          r = get_ok_index(v, al, vv)
          rui += r
      return rui
  
  
  def get_ok_index(v, al, ok_value):
      """
      ok_value以上の要素数を返す。
      """
      if v + al[0] < ok_value:
          return 0
      if v + al[-1] >= ok_value:
          return len(al)
      ok = 0
      ng = len(al)
      while ok + 1 < ng:
          # pa((ok,ng))
          m = (ok + ng) // 2
          if v + al[m] >= ok_value:
              ok = m
          else:
              ng = m
          # pa((ok,ng))
      return ok + 1
  
  
  def main():
      n, m = IN()
      al = list(IN())
      al.sort(reverse=True)
      if m == n * n:
          ret = sum(al) * n * 2
  
      ruisekiwa = al.copy()
      for i, v in enumerate(al[1:], 1):
          ruisekiwa[i] = ruisekiwa[i - 1] + v
      pa(ruisekiwa)
  
      ok = al[0] * 10
      ng = 0
  
      while ok > ng + 1:
          vv = (ok + ng) // 2
          cc = count_al(al, vv)
          pa(("ok,ng,vv,cc", ok, ng, vv, cc))
          if cc <= m:
              ok = vv
          else:
              ng = vv
      pa(("ok", ok))
  
      ret = 0
      for v in al:
          ok_id = get_ok_index(v, al, ok) - 1
          pa(ok_id)
          if ok_id == -1:
              continue
          ret += ruisekiwa[ok_id] + v * (ok_id + 1)
  
      ret += (ok - 1) * (m - count_al(al, ok))
      print(ret)
  
  
  # +++++
  isTest = False
  
  
  def pa(v):
      if isTest:
          print(v)
  
  
  def input_clipboard():
      import clipboard
  
      input_text = clipboard.get()
      input_l = input_text.splitlines()
      for l in input_l:
          yield l
  
  
  if __name__ == "__main__":
      if sys.platform == "ios":
          if input_method == input_methods[0]:
              ic = input_clipboard()
              input = lambda: ic.__next__()
          elif input_method == input_methods[1]:
              sys.stdin = open("inputFile.txt")
          else:
              pass
          isTest = True
      else:
          pass
          # input = sys.stdin.readline
  
      ret = main()
      if ret is not None:
          print(ret)
  
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"}]