;; -*- 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
(defstruct (stair-sum (:constructor %make-stair-sum))
  (cumul nil :type (simple-array (unsigned-byte 62) (*)))
  (stair nil :type (simple-array (unsigned-byte 62) (*))))

(declaim (inline make-stair-sum))
(defun make-stair-sum (vector)
  "Makes a table from VECTOR that stores 0, VECTOR[0], VECTOR[0] + 2*VECTOR[1],
VECTOR[0] + 2*VECTOR[1] + 3*VECTOR[2], ..."
  (let* ((n (length vector))
         (cumul (make-array (+ n 1) :element-type '(unsigned-byte 62) :initial-element 0))
         (stair (make-array (+ n 1) :element-type '(unsigned-byte 62) :initial-element 0)))
    (dotimes (i n)
      (setf (aref stair (+ i 1))
            (+ (aref stair i) (* (+ i 1) (aref vector i)))
            (aref cumul (+ i 1))
            (+ (aref cumul i) (aref vector i))))
    (%make-stair-sum :cumul cumul :stair stair)))

(declaim (inline stair-sum-query))
(defun stair-sum-query (stair-sum l r)
  "Returns VECTOR[L] + 2*VECTOR[L+1] + 3*VECTOR[L+2] + ... + (R-L)*VECTOR[R-1]."
  (symbol-macrolet ((stair (stair-sum-stair stair-sum))
                    (cumul (stair-sum-cumul stair-sum)))
    (the uint62 (- (- (aref stair r)
                      (aref stair l))
                   (the uint62 (* l (- (aref cumul r)
                                       (aref cumul l))))))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (declare #.OPT)
  (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
;;;

(declaim (inline calc-distribution))
(defun calc-distribution (total num)
  (declare (uint31 total num))
  (multiple-value-bind (smaller rem) (floor total num)
    (if (zerop rem)
        `((,smaller . ,num))
        (let ((larger-num (- total (* smaller num))))
          `((,(+ 1 smaller) . ,larger-num) .
            (,smaller . ,(- num larger-num)))))))

(declaim (inline get-next))
(defun get-next (distribution)
  (assert (cdr distribution))
  (let* ((node1 (car distribution))
         (node2 (cdr distribution))
         (num1 (cdr node1))
         (num2 (cdr node2)))
    (declare (uint31 num1 num2))
    (if (= num1 1)
        (rplacd node2 (+ num2 1))
        (cons (rplacd node1 (- num1 1)) (rplacd node2 (+ num2 1))))))

(declaim (inline calc-coefficient))
(defun calc-coefficient (distribution)
  (if (cdr distribution)
      (destructuring-bind ((size1 . num1) . (size2 . num2)) distribution
        (declare (uint31 size1 num1 size2 num2))
        (+ (the uint62 (* num1 (expt (+ size1 1) 2)))
           (the uint62 (* num2 (expt (+ size2 1) 2)))
           num1
           num2))
      (destructuring-bind ((size . num)) distribution
        (declare (uint31 size num))
        (+ (* num (expt (+ size 1) 2))
           num))))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (x (read))
         (xs (make-array n :element-type 'uint31))
         (dxs (make-array n :element-type 'uint31))
         (cumul (make-array (+ n 1) :element-type 'uint31 :initial-element 0))
         (res #xffffffffffffffffff))
    (declare (uint31 n x))
    (dotimes (i n)
      (setf (aref xs i) (read-fixnum)
            (aref dxs i) (- (aref xs i) (if (zerop i) 0 (aref xs (- i 1))))
            (aref cumul (+ i 1)) (+ (aref cumul i) (aref dxs i))))
    (let ((stair-sum (make-stair-sum dxs)))
      (loop for k from 1 to n
            for cost-sum of-type unsigned-byte = 0
            for n/k of-type uint31 = (floor n k)
            do (when (> n (* k n/k))
                 (let* ((end (- n (* k n/k)))
                        (base-coef (calc-coefficient (calc-distribution n k)))
                        (delta-coef (+ 1 (* 2 (+ n/k 1))))
                        (cost (- (* base-coef
                                    (- (aref cumul end) (aref cumul 0)))
                                 (* delta-coef
                                    (stair-sum-query stair-sum 1 end)))))
                   (declare (uint31 end delta-coef)
                            (uint62 base-coef))
                   (incf cost-sum cost)))
            do (loop for m from n/k above 0
                     for base-index of-type uint31 = (- n (* k m))
                     for size of-type uint31 = (floor (* m k) k)
                     for base-coef of-type uint62 = (+ (* k (expt (+ size 1) 2)) k)
                     for delta-coef of-type uint31 = (if (= 1 m) 5 (+ 1 (* 2 m)))
                     for cost = (- (* base-coef
                                      (- (aref cumul (+ base-index k))
                                         (aref cumul base-index)))
                                   (* delta-coef
                                      (stair-sum-query stair-sum
                                                       (+ base-index 1)
                                                       (+ base-index k))))
                     do (incf cost-sum cost))
               (setq res (min res (+ (* k x) cost-sum)))))
    ;; 拾うコストNXは最後に足す
    (println (+ res (* x n)))))

#-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 "200000 1000000000~%")
    (let ((xs (loop repeat 200000 collect (+ 1 (random #.(expt 10 9))))))
      (setq xs (sort xs #'<))
      (dolist (x xs)
        (println x 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 "2 100
1 10
"
    "355
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "5 1
1 999999997 999999998 999999999 1000000000
"
    "19999999983
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "10 8851025
38 87 668 3175 22601 65499 90236 790604 4290609 4894746
"
    "150710136
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "16 10
1 7 12 27 52 75 731 13856 395504 534840 1276551 2356789 9384806 19108104 82684732 535447408
"
    "3256017715
")))


Measured memory_bytes: 60004