(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
(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 #.OPT
           ((simple-array uint8 (* *)) cs)
           (uint8 h w init-y init-x k))
  (labels ((drop ()
             (dotimes (col w)
               (let ((level (- h 1)))
                 (loop for row from (- h 1) downto 0
                       when (> (aref cs row col) 0)
                       do (rotatef (aref cs row col) (aref cs level col))
                          (decf level)))))
           (erase (turn)
             (let ((weight 0))
               (declare (uint62 weight))
               (dotimes (row h)
                 (let ((prev 0))
                   (loop for col to 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)))))
               (* (ash 1 turn) weight))))
    (setf (aref cs init-y init-x) 0)
    (drop)
    (loop for turn from 0
          for delta = (erase turn)
          while (> delta 0)
          sum delta
          do (drop))))

(defun main ()
  (let* ((h (read))
         (w (read))
         (k (read))
         (init-cs (make-array (list h (+ w 1)) :element-type 'uint8 :initial-element #xff))
         (cs (make-array (list h (+ w 1)) :element-type 'uint8))
         (res 0))
    (dotimes (y h)
      (dotimes (x w (read-char))
        (setf (aref init-cs y x) (digit-char-p (read-char)))))
    (dotimes (y h)
      (dotimes (x w)
        (replace (array-storage-vector cs) (array-storage-vector init-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: 16872