Soal ini membahas permainan kartu Braindead, yang diciptakan pada 21 Februari 2019 dan secara longgar didasarkan pada permainan kartu lain yang tidak disebutkan. Namun, cukup mudah menebak permainan tersebut.

Ada kartu dengan $n$ jenis dan $m$ nilai. Beberapa jenis merupakan truf. Bisa ada beberapa jenis truf atau tidak ada sama sekali. Berbeda dari kebanyakan permainan kartu nyata, beberapa kartu dapat memiliki jenis dan nilai yang sama sekaligus.

Ada dua pemain. Masing-masing memiliki sekumpulan kartu yang tidak kosong, disebut kartu di tangan. Kedua pemain mengetahui kartu di tangan satu sama lain. Kartu di tangan seorang pemain disebut kartunya.

Kartu berjenis $s_1$ dengan nilai $r_1$ mengalahkan kartu berjenis $s_2$ dengan nilai $r_2$ jika salah satu kondisi berikut terpenuhi:

1. $s_1 = s_2$ dan $r_1 > r_2$.
2. $s_1$ adalah jenis truf dan $s_2$ bukan jenis truf.

Satu pemain adalah penyerang dan yang lainnya adalah pemain bertahan. Langkah-langkah berikut dilakukan:

1. Penyerang memulai ronde dengan memainkan salah satu kartunya. Ini disebut serangan awal.
2. Pemain bertahan memainkan salah satu kartunya yang mengalahkan kartu terakhir yang dimainkan penyerang. Jika tidak memiliki kartu seperti itu, ia kalah.
3. Penyerang memainkan salah satu kartunya yang nilainya sama dengan nilai suatu kartu yang sebelumnya dimainkan oleh salah satu pemain. Jika tidak memiliki kartu seperti itu, ia kalah.
4. Kembali ke langkah 2.

Seorang pemain tidak boleh memainkan kartu yang sama dua kali.

Berapa banyak serangan awal yang membuat penyerang memenangkan permainan jika kedua pemain bermain optimal sesudah serangan awal? Serangan awal yang memainkan kartu berbeda dengan jenis dan nilai yang sama dianggap berbeda.

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($1 \le n, m \le 18$), masing-masing banyaknya jenis dan nilai.

Baris kedua berisi $n$ bilangan bulat $t_i$ ($0 \le t_i \le 1$). $t_i$ sama dengan $1$ jika jenis ke-$i$ adalah truf, dan $0$ jika merupakan jenis biasa (bukan truf).

Sebanyak $n$ baris berikutnya mendeskripsikan kartu di tangan penyerang. Baris ke-$i$ berisi $m$ bilangan bulat $a_{i,j}$ ($0 \le a_{i,j} \le 10^{12}$). $a_{i,j}$ adalah banyaknya kartu berjenis $i$ dengan nilai $j$ yang dimiliki penyerang.

Sebanyak $n$ baris berikutnya mendeskripsikan kartu di tangan pemain bertahan dengan format yang sama.

Dijamin kartu di tangan kedua pemain tidak kosong.

Keluaran

Cetak satu bilangan bulat — banyaknya serangan awal yang menang.

Contoh

Masukan 1

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

Keluaran 1

0

Masukan 2

3 1
0 1 0
1
0
1
0
1
0

Keluaran 2

2

Masukan 3

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

Keluaran 3

15

Masukan 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

Keluaran 4

97

Masukan 5

1 2
0
4294967296 0
0 2147483647

Keluaran 5

4294967296