Nam có một ổ khóa số gồm ~n~ vòng số. Mỗi vòng số gồm 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ố, trong đó chữ số thứ ~i~ tương ứng với số đang hiển thị của vòng số ~i~.

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

• Xoay theo chiều xuôi sẽ tăng chữ số hiển thị lên ~1~ đơn vị. Nếu chữ số đang là ~9~ thì sau khi tăng sẽ trở thành ~0~.
• Xoay theo chiều ngược sẽ giảm chữ số hiển thị xuống ~1~ đơn vị. Nếu chữ số đang là ~0~ thì sau khi giảm sẽ trở thành ~9~.

Ví dụ:

• ~3 \rightarrow 4~: xoay theo chiều xuôi mất ~1~ giây.
• ~3 \rightarrow 2~: xoay theo chiều ngược mất ~1~ giây.
• ~9 \rightarrow 0~: xoay theo chiều xuôi mất ~1~ giây.
• ~0 \rightarrow 9~: xoay theo chiều ngược mất ~1~ giây.
• ~2 \rightarrow 8~: xoay theo chiều ngược ~2 \rightarrow 1 \rightarrow 0 \rightarrow 9 \rightarrow 8~, mất ~4~ giây.
• ~2 \rightarrow 8~: xoay theo chiều xuôi ~2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8~ lại mất ~6~ giây.

Nam được cho một danh sách gồm ~m~ cấu hình và phải xoay các vòng số để 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.

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

Dữ liệu vào

• Dòng đầu tiên 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 ~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ả

• Một số nguyên duy nhất là thời gian nhỏ nhất cần để thực hiện yêu cầu.

Ví dụ

Đầu vào:

4 3
1234
5678
9012

Đầu ra:

38

Giải thích: Ta xoay các vòng khóa để hiện các cấu hình theo thứ tự: ~0000 \rightarrow 5678 \rightarrow 1234 \rightarrow 9012~.

• Thời gian xoay từ ~0000~ đến ~5678~: ~5 + 4 + 3 + 2 = 14~.
• Thời gian xoay từ ~5678~ đến ~1234~: ~4 + 4 + 4 + 4 = 16~.
• Thời gian xoay từ ~1234~ đến ~9012~: ~2 + 2 + 2 + 2 = 8~.

Tổng thời gian là ~38~. Đây là cách xoay có thời gian ít nhất.

Giới hạn

• ~1 \le n \le 1000~
• ~1 \le m \le 18~

Điểm của một subtask chỉ được tính khi tất cả các test thuộc subtask đó đều đúng.