CF229A.Shifts

You are given a table consisting of n rows and m columns. Each cell of the table contains a number, 0 or 1. In one move we can choose some row of the table and cyclically shift its values either one cell to the left, or one cell to the right.

To cyclically shift a table row one cell to the right means to move the value of each cell, except for the last one, to the right neighboring cell, and to move the value of the last cell to the first cell. A cyclical shift of a row to the left is performed similarly, but in the other direction. For example, if we cyclically shift a row "00110" one cell to the right, we get a row "00011", but if we shift a row "00110" one cell to the left, we get a row "01100".

Determine the minimum number of moves needed to make some table column consist only of numbers 1.

给你一个由 $n$ 行 $m$ 列组成的表格。表格的每个单元格中包含一个数字：$0$ 或 $1$。在一次操作中，你可以选择表格的某一行，并将其所有值循环左移或循环右移一格。

将某一行循环右移一格，是指将除最后一列外的所有单元格的值向右移动至相邻的右侧单元格，同时将最后一列单元格的值移至第一列单元格。类似地，循环左移一格的操作方向相反。例如，若将行 "00110" 循环右移一格，则得到 "00011"；若将行 "00110" 循环左移一格，则得到 "01100"。

请确定使表格中某一列全部为 $1$ 所需的最少操作次数。

The first line contains two space-separated integers: n (1 ≤ n ≤ 100) — the number of rows in the table and m (1 ≤ m ≤ 104) — the number of columns in the table. Then n lines follow, each of them contains m characters "0" or "1": the j-th character of the i-th line describes the contents of the cell in the i-th row and in the j-th column of the table.

It is guaranteed that the description of the table contains no other characters besides "0" and "1".

第一行包含两个以空格分隔的整数：$n$（$1 ≤ n ≤ 100$）—— 表格的行数，以及 $m$（$1 ≤ m ≤ 10^4$）—— 表格的列数。随后是 $n$ 行，每行包含 $m$ 个字符，每个字符为 "0" 或 "1"：第 $i$ 行的第 $j$ 个字符表示表格中第 $i$ 行、第 $j$ 列单元格的内容。

保证表格的描述中仅包含字符 "0" 和 "1"，不包含其他任何字符。

Print a single number: the minimum number of moves needed to get only numbers 1 in some column of the table. If this is impossible, print -1.

输出一个整数：使表格中某一列的所有数字都变为 1 所需的最少移动次数。若无法实现，输出 -1。

In the first sample one way to achieve the goal with the least number of moves is as follows: cyclically shift the second row to the right once, then shift the third row to the left twice. Then the table column before the last one will contain only 1s.

In the second sample one can't shift the rows to get a column containing only 1s.

在第一个样例中，以最少移动次数达成目标的一种方法如下：将第二行循环右移一次，然后将第三行循环左移两次。此时，倒数第二列将全部由 1 组成。

在第二个样例中，无法通过行移位操作得到一列全为 1 的列。