(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 print-matrix))
(defun print-matrix (array &key (separator #\ ) (key #'identity) (row-start 0) row-end (col-start 0) col-end)
  (declare ((array * (* *)) array)
           ((integer 0 #.most-positive-fixnum) row-start col-start))
  (let ((row-end (or row-end (array-dimension array 0)))
        (col-end (or col-end (array-dimension array 1))))
    (declare ((integer 0 #.most-positive-fixnum) row-end col-end))
    (loop for i from row-start below row-end
          do (loop for j from col-start below col-end
                   do (unless (= j col-start)
                        (princ separator))
                      (write (funcall key (aref array i j))))
          (terpri))))

(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 solve (cs h w init-y init-x k)
  (declare ((simple-array uint8 (* *)) cs)
           (uint8 h w init-y init-x))
  (labels
      ((drop ()
         (dotimes (col w)
           (let ((level (- h 1)))
             (loop for row from (- h 1) downto 0
                   for value = (aref cs row col)
                   do (when (> value 0)
                        (rotatef (aref cs row col) (aref cs level col))
                        (decf level))))))
       (erase (turn)
         (declare (uint8 turn)
                  (values uint62))
         (let ((weight 0))
           (declare (uint62 weight))
           (dotimes (row h)
             (let ((prev 0))
               (loop for col from 1 below w
                     do (when (or (zerop (aref cs row col))
                                  (/= (aref cs row prev) (aref cs row col)))
                          (when (>= (- col prev) k)
                            (incf weight (* (aref cs row prev) (- col prev)))
                            (loop for j from prev below col
                                  do (setf (aref cs row j) 0)))
                          (setq prev col))
                     finally (when (>= (- col prev) k)
                               (incf weight (* (aref cs row prev) (- col prev)))
                               (loop for j from prev below col
                                     do (setf (aref cs row j) 0))))))
           (* (ash 1 turn) weight))))
    (let ((res 0))
      (declare (uint62 res))
      (setf (aref cs init-y init-x) 0)
      (drop)
      ;; (print-matrix cs :separator "")
      (loop for turn from 0
            for delta = (erase turn)
            while (> delta 0)
            do (incf res delta)
               (drop)
               ;; (print-matrix cs :separator "")
               ;; (terpri)
            )
      res)))

(defun main ()
  (let* ((h (read))
         (w (read))
         (k (read))
         (original-cs (make-array (list h w) :element-type 'uint8))
         (cs (make-array (list h w) :element-type 'uint8))
         (res 0))
    (dotimes (y h)
      (let ((line (read-line)))
        (dotimes (x w)
          (setf (aref original-cs y x)
                (digit-char-p (aref line x))))))
    (when (= k 1)
      (println (- (reduce #'+ (array-storage-vector original-cs))
                  (reduce #'min (array-storage-vector original-cs))))
      (return-from main))
    (dotimes (y h)
      (dotimes (x w)
        (replace (array-storage-vector cs)
                 (array-storage-vector original-cs))
        (setq res (max res (solve cs h w y x k)))))
    (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)
    (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 "4 4 2
3413
4121
1424
2312
"
    "23
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4 4 2
1212
2121
1212
2121
"
    "54
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "7 7 2
8989898
9898989
8989898
9898989
8989898
9898989
8989898
"
    "2520
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "17 17 2
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456
91234567891234567
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456
"
    "2354638
")))


Measured memory_bytes: 19816