D : Chopsticks / 箸

Problem

お箸は 2 本 1 セット(1 膳)で用いるものである。しかしあるとき一人暮らしの大学生であるいあづ君は箸立てに入っているお箸が奇数本であることに気がついた。これは明らかにおかしい。いつの間にか何本か無くしてしまったのである。 困ったいあづ君は、今後このようなことが無いように箸の本数を毎日記録することにした。

ところが、いあづ君が決めた記録の方法は少し変わっている。 それは、まずM 個の自然数 A₁, ... , A_M を決めた後、 箸の本数をそれらで割った余りを毎日記録するというものである。 例えばある日に残っている箸の本数が T のとき、 その日の記録として T % A₁ , ... , T % A_M を付ける。 ただ、たまにいくつか記録し忘れたり、間違った記録を付けたりすることもあるようだ。 (x % y は x を y で割った余りである。)

ここでいあづ君は大事なことに気づいた。 これだと最終日に何本残っているか 1 つに決まらない！

ポジティブないあづ君は、 D 日分の記録をもとに、 D 日目の記録をつけた直後に残っている箸の本数の最大値を求めるプログラムを書くことにした。

Input

入力は次のような形式で与えられる．

N M D
A₁ A₂ ... A_M
R₁₁ R₁₂ ... R_1M
R₂₁ R₂₂ ... R_2M
...
R_D1 R₁₂ ... R_DM

• N, M, D は、それぞれ記録を開始する直前にあったお箸の本数、余りを求めるのに使う整数の個数、記録をつけた日数である。A₁ A₂ ... A_M は余りを求めるのに使う整数である。
• 2 + d 行目の R_d1, R_d2, ... ,R_dM は、d 日目に残っているお箸の本数を A₁, A₂, ... ,A_M のそれぞれで割った余りである。R_di = -1 のときは、その記録を付け忘れたことを意味する。

Constraints

• 入力は全て整数である。
• 1 ≦ N ≦ 1,000,000,000
• 1 ≦ M ≦ 10
• 1 ≦ D ≦ 100
• 2 ≦ A_i ≦ 100
• i ≠ j のとき A_i ≠ A_j
• 0 ≦ R_ij < A_i
• i 日目に存在する箸の数は、i - 1 日目に存在していた箸の数と同等か、それより少なくなる。

Output

D 日目に残っていると考えられる箸の数の最大値を 1 行で出力せよ。 記録に明らかに間違いがある場合は -1 を出力せよ。

Samples

Sample Input 1

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

Sample Output 1

2

0 日目に 3 本あった箸は、 1 日目に 3 本、 2 日目に 2 本になったと考えられる。

Sample Input 2

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

Sample Output 2

-1

0 日目に 3 本あった箸は、 1 日目に 0 本になったと考えられる。ところが 2 日目の 4 で割った余りが1になっている。

Sample Input 3

3 3 2
2 3 4
1 0 3
-1 -1 -1

Sample Output 3

3

0 日目に 3 本あった箸は、 1 日目も 3 本あったと考えられる。2 日目は記録し忘れてしまった。

---