E. Цэцэрлэг

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

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

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

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

Васяд $n*m$ квадратад хуваагдсан $n × m$ тэгш өнцөгт бүхий маш үзэсгэлэнтэй цэцэрлэг байгаа. Нэг сайхан өдөр Вася ургамал агуулсан $k$ чухал квадратуудын хооронд зам байгуулах хэрэгтэй гэдгийг санасан. Зам малтахын тулд тэр өөрийн цэцэрлэгийн зарим квадратуудыг бетоноор хучиж чадна.

Цэцэрлэгийн квадрат бүрийн хувьд бид $a_{ij}$ тоог мэдэх ба энэ тоо нь $(i, j)$ координаттай квадратад ургасан цэцгийн тоо байна. Квадратыг бетоноор хучихад квадрат дотор ургасан бүх цэцэг үхнэ.

Вася дараах нөхцөлүүд биелэж байхаар зарим квадратуудыг бетоноор хучихаар шийдсэн:

  • бүх $k$ квадратууд бетоноор хучигдсан байх ёстой
  • чухал квадрат бүрээс өөр дурын чухал квадратруу очих зам байх ёстой. Бетоноор хучигдах зам нь нэг талтай квадратууд буюу хөрш квадратуудаас бүрдсэн зам байна.
  • үхсэн ургамалуудын тоо хамгийн бага байх ёстой

Вася нилээн том цэцэрлэгтэй учир таны тусламжийг хүсч байна.

Оролт

Эхний мөрөнд гурван бүхэл тоон утга $n$, $m$ ба $k$ ($1 ≤ n, m ≤ 100$, $n*m ≤ 200$, $1 ≤ k ≤ min(n*m, 7$)) байх буюу цэцэрлэгийн хэмжээсүүд болон чухал квадратуудын тоо байна. Дараагийн $n$ мөр бүрт $m$ бүхэл тоон утга $a_{ij}$ ($1 ≤ a_{ij} ≤ 1000$) байх буюу квадратуудад байгаа цэцгүүдийн тоо юм. Дараагийн $k$ мөрөнд чухал квадратуудын координатууд "$x$ $y$" (хашилтгүйгээр) ($1 ≤ x ≤ n$, $1 ≤ y ≤ m$) хэлбэртэй байна. Бүх $k$ чухал квадратууд ялгаатай координаттай байна.

Гаралт

Эхний мөрөнд зам барих хугацаанд үхэх ургамалуудын хамгийн бага тоо болох бүхэл тоон утгыг хэвлэ. Тэгээд тус бүртээ $m$ тэмдэгт агуулсан $n$ мөр байх буюу цэцэрлэгийн төлөвлөгөө байна. Энэ төлөвлөгөөнд "$X$" (Латин том X үсэг) нь бетоноор хучигдсан квадратыг илэрхийлэх ба "." (цэг) нь бетоноор хучигдаагүй квадратыг илэрхийлнэ. Хэрвээ хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 3 2
1 2 3
1 2 3
1 2 3
1 2
3 3
Гаралт
9
.X.
.X.
.XX
Оролт
4 5 4
1 4 5 1 2
2 2 2 2 7
2 4 1 4 5
3 2 1 7 1
1 1
1 5
4 1
4 4
Гаралт
26
X..XX
XXXX.
X.X..
X.XX.
Сэтгэгдлүүдийг ачааллаж байна...