تتناول هذه المسألة لعبة الورق 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