D. Үсэгт хүснэгт - 2

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

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

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

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

Вася Англи хэл сурж байлаа. Тэр Англи үсэгнүүдийг яаж бичдэг билээ гэж бодсон боловч заримыг нь сайн санахгүй байгаа тул дахиад жаахан хичээллэх хэрэгтэй юм гэж боджээ.

Вася дөрвөлжин цаас олоод үсэгнүүдээ бичиж эхлэв. Тэрээр $n$ мөр бүрт $m$ үсэг бичжээ. Өөрөөр хэлбэл $n × m$ хэмжээ бүхий тэгш өнцөгт хүснэгтийн нүд бүрт англи үсэг тэмдэглэсэн байв. Мөрүүдийг дээрээс нь доош нь $1$-ээс $n$ хүртэл, багануудыг баруунаас зүүн тийш $1$-ээс $m$ хүртэл дугаарлажээ.

Дараа нь Вася дараахь нөхцөлийг хангах дэд хүснэгт хэд байгааг олохыг хүсчээ:

  • дэд хүснэгтийн нүднүүдэд хамгийн ихдээ $k$ ширхэг "$a$" үсэг байна;
  • дэд хүснэгтийн дөрвөн булангийн нүднүүд дэхь үсэгнүүд ижил;

Дэд хүснэгтийг $x_{1}, y_{1}, x_{2}, y_{2}$ ($1 ≤ x_{1} < x_{2} ≤ n$, $1 ≤ y_{1} < y_{2} ≤ m$) гэсэн тоонуудаар тодорхойлж болно. Өөрөөр хэлбэл энэ дэд хүснэгт нь $x_{1} ≤ x ≤ x_{2}, y_{1} ≤ y ≤ y_{2}$ нөхцөлийг хангах бүх $(x, y)$ нүднүүдээс тогтох хүснэгт юм. (Энд $x$ нь мөрийн дугаар, $y$ нь баганын дугаар)

Вася олон үсэг бичээд аль хэдийнээ ядарчихжээ. Тиймээс чамаас дээрх нөхцөлийг хангах дэд хүснэгтийн тоог олж өгөхийг хүсчээ.

Оролт

Эхний мөрөнд $n, m, k$ $(2 ≤ n, m ≤ 400; 0 ≤ k ≤ n \cdot m)$ бүхэл тоонууд байна.

Дараагийн $n$ мөр бүрт $m$ тэмдэг байна. Бүх тэмдэгтүүд Англи цагаан толгойн жижиг үсгүүд байна.

Гаралт

Нөхцлийг хангах дэд хүснэгтийн тоог хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
3 4 4
aabb
baab
baab
Гаралт
2
Оролт
4 5 1
ababa
ccaca
ccacb
cbabc
Гаралт
1

Тэмдэглэл

Эхний жишээнд нөхцлийг хангах $2$ дэд хүснэгт бий:

  • Зүүн дээд нүд нь $(2, 2)$ ба баруун доод нүд нь $(3, 3)$.
  • Зүүн дээд нүд нь $(2, 1)$ ба баруун доод нүд нь $(3, 4)$.
Сэтгэгдлүүдийг ачааллаж байна...