(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
           #\# #\> (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)

(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)

;; BEGIN_INSERTED_CONTENTS
(macrolet ((def (name fname)
             `(define-modify-macro ,name (new-value) ,fname)))
  (def minf min)
  (def maxf max)
  (def mulf *)
  (def divf /)
  (def iorf logior)
  (def xorf logxor)
  (def andf logand))

;;;
;;; Sort multiple vectors
;;;

;; TODO: throw an error if there are two ore more identical vectors in the given
;; vectors

(declaim (inline %median3))
(defun %median3 (x y z order)
  (if (funcall order x y)
      (if (funcall order y z)
          y
          (if (funcall order z x)
              x
              z))
      (if (funcall order z y)
          y
          (if (funcall order x z)
              x
              z))))

(defun parallel-sort! (vector order &rest vectors)
  "Destructively sorts VECTOR w.r.t. ORDER and applies the same permutation to
all the vectors in VECTORS.

Note: not randomized; shuffle the inputs if necessary"
  (declare (vector vector))
  (labels
      ((recur (left right)
         (when (< left right)
           (let* ((l left)
                  (r right)
                  (pivot (%median3 (aref vector l)
                                   (aref vector (ash (+ l r) -1))
                                   (aref vector r)
                                   order)))
             (declare ((integer 0 #.most-positive-fixnum) l r))
             (loop (loop while (funcall order (aref vector l) pivot)
                         do (incf l 1))
                   (loop while (funcall order pivot (aref vector r))
                         do (decf r 1))
                   (when (>= l r)
                     (return))
                   (rotatef (aref vector l) (aref vector r))
                   (dolist (v vectors)
                     (rotatef (aref v l) (aref v r)))
                   (incf l 1)
                   (decf r 1))
             (recur left (- l 1))
             (recur (+ r 1) right)))))
    (recur 0 (- (length vector) 1))
    vector))

#+sbcl
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-c:define-source-transform parallel-sort! (vector order &rest vectors)
    (let ((vec (gensym))
          (vecs (loop for _ in vectors collect (gensym))))
      `(let ((,vec ,vector)
             ,@(loop for v in vectors
                     for sym in vecs
                     collect `(,sym ,v)))
         (labels
             ((recur (left right)
                (when (< left right)
                  (let* ((l left)
                         (r right)
                         (pivot (%median3 (aref ,vec l)
                                          (aref ,vec (ash (+ l r) -1))
                                          (aref ,vec r)
                                          ,order)))
                    (declare ((integer 0 #.most-positive-fixnum) l r))
                    (loop (loop while (funcall ,order (aref ,vec l) pivot)
                                do (incf l 1))
                          (loop while (funcall ,order pivot (aref ,vec r))
                                do (decf r 1))
                          (when (>= l r)
                            (return))
                          (rotatef (aref ,vec l) (aref ,vec r))
                          ,@(loop for sym in vecs
                                  collect `(rotatef (aref ,sym l) (aref ,sym r)))
                          (incf l 1)
                          (decf r 1))
                    (recur left (- l 1))
                    (recur (+ r 1) right)))))
           (recur 0 (- (length ,vec) 1))
           ,vec)))))

(defun parallel-shuffle! (vector &rest vectors)
   "Destructively shuffles VECTOR and applies the same permutation to all the
vectors in VECTORS."
  (loop for i from (- (length vector) 1) above 0
        for j = (random (+ i 1))
        do (rotatef (aref vector i) (aref vector j))
           (dolist (v vectors)
             (rotatef (aref v i) (aref v j)))
        finally (return vector)))

