(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
(declaim (inline map-indices))
(defun map-indices (function max-indices)
  "Applies function to each vector of indices smaller than MAX-INDICES. The
consequence is undefined when the vector is modified in FUNCTION."
  (declare (vector max-indices))
  (let* ((size (length max-indices))
         (indices (make-array size :element-type (array-element-type max-indices))))
    (labels ((recur (pos)
               (declare ((integer 0 #.array-dimension-limit) pos))
               (if (= pos size)
                   (funcall function indices)
                   (dotimes (idx (the (integer 0 #.most-positive-fixnum)
                                      (aref max-indices pos)))
                     (setf (aref indices pos) idx)
                     (recur (+ pos 1))))))
      (recur 0))))

(defmacro do-indices ((var end-indices) &body body)
  "DO-style macro for MAP-INDICES"
  `(block nil (map-indices (lambda (,var) ,@body) ,end-indices)))

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

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

(defconstant +inf+ most-positive-fixnum)
(defun main ()
  (let* ((n (read))
         (xs (make-array n :element-type 'int16 :initial-element 0))
         (ys (make-array n :element-type 'int16 :initial-element 0))
         (ps (make-array n :element-type 'uint31 :initial-element 0))
         (vcosts (make-array (list (ash 1 n) n) :element-type 'uint62 :initial-element 0))
         (hcosts (make-array (list (ash 1 n) n) :element-type 'uint62 :initial-element 0)))
    (declare ((integer 1 15) n))
    (dotimes (i n)
      (setf (aref xs i) (read)
            (aref ys i) (read)
            (aref ps i) (read)))
    (labels
        ((initialize (costs coords)
           (dotimes (bits (ash 1 n))
             (dotimes (i n)
               (let ((coord (aref coords i)))
                 (setf (aref costs bits i)
                       (* (aref ps i)
                          (min (if (zerop bits)
                                   +inf+
                                   (loop for j below n
                                         when (logbitp j bits)
                                         minimize (abs (- coord (aref coords j)))))
                               (abs (aref xs i))
                               (abs (aref ys i))))))))))
      (initialize vcosts xs)
      (initialize hcosts ys))
    (let ((univ (make-array n :element-type 'uint4 :initial-element 3))
          (res (make-array (+ n 1) :element-type 'uint62 :initial-element +inf+)))
      (declare ((simple-array uint4 (*)) univ))
      (do-indices (trits univ)
        (let ((vbits 0)
              (hbits 0))
          (declare (uint31 vbits hbits))
          (dotimes (i n)
            (cond ((= (aref trits i) 1)
                   (setf (ldb (byte 1 i) vbits) 1))
                  ((= (aref trits i) 2)
                   (setf (ldb (byte 1 i) hbits) 1))))
          (minf (aref res (logcount (logxor vbits hbits)))
                (loop for i below n
                      sum (min (aref vcosts vbits i)
                               (aref hcosts hbits i))
                      of-type uint62))))
      (map () #'println res))))

#-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: 32548