Rôn mua một bộ đèn trang trí gồm \(n\) đèn (\(1 \le n \le 1000\)). Mỗi đèn có một công tắc để bật hay tắt riêng đèn đó. Mỗi giây Rôn có thể bật hoặc tắt một bóng đèn tùy chọn. Ban đầu tất cả các bóng đều ở trạng thái tắt. Một cấu hình của bộ đèn là trạng thái khi một số đèn nào đó được bật sáng, những đèn còn lại tắt. Rôn đặc biệt thích một số cấu hình vì chúng có vẻ phù hợp với khung cảnh căn phòng của Rôn.

Mỗi trạng thái của bộ đèn được biểu diễn bằng một xâu \(n\) ký tự từ tập \(\{0, 1\}\). Ký tự thứ \(i\) xác định trạng thái đèn thứ \(i\), \(0\) tương ứng với trạng thái đèn tắt, \(1\) tương ứng với trạng thái đèn được bật sáng. Ví dụ, với \(n = 3\) và Rôn đặc biệt thích \(3\) cấu hình \(\{1, 0, 1\}, \{0, 1, 0\}, \{1, 1, 1\}\). Để kiểm tra xem cấu hình nào là thích hợp nhất Rôn phải lần lượt bật tắt một số đèn. Trong trường hợp này Rôn cần \(4\) giây để xem xét hết mọi cấu hình.

Yêu cầu

Cho biết \(n\) và \(m\), trong đó \(m\) là số cấu hình khác nhau mà Rôn đặc biệt yêu thích (\(1 \le m \le 15\)). Hãy xác định thời gian tối thiểu cần thiết để kiểm tra hết tất cả các trạng thái mà Rôn quan tâm.

Input

• Dòng đầu tiên chứa \(2\) số nguyên \(n\) và \(m\).
• Mỗi dòng trong \(m\) dòng tiếp theo chứa xâu \(n\) ký tự xác định một cấu hình Rôn yêu thích.

Output

• Một số nguyên duy nhất là thời gian tối thiểu để kiểm tra hết các cấu hình.

Example

3 3
101
010
111

4

Constraints

• \(1 \le n \le 1000\).
• \(1 \le m \le 15\).