There is a binary matrix, mat, that consists of n rows and m columns. Each of the cells contains either 0 or 1. In one shift operation, select any row of the matrix and cyclically shift its values either to the left or to the right. In the cyclic left shift of a row, the value at each cell except for the first cell is shifted to one cell left, and the value at the first cell is moved from the beginning to the end. Similarly, in the cyclic right shift of a row, the value at each cell except for the last cell is shifted to one cell right, and the value at the last cell is moved from the end to the beginning.

Determine the minimum number of shifts needed to make at least one column consist only of cell values equal to 1. Print -1 if it's not possible to do so.

Note : The input matrix is given in the form of a string array of length n. Each of the ith string represents the ith row of the matrix. The length of each string is equal to the numbr of columns in the matrix.

matrix = ["0101","1010","0100","0001"]

One possible solution

1. Cyclically shift row 1 to the right. (*0101" -> "1010")
2. Cyclically shift row 3 to the right. (*0100" -> "0010")
3. Cyclically shift row 4 to the left. (0001 -> "0010")

The minimum shifts required to make at least one column, the third column, consist only of 1s is 3.