Hoán Vị Cột Số · canuc80k0723 · Thuật toán Canuc80k

Cho $n$ xâu, mỗi xâu gồm đúng $k$ chữ số. Chọn một hoán vị của $k$ vị trí và sắp lại các vị trí của mọi xâu bằng cùng hoán vị đó. Sau biến đổi, mỗi xâu được đọc như một số thập phân; các chữ số $0$ ở đầu vẫn chỉ đóng vai trò giữ vị trí. Hãy tối thiểu hóa hiệu giữa số lớn nhất và số nhỏ nhất.

Input

Dòng đầu chứa $n$ và $k$ . Trong $n$ dòng tiếp theo, mỗi dòng chứa một xâu đúng $k$ chữ số.

Output

In giá trị nhỏ nhất có thể của $max - min$ sau khi áp dụng một hoán vị cột chung.

Constraints

$1 \leq n \leq 8, 1 \leq k \leq 8$ .
Mỗi hàng có đúng $k$ ký tự thuộc $0, \dots, 9$ .

Scoring

Subtask $1$ ( $50%$ ): $k \leq 6$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

2 2
01
10

Output

Giải thích: Hai hoán vị cột cho các cặp số $(1, 10)$ và $(10, 1)$ . Cả hai đều có hiệu $9$ , nên đáp án là $9$ .

Ý tưởng: Quyết định duy nhất là thứ tự chung của k cột. Sau khi cố định một hoán vị, có thể đọc lại từng xâu theo thứ tự đó, rồi lấy hiệu giữa giá trị lớn nhất và nhỏ nhất.
Thuật toán: Duyệt mọi hoán vị của các chỉ số 0..k-1. Với mỗi hoán vị, tạo giá trị của từng hàng bằng cách ghép chữ số theo thứ tự đang xét, đồng thời cập nhật nhỏ nhất và lớn nhất. Dùng hiệu của hai giá trị này để cải thiện đáp án.
Tính đúng đắn: Mọi phép biến đổi hợp lệ tương ứng duy nhất với một hoán vị cột và đều được duyệt. Với một hoán vị cố định, thuật toán áp dụng đúng cùng thứ tự cho tất cả hàng và tính chính xác cực tiểu, cực đại của các số nhận được. Vì vậy giá trị nhỏ nhất qua toàn bộ hoán vị là tối ưu.
Độ phức tạp: Thời gian O(k!·n·k), bộ nhớ phụ O(k).