Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P146PROE - ROUND 6E - Dịch chuyển

Bạn được cho một bảng số n dòng và m cột. Mỗi ô chỉ chứa ký tự ‘0’ hoặc ‘1’. Một bước di chuyển trên bảng là chọn một hàng trên bảng và dịch chuyển các ô sang ô bên cạnh theo phía bên trái hoặc bên phải (dịch vòng).

Ví dụ với hàng gồm “00110”, với một bước di chuyển sang phải ta sẽ được “00011”, nếu sang trái sẽ là “01100”. Nếu dịch sang phải 2 bước, ta sẽ được "10001".

Nhiệm vụ của bạn là tìm xem cần di chuyển ít nhất bao nhiêu bước để bảng có ít nhất 1 cột toàn các số 1.

Input

Dòng đầu tiên gồm 2 số nguyên : n là số hàng của bảng (1<=n <=100) và m là số cột của bảng (1<= m <=10^4).

n dòng tiếp theo, mỗi dòng gồm m kí tự thể hiện cho bảng với các ký tự 0 và 1.

Output

In ra số bước dịch chuyển ít nhất để đạt được mục đích của bài toán. Nếu không có phương án nào, in ra -1.

Example

Test 1:

Input:

3 6
101010
000100
100000

Output:

3

Giải thích test 1: Một trong những cách tối ưu là dịch hàng 2 sang trái 1 bước,
và dịch hàng 3 sang phải 2 bước.

Test 2:

Input:

2 3
111
000

Output:

-1


Test 3:

Input:

4 6
000001
100000
100000
100000

Output:

1

Giải thích test 3: Dịch hàng 1 sang phải 1 bước.

 


Được gửi lên bởi:adm
Ngày:2014-03-11
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-MONKEY JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.