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...0 (~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.

Input

• 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.

Output

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.

Scoring

Sample Input 1

4 3
1234
5678
9012

Sample Output 1

38

Notes

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.