Giải bài trực tuyến

Hôm nay, Naruto bắt đầu làm quen với máy tính. Chương trình đầu tiên mà cậu được học là paint :D . Và tất nhiên,đã học là phải có bài tập về nhà, Naruto được giao cho 1 bức tranh đen trắng. Bức tranh là 1 hình chữ nhật m dòng n cột, mỗi một ô chỉ tô 1 trong 2 màu: đen hoặc trắng. Nhiệm vụ của Naruto là phải vẽ lại giống y hệt bức tranh này trên paint !!!

Nhưng với tính nghịch ngợm của mình, Naruto nào có chịu ngồi im trong lớp nghe giảng nên cậu chẳng biết phải làm thế nào để thực hành bài tập về nhà cả. Không muốn bị thầy giáo phạt, cậu đành phải làm bài tập theo một cách rất chi là thủ công như sau : phóng to trang giấy vẽ lên cho đến khi có thể nhìn thấy từng điểm ảnh, rồi sau đo chép lại bức tranh bằng cách tô đen hoặc tô trắng từng điểm ảnh một !!! Và để tránh nhầm lẫn, Naruto sẽ chép lại từng cột một. Đầu tiên, Naruto sẽ chọn trên trang vẽ một cột i bất kì, so sánh sang cột i ở bức tranh mẫu, nếu thấy 2 điểm ảnh tương ứng nào không giống nhau thì tô lại điểm ảnh đó trên tranh vẽ của mình. Sau khi tô xong cột đầu tiên này, từ lần thứ 2 trở đi, Naruto sẽ vẽ tiếp theo quy tắc sau

- Chọn 1 cột j bất kì chưa từng được chon trước đó, copy nguyên cột i vừa vẽ lên cột j rồi so sánh sang cột j ở bức tranh mẫu, nếu thấy 2 điểm ảnh tương ứng nào không giống nhau thì tô lại điểm ảnh đó trên tranh vẽ của mình

- Chọn cột j chưa từng được chọn trước đó,j là một trong 2 cột ở cạnh cột vừa tô (j=i+1 hoặc j=i-1), so sánh cột j với cột tương ứng ở bức tranh mẫu, nếu thấy 2 điểm ảnh tương ứng nào không giống nhau thì tô lại điểm ảnh đó trên tranh vẽ của mình

Trang vẽ ban đầu toàn là màu trắng. Thời gian để chỉnh sửa lại 1 điểm ảnh là 1s, thời gian để copy 1 cột và paste vào 1 cột khác là không đáng kể. Bạn hãy giúp Naruto tính xem cậu ta sẽ phải mất ít nhất bao nhiêu lâu để hoàn thành bài tập của mình.

Input

Dòng đầu là 2 số m,n (m<10001, n<16) - độ lớn của bức tranh mẫu

m dòng sau thể hiện bức tranh mẫu, mỗi dòng là 1 dãy gồm n phần tử mang 1 trong 2 giá trị: 0 hoặc 1, 0 thể hiện cho màu trắng và ngược lại.

Output

Ghi ra thời gian ngắn nhất Naruto hoàn thành bài tập của mình

Example

Input:
3 4
0000
0110
0000

Output:
1

Giải thích test đề bài: đầu tiên Naruto se chọn tô cột 1,thời gian để tô xong cột 1 la 0s, copy cột 1 sang cột 4,chỉnh sửa lại mất 0s,chuyển sang tô cột 3 bên cạnh hết 1s, copy cột 3 paste lên cột 2.Vậy Naruto hết 1s để hoàn thành bức tranh