A. Шилжилт

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

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

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

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

Танд $n$ мөртэй $m$ баганатай хүснэгт өгөгдөв. Нүд бүрт 0 юмуу 1 гэсэн тоо байна. Та нэг үйлдлээр дурийн мөрийг сонгон авч баруун юмуу зүүн тийш нь нэг нүдээр шилжүүлж чадна.

Баруун тийш нэг нүд шилжүүлнэ гэдэг нь хамгийн сүүлийн нүд нь эхэнд ирж бусад бүх нүд баруун тийш болно. Зүүн шилжилт нь нөгөө зүгрүү л болохоос бусад нь ижил. Жишээ нь энэ "$00110$" мөрийг баруун тийш нэг шилжилт хийвэл ийм "$00011$" болно. энэ "$00110$" мөрийг зүүн тийш нэг нүд шилжүүлвэл "$01100$" болно.

Хүснэгтийн аль нэгэн баганыг зөвхөн нэгүүдээр бүтсэн байлгахын тулд хамгийн багадаа хэдэн үйлдэл хийх хэрэгтэйг олно уу.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 100$) мөрний тоо, $m$ ($1 ≤ m ≤ 10^{4}$) баганы тоо. Дараагийн $n$ мөрөнд $m$ ширхэг 1 эсвэл 0 -с бүтсэн тэмдэгтүүд. $i$-дэх мөрний $j$-дэх тэмдэгт нь хүснэгтийн $i$-дэх мөрний $j$-дэх баганы нүдийг илэрхийлнэ.

Хүснэгт "$0$" болон "$1$" -с өөр тоо агуулагүй нь баттай.

Гаралт

Хариу болох ганц тоог хэвлэнэ үү. Хэрвээ боломжгүй бол -1 гэж хэвлэнэ үү.

Орчуулсан: anhaabc

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

Оролт
3 6
101010
000100
100000
Гаралт
3
Оролт
2 3
111
000
Гаралт
-1

Тэмдэглэл

Эхний жишээний хувьд зорилгодоо хүрэхийн тулд хийж байгаа үйлдэл нь: 2 дахь мөрийг баруун тийш ганц удаа, 3 дахь мөрийг зүүн тийш 2 удаа. Ингэснээр сүүлээсээ 2 дахь багана бүгд 1 болно.

Хоёр дахь жишээн дээр 2 дахь мөрөнд 0 байхгүй учир боломжгүй.

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