给你一个由 n 行和 m 列组成的表。表中的每个单元格都包含一个数字 0 或 1。在一次移动中,我们可以选择表中的某一行,然后循环将其值向左移动一个单元格,或者向右移动一个单元格。
将表格行循环向右移动一个单元格意味着将除最后一个单元格之外的每个单元格的值移动到右相邻单元格,并将最后一个单元格的值移动到第一个单元格。行向左循环移位的执行方式类似,但方向相反。例如,如果我们将行“00110”循环向右移动一个单元格,我们会得到一行“00011”,但如果我们将行“00110”向左移动一个单元格,我们会得到一行“01100”。
确定使某些表列仅包含数字 1 所需的最小移动次数。
输入
第一行包含两个以空格分隔的整数:n (1 ≤ n ≤ 100) - 表中的行数和 m (1 ≤ m ≤ 104) - 表中的列数。接下来n行,每行包含m个字符“0”或“1”:第i行的第j个字符描述了表格第i行第j列的单元格的内容。
保证表的描述中不包含除“0”和“1”之外的其他字符。
输出
打印单个数字:在表格的某列中仅得到数字 1 所需的最少移动次数。如果不可能,则打印 -1。
示例
输入 #1
3 6 101010 000100 100000
输出 #1
3
输入 #2
2 3 111 000
输出 #2
-1
注意
在第一个示例中,以最少的移动次数实现目标的一种方法如下:循环地将第二行向右移动一次,然后将第三行向左移动两次。那么最后一列之前的表列将只包含 1。
在第二个示例中,无法移动行以获得仅包含 1 的列。