D. Сережа ба хүснэгт

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

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

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

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

Сережад $n × m$ хэмжээтэй тэгш өнцөгт $a$ хүснэгт байсан ба хүснэгтийн нүд бүр нь нэг эсвэл тэгийг агуулна. Сережа хүснэгтээ дараах шаардлагыг хангасан байхыг хүсчээ:

Ижил утгуудаар холбогдсон тэгш өнцөгт хэлбэртэй хэсэг бүрийн талууд нь хүснэгтийн талуудтай парелель. Хэрвээ тэгш өнцөгт хэлбэртэй хэсэг нь $h × w$ хэмжээтэй бол бүрэлдэхүүн хэсгүүд нь яг $hw$ нүднүүд агуулсан байх ба нүднүүд нь дүүрэн байх ёстой.

Ижил утгуудаар холбогдсон бүрэлдэхүүн хэсэг нь дараах нөхцлийг хангасан хүснэгтийн нүднүүдийн олонлог байна:

  • Олонлогийн ямар ч хоёр нүд нь ижил утгатай байна
  • Олонлогийн нүднүүд нь хүснэгтэд холбогдсон мужийг үүсгэдэг (Хэрвээ хүснэгтийн зарим мөр эсвэл баганууд зэрэгцээ бол тухайн хоёр нүд нь холбогдсон байна)
  • Хэрвээ өмнөх хоёр нөхцлийг бид зөрчөөгүй бол олонлогт ямар нэг нүд нэмэх боломжгүй.

Хүснэгтийн заасан шаардлагыг хангасан байхын тулд Сережа нүднүүдийн хамгийн ихдээ $k$ утгыг өөрчилнө. Энэ тохиолдолд өөрчлөх шаардлагатай хүснэгтийн нүднүүдийн хамгийн бага тоо хэд байх вэ?

Оролт

Эхний мөр нь $n$, $m$, $k$ $(1 ≤ n, m ≤ 100; 1 ≤ k ≤ 10)$ бүхэл тоонуудыг агуулна. Дараагийн $n$ мөр бүр нь хүснэгтийг тодорхойлох $a$: $i$-р мөр нь $m$ бүхэл тоо $a_{i1}, a_{i2}, ..., a_{im}$ $(0 ≤ a_{i, j} ≤ 1)$ агуулна.

Гаралт

Шаардлагыг хангах боломжгүй бол -1 гэж хэвлэнэ. Эсрэг тохиолдолд, өөрчлөх хэрэгтэй нүднүүдийн хамгийн бага тоог хэвлэх.

Орчуулсан: Даариймаа

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

Оролт
5 5 2
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
Гаралт
1
Оролт
3 4 1
1 0 0 0
0 1 1 1
1 1 1 0
Гаралт
-1
Оролт
3 4 1
1 0 0 1
0 1 1 0
1 0 0 1
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...