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

;;;
;;; Minimum cost flow (Primal-Dual, O(FElogV))
;;;

(setf *print-circle* t)

;; COST-TYPE and +INF-COST+ may be changed. (A supposed use case is to adopt
;; bignum).
(deftype cost-type () '(signed-byte 32))
(defconstant +inf-cost+ #x7fffffff)
(assert (and (typep +inf-cost+ 'cost-type)
             (subtypep 'cost-type 'integer)))

(defstruct (edge (:constructor %make-edge))
  (to nil :type (integer 0 #.most-positive-fixnum))
  (capacity 0 :type (integer 0 #.most-positive-fixnum))
  (cost 0 :type cost-type)
  (reversed nil :type (or null edge)))

(defun push-edge (from-idx to-idx capacity cost graph)
  "FROM-IDX, TO-IDX := index of vertex
GRAPH := vector of list of all the edges that goes from the vertex"
  (declare ((simple-array list (*)) graph)
           (cost-type cost))
  (let* ((dep (%make-edge :to to-idx :capacity capacity :cost cost))
         (ret (%make-edge :to from-idx :capacity 0 :cost (- cost) :reversed dep)))
    (setf (edge-reversed dep) ret)
    (push dep (aref graph from-idx))
    (push ret (aref graph to-idx))))

;; binary heap for Dijkstra's algorithm
(defstruct (fheap (:constructor make-fheap
                          (size
                           &aux (costs (make-array (1+ size) :element-type 'cost-type))
                                (vertices (make-array (1+ size) :element-type 'fixnum)))))
  (costs nil :type (simple-array cost-type (*)))
  (vertices nil :type (simple-array fixnum (*)))
  (position 1 :type (integer 1 #.most-positive-fixnum)))

(defun fheap-push (cost vertex fheap)
  (declare (optimize (speed 3)))
  (symbol-macrolet ((position (fheap-position fheap)))
    (when (>= position (length (fheap-costs fheap)))
      (setf (fheap-costs fheap)
            (adjust-array (fheap-costs fheap) (* position 2))
            (fheap-vertices fheap)
            (adjust-array (fheap-vertices fheap) (* position 2))))
    (let ((costs (fheap-costs fheap))
          (vertices (fheap-vertices fheap)))
      (labels ((update (pos)
                 (declare (optimize (safety 0)))
                 (unless (= pos 1)
                   (let ((parent-pos (ash pos -1)))
                     (when (< (aref costs pos) (aref costs parent-pos))
                       (rotatef (aref costs pos) (aref costs parent-pos))
                       (rotatef (aref vertices pos) (aref vertices parent-pos))
                       (update parent-pos))))))
        (setf (aref costs position) cost
              (aref vertices position) vertex)
        (update position)
        (incf position)
        fheap))))

(defun fheap-pop (fheap)
  (declare #.OPT)
  (symbol-macrolet ((position (fheap-position fheap)))
    (let ((costs (fheap-costs fheap))
          (vertices (fheap-vertices fheap)))
      (labels ((update (pos)
                 (declare (optimize (safety 0))
                          ((integer 1 #.most-positive-fixnum) pos))
                 (let* ((child-pos1 (+ pos pos))
                        (child-pos2 (1+ child-pos1)))
                   (when (<= child-pos1 position)
                     (if (<= child-pos2 position)
                         (if (< (aref costs child-pos1) (aref costs child-pos2))
                             (unless (< (aref costs pos) (aref costs child-pos1))
                               (rotatef (aref costs pos) (aref costs child-pos1))
                               (rotatef (aref vertices pos) (aref vertices child-pos1))
                               (update child-pos1))
                             (unless (< (aref costs pos) (aref costs child-pos2))
                               (rotatef (aref costs pos) (aref costs child-pos2))
                               (rotatef (aref vertices pos) (aref vertices child-pos2))
                               (update child-pos2)))
                         (unless (< (aref costs pos) (aref costs child-pos1))
                           (rotatef (aref costs pos) (aref costs child-pos1))
                           (rotatef (aref vertices pos) (aref vertices child-pos1))))))))
        (multiple-value-prog1 (values (aref costs 1) (aref vertices 1))
          (decf position)
          (setf (aref costs 1) (aref costs position)
                (aref vertices 1) (aref vertices position))
          (update 1))))))

(declaim (inline fheap-empty-p))
(defun fheap-empty-p (fheap)
  (= (fheap-position fheap) 1))

(declaim (inline fheap-reinitialize))
(defun fheap-reinitialize (heap)
  (setf (fheap-position heap) 1)
  heap)

(define-condition not-enough-capacity-error (error)
  ((graph :initarg :graph :reader not-enough-capacity-error-graph)
   (flow :initarg :flow :reader not-enough-capacity-error-flow))
  (:report
   (lambda (c s)
     (format s "Cannot send ~A units of flow on graph ~A due to not enough capacity."
             (not-enough-capacity-error-flow c)
             (not-enough-capacity-error-graph c)))))

(defun min-cost-flow! (src-idx dest-idx flow graph &key density)
  "Returns the minimum cost to send FLOW units from SRC-IDX to DEST-IDX in
GRAPH. Destructively modifies GRAPH.

DENSITY := nil | the number of edges (assumed to be (size of GRAPH)*2 if NIL)"
  (declare #.OPT
           ((integer 0 #.most-positive-fixnum) flow)
           ((simple-array list (*)) graph))
  (macrolet ((the-cost-type (form)
               (reduce (lambda (x y) `(,(car form) (the cost-type ,x) (the cost-type ,y)))
		       (cdr form))))
    (let* ((size (length graph))
           (density (or density (* size 2)))
           (prev-vertices (make-array size :element-type 'fixnum :initial-element 0))
           (prev-edges (make-array size :element-type 'edge))
           (potential (make-array size :element-type 'cost-type :initial-element 0))
           (dist (make-array size :element-type 'cost-type))
           (pqueue (make-fheap density))
           (res 0))
      (declare (fixnum density)
               (cost-type res))
      (loop while (> flow 0)
            do (fill dist +inf-cost+)
               (setf (aref dist src-idx) 0)
               (fheap-reinitialize pqueue)
               (fheap-push 0 src-idx pqueue)
               (loop until (fheap-empty-p pqueue)
                     do (multiple-value-bind (cost v) (fheap-pop pqueue)
                          (declare (cost-type cost)
                                   (fixnum v))
                          (when (<= cost (aref dist v))
                            (dolist (edge (aref graph v))
                              (let* ((next-v (edge-to edge))
                                     (next-cost (the-cost-type
                                                 (+ (aref dist v)
                                                    (edge-cost edge)
                                                    (aref potential v)
                                                    (- (aref potential next-v))))))
                                (when (and (> (edge-capacity edge) 0)
                                           (> (aref dist next-v) next-cost))
                                  (setf (aref dist next-v) next-cost
                                        (aref prev-vertices next-v) v
                                        (aref prev-edges next-v) edge)
                                  (fheap-push next-cost next-v pqueue)))))))
               (when (= (aref dist dest-idx) +inf-cost+)
                 (error 'not-enough-capacity-error :flow flow :graph graph))
               (let ((max-flow flow))
                 (declare (fixnum max-flow))
                 (dotimes (v size)
                   (setf (aref potential v)
                         (min +inf-cost+
                              (+ (aref potential v) (aref dist v)))))
                 (do ((v dest-idx (aref prev-vertices v)))
                     ((= v src-idx))
                   (setf max-flow (min max-flow (edge-capacity (aref prev-edges v)))))
                 (decf flow max-flow)
                 (incf res (the cost-type (* max-flow (aref potential dest-idx))))
                 (do ((v dest-idx (aref prev-vertices v)))
                     ((= v src-idx))
                   (decf (edge-capacity (aref prev-edges v)) max-flow)
                   (incf (edge-capacity (edge-reversed (aref prev-edges v))) max-flow))))
      res)))

(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)
  (let* ((h (read))
         (w (read))
         (as (make-array (list h w) :element-type 'uint31))
         (graph (make-array (* h w 2) :element-type 'list :initial-element nil)))
    (declare (uint16 h w))
    (labels ((encode (y x dir)
               (let ((res (if (eql dir :in)
                              (* 2 (+ (* w y) x))
                              (+ (* 2 (+ (* w y) x)) 1))))
                 res)))
      (dotimes (i h)
        (dotimes (j w)
          (let ((a (read-fixnum)))
            (setf (aref as i j) a)
            (push-edge (encode i j :in)
                       (encode i j :out)
                       1
                       (- a)
                       graph))))
      (labels ((connect (i1 j1 i2 j2)
                 (when (and (< i2 h) (< j2 w))
                   (push-edge (encode i1 j1 :out) (encode i2 j2 :in) 1 0 graph))))
        (dotimes (i h)
          (dotimes (j w)
            (connect i j i (+ j 1))
            (connect i j (+ i 1) j))))
      (println (+ (aref as 0 0)
                  (aref as (- h 1) (- w 1))
                  (- (min-cost-flow! (encode 0 0 :out)
                                     (encode (- h 1) (- w 1) :in)
                                     2 graph)))))))

#-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 "3 3
1 0 5
2 2 3
4 2 4
"
    "21
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "6 6
1 2 3 4 5 6
8 6 9 1 2 0
3 1 4 1 5 9
2 6 5 3 5 8
1 4 1 4 2 1
2 7 1 8 2 8
"
    "97
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "3 3
1 0 5
2 2 3
4 2 4
"
    "21
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "6 6
1 2 3 4 5 6
8 6 9 1 2 0
3 1 4 1 5 9
2 6 5 3 5 8
1 4 1 4 2 1
2 7 1 8 2 8
"
    "97
")))
