Xâu may mắn

Time limit: 1.0s , Memory limit: 256M , Points: 3000 (partial)

Cho hai xâu $s$ ~s~ và $t$ ~t~ đều có độ dài $n$ ~n~, xâu chỉ bao gồm các ký tự chữ số từ 0 đến 9.

Cho danh sách gồm $m$ ~m~ xâu may mắn, mỗi xâu đều có độ dài $n$ ~n~ và chỉ bao gồm các ký tự chữ số từ 0 đến 9.

Thực hiện thao tác sau trên xâu $s$ ~s~:

Chọn một ký tự thứ $i$ ~i~ $(1 \le i \le n)$ ~(1 \le i \le n)~ của xâu $s$ ~s~ và thay thế nó bằng ký tự liền kề ở sau $($ ~(~0 ->1, 1 -> 2, $...$ ~...~ , 8 -> 9, 9 -> 0 $)$ ~)~ hoặc thay thế nó bằng ký tự liền kề ở trước $($ ~(~9 ->8, 8 -> 7, $...$ ~...~ , 1 -> 0, 0 -> 9 $)$ ~)~.

Lưu ý rằng sau mỗi thao tác thực hiện, xâu $s$ ~s~ mới thu được, hoặc là xâu $t$ ~t~, hoặc là một xâu may mắn nằm trong danh sách đã cho.

Bạn hãy xác định số lần thực hiện thao tác ít nhất để biến đổi xâu $s$ ~s~ trở thành xâu $t$ ~t~.

Dòng đầu tiên chứa hai số nguyên $n$ ~n~ và $m$ ~m~ $(1 \le n,m)$ ~(1 \le n,m)~.
Dòng thứ hai chứa xâu $s$ ~s~ độ dài $n$ ~n~.
Dòng thứ ba chứa xâu $t$ ~t~ độ dài $n$ ~n~.
$m$ ~m~ dòng tiếp theo, mỗi dòng chứa một xâu may mắn độ dài $n$ ~n~.
Dữ liệu đảm bảo các xâu đã cho đều chỉ chứa các ký tự chữ số từ 0 đến 9.

In ra số lần thực hiện thao tác ít nhất để biến đổi xâu $s$ ~s~ trở thành xâu $t$ ~t~. Nếu không thể biến đổi xâu $s$ ~s~ thành xâu $t$ ~t~, in ra :(

:(

Subtask $1$ ~1~ $-$ ~-~ $500$ ~500~ điểm: $n = 1$ ~n = 1~ $;$ ~;~ $m \le 10$ ~m \le 10~
Subtask $2$ ~2~ $-$ ~-~ $500$ ~500~ điểm: $n = 2$ ~n = 2~ $;$ ~;~ $m \le 100$ ~m \le 100~
Subtask $3$ ~3~ $-$ ~-~ $500$ ~500~ điểm: $n = 3$ ~n = 3~ $;$ ~;~ $m \le 10^3$ ~m \le 10^3~
Subtask $4$ ~4~ $-$ ~-~ $500$ ~500~ điểm: $n = 5$ ~n = 5~ $;$ ~;~ $m \le 10^5$ ~m \le 10^5~
Subtask $5$ ~5~ $-$ ~-~ $500$ ~500~ điểm: $n \le 50$ ~n \le 50~ $;$ ~;~ $m \le 10$ ~m \le 10~
Subtask $6$ ~6~ $-$ ~-~ $250$ ~250~ điểm: $n \le 50$ ~n \le 50~ $;$ ~;~ $m \le 20$ ~m \le 20~
Subtask $7$ ~7~ $-$ ~-~ $250$ ~250~ điểm: $n \le 50$ ~n \le 50~ $;$ ~;~ $n \times m \le 10^5$ ~n \times m \le 10^5~

Comments