Robot SMARTBOT là một robot được tham gia huấn luyện trong chương trình "Trải nghiệm thế giới thông minh". Trong hệ thống này có ~k~ kỹ năng công nghệ khác nhau (ví dụ: xử lý ảnh, điều khiển, tối ưu hoá, mô phỏng, học máy...), được đánh số từ ~1~ đến ~k~. Ban đầu, robot đã được cài và sử dụng thành thạo ~4~ kỹ năng khác nhau, đó là ~s_1, s_2, s_3~ và ~s_4~.

Robot chuẩn bị đi qua một chuỗi ~n~ trạm được đánh số từ ~1~ đến ~n~. Hành trình là một chiều: robot chỉ có thể ghé thăm trạm ~x + 1~, nhưng không thể quay lại trạm ~x - 1~. Có hai loại trạm trong hành trình. Một trạm ~x~ có thể là một trong hai loại sau:

• ~1~ ~a~: Trạm ~x~ là trạm thử thách. Ở trạm này có một bài thử thách công nghệ được gắn nhãn kỹ năng yêu cầu là ~a~. Robot có thể: Thực hiện thử thách (nếu kỹ năng hiện có "phù hợp" để xử lý), hoặc bỏ qua ngay và chuyển sang trạm tiếp theo.

• ~2~: Trạm học tập. Ở trạm này robot có thể học thêm ~1~ kỹ năng mới, nhưng bắt buộc phải xóa bỏ ~1~ kỹ năng đang có (do giới hạn bộ nhớ/tài nguyên). Robot cũng có thể chọn không nâng cấp và đi tiếp. Có tối đa ~100~ trạm học tập.

Khả năng robot xử lý các thử thách được mô tả bởi ma trận ~M~ kích thước ~k \times k~, trong đó mỗi phần tử là ~0~ hoặc ~1~. Các hàng và cột của ~M~ đánh số từ ~1~ đến ~k~. Nếu robot đang có kỹ năng ~i~, thì robot có thể xử lý thử thách yêu cầu kỹ năng ~j~ nếu và chỉ nếu khi hàng ~i~ và cột ~j~ của ma trận ~M~ là ~1~.

Trước khi bắt đầu khóa huấn luyện, robot muốn bạn lập trình cho nó để chinh phục được càng nhiều số lượng thử thách càng tốt. Hãy đếm số lượng thử thách tối đa mà robot có thể chinh phục.

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 trạm, mỗi dòng theo một trong hai loại sau:

  • ~1~ ~a~: trạm thử thách ~(1 \le a \le k)~.

  • ~2~: trạm học tập. Có tối đa ~100~ trạm học tập.

Output

Gồm một dòng duy nhất là số lượng thử thách tối đa robot có thể xử lí thành công.

Scoring

Sample Input 1

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

Sample Output 1

3