בעיה זו עוסקת במשחק הקלפים 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