Chiến đấu

Cuội là một dũng sĩ lành nghề. Trong thế giới mà Cuội sinh sống, có tồn tại $k$ kĩ năng chiến đấu khác nhau được đánh số từ $1$ đến $k$. Ban đầu, Cuội đã thành thạo $4$ kĩ năng khác nhau, đó là $s_1,s_2,s_3$ và $s_4$.

Cuội lên kế hoạch tấn công một lâu đài chứa chấp các tên tội phạm. May mắn thay, Cuội đã có được thông tin về kiến trúc của lâu đài. Lâu đài bao gồm $n$ phòng được đánh số từ $1$ đến $n$. Cuội bắt đầu ở phòng $1$. Nếu Cuội hiện đang ở phòng thứ $x$, thì Cuội chỉ có thể ghé thăm phòng $x+1$, nhưng không thể quay lại phòng $x-1$. Như vậy Cuội đi qua các phòng lần lượt theo thứ tự $1,2,\dots ,n$.

Có $2$ loại phòng là phòng chiến đấu và phòng thư viện. Phòng $x$ có một trong các thông tin sau:

• $1a$: phòng $x$ là phòng chiến đấu. Trong căn phòng này có một tên tội phạm mà Cuội có thể chiến đấu. Tên này làm chủ kĩ năng $a$. Cuội cũng có thể chọn không chiến đấu với tên tội phạm này và ngay lập tức chuyển sang căn phòng tiếp theo.
• $2$: phòng $x$ là một thư viện. Trong căn phòng này, Cuội có thể học cách sử dụng một trong những kĩ năng chiến đấu mới (một kĩ năng mà anh chưa thành thạo), nhưng anh phải quên một kĩ năng mà hiện anh đang làm chủ. Cuội cũng có thể chọn không học gì cả và ngay lập tức chuyển sang phòng tiếp theo. Như vậy tại mỗi thư viện Cuội học được nhiều nhất một kĩ năng, và anh luôn thành thạo đúng $4$ kĩ năng.

Khả năng đánh bại tội phạm của Cuội được thể hiện bằng ma trận $M$. Ma trận $M$ có kích thước là $k\times k$, trong đó mỗi phần tử có thể là $0$ hoặc $1$. Các hàng và cột của $M$ được đánh số từ $1$ đến $k$. Nếu Cuội thành thạo kĩ năng chiến đấu $i$, thì Cuội có thể đánh bại những tên tội phạm làm chủ kĩ năng chiến đấu $j$ nếu và chỉ nếu phần tử ở hàng $i$ và cột $j$ của ma trận $M$ là $1$. Cuội đánh bại được tên tội phạm trong một phòng chiến đấu khi và chỉ khi ít nhất một trong $4$ kĩ năng anh đang thành thạo lúc đó đánh bại được kĩ năng của tên tội phạm.

Trước khi tấn công lâu đài, Cuội xin lời khuyên của bạn để có thể đánh bại càng nhiều tên tội phạm càng tốt. Hãy giúp Cuội đếm số lượng tội phạm tối đa mà anh ta có thể đánh bại!

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n,k$ ($1\le n\le 2·{10}^5$, $4\le k\le 20$).
• Dòng hai chứa bốn số nguyên đôi một khác nhau $s_1,s_2,s_3,s_4$ ($1\le s_1,s_2,s_3,s_4\le k$).
• $k$ dòng tiếp theo, mỗi dòng chứa một xâu gồm $k$ kí tự $0$ hoặc $1$ mô tả ma trận $M$; kí tự thứ $j$ của dòng thứ $i$ là phần tử ở hàng $i$, cột $j$.
• Tiếp theo là $n$ dòng mô tả các phòng trong lâu đài theo thứ tự từ phòng $1$ đến phòng $n$, mỗi dòng theo một trong hai loại sau:
  • $1a$: nếu là phòng chiến đấu ($1\le a\le k$);
  • $2$: nếu là phòng thư viện. Có tối đa $100$ phòng là thư viện.

Dữ liệu ra

Đưa ra số tên tội phạm tối đa bị đánh bại.

Ràng buộc

• $1\le n\le 2·{10}^5$, $4\le k\le 20$.
• $1\le s_1,s_2,s_3,s_4\le k$, đôi một khác nhau.
• $1\le a\le k$ với mọi phòng chiến đấu.
• Có tối đa $100$ phòng là thư viện.

Subtasks

• $15\%$ số test không có phòng nào là thư viện.
• $15\%$ số test có số lượng phòng là thư viện $\le 3$.
• $15\%$ số test có $k=5$.
• $15\%$ số test có $n\le 1000$, $k\le 10$.
• $15\%$ số test có $n\le 1000$.
• $15\%$ số test có $k\le 10$.
• $10\%$ số test còn lại không có ràng buộc gì thêm.

Ví dụ