F. Ээжид өгөх бэлэг

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Тэнгэрт хэдэн од байдаг вэ? Залуу програмист Поликарпус энэ асуултыг толгойноосоо авч чаддаггүй ээ! Тэр дижитал камераа ашиглан одот тэнгэрийн зургийг аваад хар цагаан дижитал зураг үүсгэхээр судалж эхлэв. Зураг нь тус бүр нь $m$ тооны тэмдэгтийг агуулах $n$ ширхэг мөрөөс бүрдсэн тэгш өнцөгт матрицаар дүрслэгдэж болно. Зургийн пиксель нь цагаан өнгөтэй бол "1", хар бол "0" байна.

Поликарпус цагаан өнгөтэй 4 пикселиэр хүрээлэгдсэн цагаан өнгийн пиксель олбол тэр зурагнаас од олсон гэж үзнэ.

 1   
111  
 1

Зураг дээрх од

Поликарпус зурагнаас тэгш өнцөгт хэсгийг хайчлан авч ээждээ бэлэг болгон өгөхийг хүсч байлаа. Энэ хэсэг нь $k$-аас багагүй тооны од агуулсан байх ёстой. Оддын зурган дээрх цагаан пикселиүд нь огтлолцож болно. Тэгш өнцөгт хэсгээ зургийн талуудтай параллелиэр шулуун тайрна.

Поликарпус одоо дээр өгөгдсөн нөхцөлийг хангадаг зургийг тайрах хэдэн арга байгааг бодсоор байна. Энэхүү тоог олоход Поликарпуст туслаарай.

Оролт

Оролтын эхний мөр нь $n, m$, $k$ ($1≤n, m≤500; 1≤k≤nm$) бүхэл тоонуудыг агуулна. Дараагийн $n$ мөрүүд нь өгөгдсөн зургийн тайлбарыг дараалсан мөрүүд хэлбэрээр агуулна. Мөр тус бүр нь "0" эсвэл "1"-ээс бүрдэх $m$ ширхэг тэмдэгтүүдийг агуулна.

С++ хэлэнд $64$ битийн бүхэл тоог унших, бичихдээ %lld тодорхойлогчийг битгий ашиглаарай. Харин %I64d тодорхойлогчийг эсвэл cin, cout урсгалуудыг ашиглах нь дээр байдаг.

Гаралт

Өгөгдсөн зургийн шаардлагатай хэсгүүдийн тоог хэвлээрэй.

Орчуулсан: Солонго

Жишээ тэстүүд

Оролт
4 6 2
111000
111100
011011
000111
Гаралт
6
Оролт
5 5 4
11111
11111
11111
11111
11111
Гаралт
9

Тэмдэглэл

Бид доорх жишээнүүнэд мөр болон баганыг $1$-ээс эхлэн дугаарлав. $p$-р мөр, $q$-р баганы нүдийг $(p, q)$ координатаар илэрхийлэв.

Эхний жишээнд, Поликарпус эсрэг булан нь $(1, 1)$ ба ($3, 4$) нүднүүдэд байх ямар ч тэгш өнцөгтийг тайрч болно. Эсрэг булангууд нь $(1, 1)$ ба ($x, y$) байх тэгш өнцөгтүүд өгөгдсөн нөхцөлийг хангана. Энд, $x≥3$ ба $y≥4$ байна.

Хоёр дахь жишээнд, талууд нь $4$-өөс багагүй байх бүх тэгш өнцөгтүүд байж болно. Боломжит тэгш өнцөгтийн хэмжээ нь $4×4$, $4×5$, $5×4$, $5×5$ байна. Дээрх тохиолдлуудад тайрах арга нь харгалзан $4$, $2$, $2$, $1$ байна.

Сэтгэгдлүүдийг ачааллаж байна...