Ổ khóa số

Nam có một ổ khóa số gồm ~n~ vòng số. Mỗi vòng chứa các chữ số theo thứ tự từ ~0~ đến ~9~. Một cấu hình của ổ khóa được biểu diễn bởi một xâu gồm ~n~ chữ số; chữ số thứ ~i~ là số đang hiển thị ở vòng thứ ~i~.

Ban đầu, ổ khóa ở cấu hình gồm ~n~ chữ số ~0~. Mỗi giây, Nam có thể xoay đúng một vòng số một đơn vị theo một trong hai chiều:

• Xoay theo chiều xuôi làm chữ số tăng một đơn vị; ~9~ chuyển thành ~0~.
• Xoay theo chiều ngược làm chữ số giảm một đơn vị; ~0~ chuyển thành ~9~.

Nam được cho danh sách ~m~ cấu hình phân biệt và phải làm cho mỗi cấu hình xuất hiện ít nhất một lần. Các cấu hình có thể xuất hiện theo thứ tự bất kỳ, nhưng cấu hình xuất hiện cuối cùng phải là cấu hình thứ ~m~ trong danh sách.

Hãy xác định thời gian nhỏ nhất để thực hiện yêu cầu.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên ~n, m~ ~(1 \le n \le 1000; 1 \le m \le 18)~.
• ~m~ dòng tiếp theo, mỗi dòng chứa một xâu gồm đúng ~n~ chữ số biểu diễn một cấu hình.
• Các cấu hình đôi một khác nhau.

Kết quả

In ra một số nguyên duy nhất: thời gian nhỏ nhất cần để thực hiện yêu cầu.

Ví dụ

Dữ liệu vào

4 3
1234
5678
9012

Kết quả

38

Một thứ tự tối ưu là ~0000 \rightarrow 5678 \rightarrow 1234 \rightarrow 9012~, với tổng thời gian ~14 + 16 + 8 = 38~.

Ràng buộc

• Subtask 1 (~10\%~ số điểm): ~m = 3~.
• Subtask 2 (~30\%~ số điểm): ~m \le 8~.
• Subtask 3 (~60\%~ số điểm): không có ràng buộc bổ sung.

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 256 MB.