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\). 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\).

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:

• \(1 \ a\): 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, 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.

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 \cdot 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 hàng \(i\) và cột \(j\) của ma trận \(M\) là \(1\).

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!

Input

• Dòng đầu tiên chứa hai số nguyên \(n, k\) (\(1 \le n \le 2 \cdot 10^5, 4 \le k \le 20\)).
• Dòng hai chứa bốn số \(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 xâu \(k\) kí tự \(0\) hoặc \(1\) mô tả ma trận \(M\).
• Tiếp theo là \(n\) dòng mô tả các phòng trong lâu đài, mỗi dòng theo một trong hai loại sau:
  • \(1 \ a\): 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.

Output

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

Example

5 5
1 2 3 5
11100
01010
10110
01001
11010
1 2
1 5
2
1 3
1 5

3

Scoring

• Subtask \(1\) (\(15\%\) số điểm): Không có phòng nào là thư viện.
• Subtask \(2\) (\(15\%\) số điểm): Số lượng phòng là thư viện \(\le 3\).
• Subtask \(3\) (\(15\%\) số điểm): \(k = 5\).
• Subtask \(4\) (\(15\%\) số điểm): \(n \le 1000, k \le 10\).
• Subtask \(5\) (\(15\%\) số điểm): \(n \le 1000\).
• Subtask \(6\) (\(15\%\) số điểm): \(k \le 10\).
• Subtask \(7\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.