B. Сережа ба толин тусгал

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

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

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

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

Бидэнд $x × y$ хэмжээтэй $b$ матриц өгөгдсөн гэж үзээд $b$ матрицийн толин тусгалын үйлдлийг тодорхойлцгооё. $b$ матрицийн толин тусгал $2x × y$ хэмжээтэй $c$ матриц нь дараах шинж чанаруудтай:

  • $c$ матрицийн дээд хагас ($1$-с $x$ дугаартай мөрүүд) нь яг $b$ матриц байна;
  • $c$ матрицийн доод хагас ($x + 1$-с $2x$ дугаартай мөрүүд) нь дээдэхтэй тэгш хэмтэй; тэгш хэмийн шугам нь дундуур нь хоёр хэсэгт тусгаарласан шугам юм ($x$ ба $x + 1$ мөрүүдийн голоор нь явсан шугам).

Сережад $n × m$ хэмжээтэй $a$ матриц байна. Тэр $b$ матрицийг олохыг хүсэж байгаа ба хэрвээ бид хэд хэдэн толин тусгал (0 орохгүй) үйлдэл хийх бол $a$ матриц хувирч болно. Агуулсан матрицийн хамгийн бага мөрийн тоо хэд байх вэ?

Оролт

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

Гаралт

Асуултын хариултыг нэг мөрөнд хэвлэнэ. $b$ матрицийн хамгийн бага мөрийн тоо.

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

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

Оролт
4 3
0 0 1
1 1 0
1 1 0
0 0 1
Гаралт
2
Оролт
3 3
0 0 0
0 0 0
0 0 0
Гаралт
3
Оролт
8 1
0
1
1
0
0
1
1
0
Гаралт
2

Тэмдэглэл

Эхний жишээний хариулт нь $b$ матриц $2 × 3$ хэмжээтэй:

001  
110

Хэрвээ бид энэ матриц дээр толин тусгалын үйлдэл хийх юм бол оролтонд өгөгдсөн $a$ матрицийг авах болно:

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