この問題は、2019 年 2 月 21 日に考案され、別の名前を明かさないカードゲームを緩やかに基にした Braindead というカードゲームについてのものです。とはいえ、何のゲームかを推測するのはかなり簡単です。

カードには $n$ 種類のスートと $m$ 種類のランクがあります。一部のスートは切り札です。切り札のスートは複数ある場合も、まったくない場合もあります。実際の多くのカードゲームとは異なり、同じスートとランクの組を持つカードが複数存在してもかまいません。

プレイヤーは 2 人です。それぞれ空でないカードの集合を持ち、これを手札と呼びます。両者は互いの手札を知っています。あるプレイヤーの手札のカードを、そのプレイヤーのカードと呼びます。

スート $s_1$、ランク $r_1$ のカードは、次のいずれかが成り立つとき、スート $s_2$、ランク $r_2$ のカードに勝ちます。

1. $s_1 = s_2$ かつ $r_1 > r_2$。
2. $s_1$ は切り札であり、$s_2$ は切り札ではない。

一方のプレイヤーが攻撃側、もう一方が防御側です。次の手順で進みます。

1. 攻撃側が自分のカードを 1 枚出してラウンドを開始します。これを最初の攻撃と呼びます。
2. 防御側が、攻撃側が最後に出したカードに勝つ自分のカードを 1 枚出します。そのようなカードがなければ、防御側は敗北します。
3. 攻撃側が、それまでにどちらかのプレイヤーが出したカードのいずれかとランクが等しい自分のカードを 1 枚出します。そのようなカードがなければ、攻撃側は敗北します。
4. 手順 2 に戻ります。

プレイヤーは同じカードを 2 回出すことはできません。

最初の攻撃の後に両者が最適に行動するとき、攻撃側が勝てる最初の攻撃は何通りありますか？スートとランクが同じでも、異なるカードを出す最初の攻撃は異なるものとみなします。

入力

最初の行には、スート数とランク数をそれぞれ表す 2 つの整数 $n$ と $m$（$1 \le n, m \le 18$）が与えられます。

2 行目には $n$ 個の整数 $t_i$（$0 \le t_i \le 1$）が与えられます。$i$ 番目のスートが切り札なら $t_i$ は $1$、通常のスート（切り札ではない）なら $0$ です。

続く $n$ 行は攻撃側の手札を表します。その $i$ 行目には $m$ 個の整数 $a_{i,j}$（$0 \le a_{i,j} \le 10^{12}$）が与えられます。$a_{i,j}$ は、攻撃側が持つスート $i$、ランク $j$ のカードの枚数です。

続く $n$ 行は、同じ形式で防御側の手札を表します。

両者の手札が空でないことが保証されます。

出力

勝てる最初の攻撃の数を表す整数を 1 つ出力してください。

入出力例

入力 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