โจทย์นี้เกี่ยวกับเกมไพ่ Braindead ซึ่งคิดค้นขึ้นเมื่อวันที่ 21 กุมภาพันธ์ 2019 และอ้างอิงอย่างหลวม ๆ จากเกมไพ่อื่นที่ไม่ได้ระบุชื่อ แต่ก็เดาได้ไม่ยากว่าเป็นเกมอะไร

มีไพ่ $n$ ดอกและ $m$ ระดับ บางดอกเป็นดอกทรัมป์ อาจมีดอกทรัมป์หลายดอกหรือไม่มีเลยก็ได้ ต่างจากเกมไพ่จริงส่วนใหญ่ ไพ่หลายใบอาจมีทั้งดอกและระดับเหมือนกันได้

มีผู้เล่นสองคน แต่ละคนมีชุดไพ่ที่ไม่ว่าง เรียกว่าไพ่ในมือ ผู้เล่นทั้งสองรู้ไพ่ในมือของกันและกัน ไพ่ในมือของผู้เล่นคนหนึ่งเรียกว่าไพ่ของเขา

ไพ่ดอก $s_1$ ระดับ $r_1$ ชนะไพ่ดอก $s_2$ ระดับ $r_2$ หากเงื่อนไขใดเงื่อนไขหนึ่งต่อไปนี้เป็นจริง:

1. $s_1 = s_2$ และ $r_1 > r_2$
2. $s_1$ เป็นดอกทรัมป์ และ $s_2$ ไม่ใช่ดอกทรัมป์

ผู้เล่นคนหนึ่งเป็นผู้โจมตี อีกคนเป็นผู้ป้องกัน ดำเนินการตามขั้นตอนต่อไปนี้:

1. ผู้โจมตีเริ่มรอบโดยเล่นไพ่ของตนหนึ่งใบ เรียกว่าการโจมตีเริ่มต้น
2. ผู้ป้องกันเล่นไพ่ของตนหนึ่งใบที่ชนะไพ่ใบล่าสุดที่ผู้โจมตีเล่น หากไม่มีไพ่ดังกล่าว ผู้ป้องกันจะแพ้เกม
3. ผู้โจมตีเล่นไพ่ของตนหนึ่งใบที่มีระดับเท่ากับระดับของไพ่บางใบที่ผู้เล่นคนใดคนหนึ่งเคยเล่นไปแล้ว หากไม่มีไพ่ดังกล่าว ผู้โจมตีจะแพ้เกม
4. กลับไปขั้นตอนที่ 2

ผู้เล่นไม่สามารถเล่นไพ่ใบเดิมสองครั้งได้

มีการโจมตีเริ่มต้นกี่แบบที่ทำให้ผู้โจมตีชนะเกม โดยสมมติว่าหลังจากการโจมตีเริ่มต้น ผู้เล่นทั้งสองเล่นอย่างเหมาะสมที่สุด? การโจมตีเริ่มต้นที่ใช้ไพ่คนละใบ แม้มีดอกและระดับเดียวกัน ถือว่าต่างกัน

ข้อมูลนำเข้า

บรรทัดแรกมีจำนวนเต็มสองจำนวน $n$ และ $m$ ($1 \le n, m \le 18$) ซึ่งเป็นจำนวนดอกและจำนวนระดับตามลำดับ

บรรทัดที่สองมีจำนวนเต็ม $n$ จำนวน $t_i$ ($0 \le t_i \le 1$) โดย $t_i$ เท่ากับ $1$ หากดอกที่ $i$ เป็นทรัมป์ และเท่ากับ $0$ หากเป็นดอกปกติ (ไม่ใช่ทรัมป์)

อีก $n$ บรรทัดถัดมาอธิบายไพ่ในมือผู้โจมตี บรรทัดที่ $i$ มีจำนวนเต็ม $m$ จำนวน $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$) โดย $a_{i,j}$ คือจำนวนไพ่ดอก $i$ ระดับ $j$ ที่ผู้โจมตีมี

อีก $n$ บรรทัดถัดมาอธิบายไพ่ในมือผู้ป้องกันด้วยรูปแบบเดียวกัน

รับประกันว่าไพ่ในมือของผู้เล่นทั้งสองไม่ว่าง

ข้อมูลส่งออก

พิมพ์จำนวนเต็มหนึ่งจำนวน คือจำนวนการโจมตีเริ่มต้นที่ทำให้ชนะ

ตัวอย่าง

ข้อมูลนำเข้า 1

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

ข้อมูลส่งออก 1

0

ข้อมูลนำเข้า 2

3 1
0 1 0
1
0
1
0
1
0

ข้อมูลส่งออก 2

2

ข้อมูลนำเข้า 3

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

ข้อมูลส่งออก 3

15

ข้อมูลนำเข้า 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

ข้อมูลส่งออก 4

97

ข้อมูลนำเข้า 5

1 2
0
4294967296 0
0 2147483647

ข้อมูลส่งออก 5

4294967296