Bài toán này nói về trò chơi bài Braindead, được phát minh ngày 21 tháng 2 năm 2019 và dựa phần nào trên một trò chơi bài khác không được nêu tên. Tuy vậy, cũng khá dễ đoán đó là trò nào.

Có các lá bài thuộc $n$ chất và $m$ hạng. Một số chất là chất chủ. Có thể có nhiều chất chủ hoặc không có chất chủ nào. Khác với phần lớn trò chơi bài thực tế, nhiều lá bài có thể đồng thời có cùng chất và cùng hạng.

Có hai người chơi. Mỗi người có một tập hợp lá bài không rỗng, gọi là bài trên tay. Hai người đều biết bài trên tay của nhau. Các lá bài trên tay một người được gọi là bài của người đó.

Lá bài chất $s_1$, hạng $r_1$ thắng lá bài chất $s_2$, hạng $r_2$ nếu một trong các điều kiện sau đúng:

1. $s_1 = s_2$ và $r_1 > r_2$.
2. $s_1$ là chất chủ còn $s_2$ không phải chất chủ.

Một người là người tấn công, người còn lại là người phòng thủ. Các bước sau diễn ra:

1. Người tấn công bắt đầu vòng chơi bằng cách đánh một lá bài của mình. Đây được gọi là đòn tấn công mở đầu.
2. Người phòng thủ đánh một lá bài của mình thắng lá bài người tấn công vừa đánh gần nhất. Nếu không có lá bài như vậy, người phòng thủ thua.
3. Người tấn công đánh một lá bài của mình có hạng bằng hạng của một lá bài đã được một trong hai người đánh trước đó. Nếu không có lá bài như vậy, người tấn công thua.
4. Quay lại bước 2.

Một người chơi không được đánh cùng một lá bài hai lần.

Có bao nhiêu đòn tấn công mở đầu để người tấn công thắng, giả sử sau đòn tấn công mở đầu cả hai người đều chơi tối ưu? Những đòn tấn công mở đầu đánh các lá bài khác nhau nhưng cùng chất và hạng vẫn được coi là khác nhau.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ ($1 \le n, m \le 18$), lần lượt là số chất và số hạng.

Dòng thứ hai chứa $n$ số nguyên $t_i$ ($0 \le t_i \le 1$). $t_i$ bằng $1$ nếu chất thứ $i$ là chất chủ và bằng $0$ nếu là chất thường (không phải chất chủ).

Tiếp theo là $n$ dòng mô tả bài trên tay của người tấn công. Dòng thứ $i$ chứa $m$ số nguyên $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$). $a_{i,j}$ là số lá bài chất $i$, hạng $j$ mà người tấn công có.

Tiếp theo là $n$ dòng mô tả bài trên tay của người phòng thủ theo cùng định dạng.

Bảo đảm bài trên tay của cả hai người đều không rỗng.

Dữ liệu ra

In ra một số nguyên — số đòn tấn công mở đầu dẫn đến chiến thắng.

Ví dụ

Dữ liệu vào 1

3 2
0 0 1
1 1
1 0
1 0
0 1
0 1
1 1

Dữ liệu ra 1

0

Dữ liệu vào 2

3 1
0 1 0
1
0
1
0
1
0

Dữ liệu ra 2

2

Dữ liệu vào 3

2 4
1 1
5 5 5 0
0 0 0 0
5 5 5 0
0 0 0 10

Dữ liệu ra 3

15

Dữ liệu vào 4

4 13
1 0 1 0
3 2 0 2 0 3 0 0 3 5 2 1 5
3 3 2 2 2 1 0 4 5 1 5 3 3
1 4 4 2 0 3 2 5 2 5 0 5 3
3 5 4 2 3 3 4 2 2 4 3 2 3
4 3 4 9 0 4 0 1 4 0 1 2 5
1 8 8 6 5 1 1 7 2 4 1 3 9
3 7 3 1 8 9 2 0 0 1 9 6 6
4 6 6 7 9 5 3 2 9 5 0 7 8

Dữ liệu ra 4

97

Dữ liệu vào 5

1 2
0
4294967296 0
0 2147483647

Dữ liệu ra 5

4294967296