A. Ширээ

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

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

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

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

Саймонд $n$ мөр, and $m$ баганаас бүтсэн тэгш өнцөгт ширээ байдаг. Тэр ширээний мөрүүдийг дээрээс нь доош нь, багануудыг нь зүүнээс баруун тийш тус тус нэгээс эхлэн дугаарлажээ. Бид $х$ мөр, $у$ багана дахь нүдийг ($x,y$) тооны хослолоор тэмдэглэх болно. Ширээний булангууд нь: ($1,1$), ($n,1$), ($1,m$), ($n,m$) нүднүүд болно.

Саймон ширээний зарим нүднүүдийг “сайн” нүднүүд гэж үзнэ. Мөн ширээний булангийн нүднүүд “сайн” нүд биш гэдэг мэдэгдэж байгаа болно.

Эхний байдлаар ширээний бүх нүднүүд өнгөгүй байна. Саймон ширэний бүх нүднүүдийг будахыг хүсдэг. Нэг үйлдлээр ширээний аль нэг сайн нүд ($x_1,y_1$), ширээний дурын нэг булан ($x_2,y_2$)-ийг сонгон авах бөгөөд дараах 2 тэнцэтгэл бишийг зэрэг хангаж буй бүх ($p,q$) нүднүүдийг будна: $min(x_1, x_2) ≤ p ≤ max(x_1, x_2)$, $min(y_1, y_2) ≤ q ≤ max(y_1, y_2)$.

Саймонд тусалж ширээний бүх нүднүүдийг будахад хийх үйлдлүүдийн тооны хамгийн бага утгыг ол. Нэг нүдийг хэд хэдэн удаа будаж болохыг санаарай.

Оролт

Эхний мөрөнд $n, $m$ (3 ≤ n, m ≤ 50)$ гэсэн 2 бүхэл тоо байна.

Дараагийн $n$ мөрүүд ширээний нүднүүдийн тодорхойлолтуудыг агуулна. i дүгээр мөр хоосон зайгаар тусгаарлагдсан $m$ ширхэг $a_{i1}$, $a_{i2}$, ..., $a_{im}$ бүхэл тоонуудыг агуулна. Хэрэв $a_{ij} = 0$ байвал ($i, j$) нүд “сайн” нүд биш болно. Өөрөөр хэлбэл $a_{ij} = 1$ байна. Оролтонд дор хаяж нэг нүд “сайн” нүд байгаа. Мөн “сайн” нүд булан биш байна.

Гаралт

Саймон санаагаа биелүүлэхэд шаардагдах үйлдлүүдийн хамгийн бага утга.

Орчуулсан: Энхдүүрэн, zoloogg

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

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

Тэмдэглэл

In the first sample, the sequence of operations can be like this:

  • For the first time you need to choose cell $(2, 2)$ and corner $(1, 1)$.
  • For the second time you need to choose cell $(2, 2)$ and corner $(3, 3)$.
  • For the third time you need to choose cell $(2, 2)$ and corner $(3, 1)$.
  • For the fourth time you need to choose cell $(2, 2)$ and corner $(1, 3)$.

In the second sample the sequence of operations can be like this:

  • For the first time you need to choose cell $(3, 1)$ and corner $(4, 3)$.
  • For the second time you need to choose cell $(2, 3)$ and corner $(1, 1)$.
Сэтгэгдлүүдийг ачааллаж байна...