Trên con đường dài mười dặm dẫn vào rừng nhà Bạch Chân, người ta trồng một hàng cây hoa đào, đánh số từ $1$ đến $n$. Mỗi cây được treo một dây đèn lồng, ban đêm tỏa sáng lung linh trên nền sương mù.

Trong đêm hội hoa đào, ban tổ chức muốn điều khiển hệ thống đèn bằng một dãy nút bấm bí mật. Có tất cả $m$ nút bấm, đánh số từ $1$ đến $m$. Khi bấm nút thứ $j$, trạng thái đèn (bật $\rightarrow$ tắt, tắt $\rightarrow$ bật) sẽ đổi ở một số cây nhất định dọc theo con đường; danh sách các cây bị ảnh hưởng bởi nút $j$ được cho trước.

Mỗi lần bấm một nút được tính là một thao tác. Một nút có thể được bấm nhiều lần.

Ban đầu, mỗi cây hoa đào đang ở trạng thái bật hoặc tắt nào đó. Ban tổ chức muốn làm cho hệ thống đèn chuyển sang một trạng thái mong muốn, để vẽ nên một “bức tranh ánh sáng” đúng ý họ.

Yêu cầu

Cho biết trạng thái đèn ban đầu của $n$ cây, trạng thái đèn mong muốn, và mô tả $m$ nút bấm (mỗi nút làm đổi trạng thái ở những cây nào), hãy tính số thao tác bấm nút ít nhất để đạt tới trạng thái mong muốn.

Nếu không thể đạt được trạng thái mong muốn bằng bất kỳ cách bấm nút nào, hãy in ra -1.

Dữ liệu

Vào từ thiết bị vào chuẩn:

• Dòng thứ nhất chứa hai số nguyên $n, m$ — số cây hoa đào và số nút bấm.

• Dòng thứ hai là một xâu gồm đúng $n$ ký tự, mỗi ký tự là B hoặc T, thể hiện trạng thái ban đầu của $n$ cây từ cây $1$ đến cây $n$:

  • B nghĩa là đèn Bật,
  • T nghĩa là đèn Tắt.

• Dòng thứ ba là một xâu có dạng hoàn toàn giống dòng thứ hai, thể hiện trạng thái đèn mong muốn.

• Mỗi dòng trong $m$ dòng tiếp theo mô tả một nút bấm:

  • Là một xâu gồm đúng $n$ ký tự 0 hoặc 1.
  • Ở dòng thứ $3 + j$, ký tự thứ $i$ là 1 nếu nút $j$ khi được bấm sẽ làm đổi trạng thái đèn trên cây thứ $i$; là 0 nếu cây thứ $i$ không bị ảnh hưởng bởi nút $j$.

Kết quả

Ghi ra đầu ra chuẩn một số nguyên duy nhất là số thao tác bấm nút ít nhất để đưa hệ thống đèn từ trạng thái ban đầu về trạng thái mong muốn.

Nếu không thể thực hiện được, in ra -1.

Ví dụ mẫu

3 2
BTB
TTT
110
011

2

Giới hạn

Subtask 1 (50% số điểm): $1 \le n \le 10$, $1 \le m \le 10$.

Subtask 2 (50% số điểm): $1 \le n \le 20$, $1 \le m \le 20$.