#+sbcl
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-c:define-source-transform parallel-shuffle! (vector &rest vectors)
    (let ((vec (gensym))
          (vecs (loop for _ in vectors collect (gensym))))
      `(let ((,vec ,vector)
             ,@(loop for v in vectors
                     for sym in vecs
                     collect `(,sym ,v)))
         (loop for i from (- (length ,vec) 1) above 0
               for j = (random (+ i 1))
               do (rotatef (aref ,vec i) (aref ,vec j))
                  ,@(loop for sym in vecs
                          collect `(rotatef (aref ,sym i) (aref ,sym j)))
               finally (return ,vec))))))

(in-package :cl-user)

(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)))

(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 solve (n xs ys ps k seconds)
  (declare #.OPT
           ((simple-array int32 (*)) xs ys ps)
           (uint8 n k))
  (let ((on-set (make-array k :element-type 'int32 :initial-element 0))
        (off-set (make-array n :element-type 'int32 :initial-element 0))
        ;; 0: horizontal, 1: vertical
        (dirs (make-array k :element-type 'bit :initial-element 0)))
    (parallel-shuffle! xs ys ps)
    (dotimes (i n)
      (if (< i k)
          (setf (aref on-set i) i
                (aref dirs i) (random 2))
          (setf (aref off-set (- i k)) i)))
    (labels ((calc-score ()
               (loop for x across xs
                     for y across ys
                     for p across ps
                     sum (* p (min (loop for idx across on-set
                                         for dir across dirs
                                         minimize (if (zerop dir)
                                                      (abs (- y (aref ys idx)))
                                                      (abs (- x (aref xs idx)))))
                                   (abs y)
                                   (abs x)))
                     of-type fixnum)))
      (let* ((min-score (calc-score))
             (current-score min-score)
             (count 0)
             (kick-count 0))
        (declare (fixnum min-score current-score count))
        (sb-int:with-progressive-timeout (get-remaining-time :seconds seconds)
          (loop (minf min-score current-score)
                (when (eq 0 (get-remaining-time))
                  #>kick-count
                  (return min-score))
                (let ((i (random k))
                      (j (random (- n k)))
                      (flip (random 2)))
                  (rotatef (aref on-set i) (aref off-set j))
                  (xorf (aref dirs i) flip)
                  (let ((score (calc-score)))
                    (cond ((< score current-score)
                           (setq current-score score
                                 count 0))
                          ((= score current-score)
                           (incf count))
                          (t
                           (rotatef (aref on-set i) (aref off-set j))
                           (xorf (aref dirs i) flip)
                           (incf count))))
                  ;; kick
                  (when (>= count 1000)
                    (incf kick-count)
                    (parallel-shuffle! xs ys ps)
                    (setq current-score (calc-score))))))))))

(defun main ()
  (let* ((n (read))
         (xs (make-array n :element-type 'int32 :initial-element 0))
         (ys (make-array n :element-type 'int32 :initial-element 0))
         (ps (make-array n :element-type 'int32 :initial-element 0)))
    (dotimes (i n)
      (setf (aref xs i) (read)
            (aref ys i) (read)
            (aref ps i) (read)))
    (println (loop for x across xs
                   for y across ys
                   for p across ps
                   sum (* p (min (abs x) (abs y)))))
    (loop for k from 1 below n
          do (println (if (member k (list 1 (- n 2)))
                          (solve n xs ys ps k 0.02d0)
                          (solve n xs ys ps k 0.24d0))))
    (println 0)))

#-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)
    #+os-windows (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)
    #+os-unix (run-program "xsel" '("-b" "-o") :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 "15~%")
    (dotimes (_ 15)
      (format out "~D ~D ~D~%"
              (- (random 20000) 10000)
              (- (random 20000) 10000)
              (+ 1 (random 1000000))))))

#+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 "3
1 2 300
3 3 600
1 4 800
"
    "2900
900
0
0
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "5
3 5 400
5 3 700
5 5 1000
5 7 700
7 5 400
"
    "13800
1600
0
0
0
0
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "6
2 5 1000
5 2 1100
5 5 1700
-2 -5 900
-5 -2 600
-5 -5 2200
"
    "26700
13900
3200
1200
0
0
0
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "8
2 2 286017
3 1 262355
2 -2 213815
1 -3 224435
-2 -2 136860
-3 -1 239338
-2 2 217647
-1 3 141903
"
    "2576709
1569381
868031
605676
366338
141903
0
0
0
")))


Measured memory_bytes: 24940