;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           ;; enclose the form with VALUES to avoid being captured by LOOP macro
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (inline bisect-right))
(defun bisect-right (target value &key (start 0) end (order #'<) (key #'identity))
  "TARGET := vector | function (taking an integer argument)
ORDER := strict order

Analogue of upper_bound of C++ or bisect_right of Python: Returns the smallest
index (or input) i that fulfills TARGET[i] > VALUE. In other words, this
function returns the rightmost index at which VALUE can be inserted with keeping
the order. Therefore, TARGET must be monotonically non-decreasing with respect
to ORDER.

This function returns END if VALUE >= TARGET[END-1]. Note that the range [START,
END) is half-open. END must be explicitly specified if TARGET is function. KEY
is applied to each element of TARGET before comparison."
  (declare (function key order)
           (integer start)
           ((or null integer) end))
  (macrolet
      ((body (accessor &optional declaration)
         `(progn
            (assert (<= start end))
            (if (= start end)
                end
                (labels
                    ((%bisect-right (left ok)
                       ;; TARGET[OK] > VALUE always holds (assuming
                       ;; TARGET[END] = +infinity)
                       ,@(list declaration)
                       (let ((mid (ash (+ left ok) -1)))
                         (if (= mid left)
                             (if (funcall order value (funcall key (,accessor target left)))
                                 left
                                 ok)
                             (if (funcall order value (funcall key (,accessor target mid)))
                                 (%bisect-right left mid)
                                 (%bisect-right mid ok))))))
                  
                  (%bisect-right start end))))))
    (etypecase target
      (vector
       (when (null end)
         (setf end (length target)))
       (body aref (declare ((integer 0 #.most-positive-fixnum) left ok))))
      (function
       (assert end () "Requires END argument if TARGET is a function.")
       (body funcall)))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48)
                              (* 10 (the (integer 0 #.(floor most-positive-fixnum 10))
                                         result))))
              (return (if minus (- result) result))))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(defun main ()
  (declare #.OPT
           (inline sort))
  (let* ((n (read))
         (m (read))
         (as (make-array n :element-type 'uint31)))
    (declare ((simple-array uint31 (*)) as))
    (dotimes  (i n)
      (let ((a (read-fixnum)))
        (setf (aref as i) a)))
    (setq as (sort as #'>))
    (let ((cumuls (make-array (+ n 1) :element-type 'uint62)))
      (dotimes (i n)
        (setf (aref cumuls (+ i 1))
              (+ (aref as i) (aref cumuls i))))
      (labels ((%calc-sum (pivot threshold)
                 (declare (uint62 pivot threshold))
                 (let ((sup (bisect-right as
                                          (- threshold (aref as pivot))
                                          :order #'>)))
                   (+ (the uint62 (* sup (aref as pivot)))
                      (aref cumuls sup))))
               (calc-sum (threshold)
                 (loop for i below n
                       sum (%calc-sum i threshold) of-type uint62))
               (%calc-count (pivot threshold)
                 (declare (uint62 pivot threshold))
                 (let ((sup (bisect-right as
                                          (- threshold (aref as pivot))
                                          :order #'>)))
                   sup))
               (calc-count (threshold)
                 (loop for i below n
                       sum (%calc-count i threshold) of-type uint62)))
        (sb-int:named-let bisect ((ok -1) (ng 10000000))
          (declare (int32 ng ok))
          (if (<= (- ng ok) 1)
              (let ((actual-count (calc-count ok))
                    (sum (calc-sum ok)))
                (assert (>= actual-count m))
                (println
                 (- sum (* (- actual-count m) ok))))
              (let ((mid (ash (+ ng ok) -1)))
                (if (>= (calc-count mid) m)
                    (bisect mid ng)
                    (bisect ok mid)))))))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    ;; (run-program "C:/Windows/System32/WindowsPowerShell/v1.0/powershell.exe" '("get-clipboard") :output out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "5 3
10 14 19 34 33
"
    "202
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "9 14
1 3 5 110 24 21 34 5 3
"
    "1837
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076
"
    "8128170
")))


Measured memory_bytes: 39652