You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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

Mỗi nút bấm $j$ có một chi phí $c_j$, và làm đổi trạng thái (bật $\rightarrow$ tắt, tắt $\rightarrow$ bật) ở 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, và tốn chi phí đúng bằng $c_j$. 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ọ, sao cho tổng chi phí bấm nút là nhỏ nhất.

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, chi phí và mô tả tác động của $m$ nút bấm, hãy tính tổng chi phí nhỏ nhất để đạt tới trạng thái mong muốn.

Dữ liệu

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

• Dòng thứ nhất chứa hai số nguyên dương $n, m$ ($m \le 30$) — 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$ dòng tiếp theo (từ dòng thứ $3+1$ tới dòng thứ $3+m$), dòng thứ $3+j$ mô tả nút bấm thứ $j$, gồm:

  • Một số nguyên dương $c_j$ ($\le 10^7$) — chi phí của nút bấm thứ $j$.
  • Một xâu gồm đúng $n$ ký tự 0 hoặc 1. 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$, ký tự thứ $i$ là 0 nếu cây thứ $i$ không bị ảnh hưởng bởi nút $j$.

Các số và xâu trên một dòng được cách nhau bởi đúng một dấu cách.

Kết quả

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

Dữ liệu đảm bảo luôn tồn tại cách bấm nút để đạt tới trạng thái mong muốn.

Ví dụ mẫu

3 3
BTB
TTT
13 101
5 110
7 011

12

Subtask

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

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