Problem:


D : Chopsticks / 箸

Problem

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

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

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

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

Input

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

N M D
A1 A2 ... AM
R11 R12 ... R1M
R21 R22 ... R2M
...
RD1 R12 ... RDM

  
N, M, D は、それぞれ記録を開始する直前にあったお箸の本数、余りを求めるのに使う整数の個数、記録をつけた日数である。A1 A2 ... AM は余りを求めるのに使う整数である。

  
2 + d 行目の Rd1, Rd2, ... ,RdM は、d 日目に残っているお箸の本数を A1, A2, ... ,AM のそれぞれで割った余りである。Rdi = -1 のときは、その記録を付け忘れたことを意味する。

Constraints

入力は全て整数である。

1 ≦ N ≦ 1,000,000,000

1 ≦ M ≦ 10

1 ≦ D ≦ 100

2 ≦ Ai ≦ 100

i ≠ j のとき Ai ≠ Aj

0 ≦ Rij < Ai

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 日目は記録し忘れてしまった。


Sample input:
3 3 2
2 3 4
1 0 3
0 2 2


Sample output:
2

Submission status: Accepted

Solution code:
def extgcd(a,b):
    if b == 0:
        x = 1
        y = 0
        return a,x,y
    g,s,t = extgcd(b,a%b)
    x,y = t,s-a//b*t
    return g,x,y

def chineserem(b,m):
    r = 0
    M = 1
    for i in range(len(b)):
        g,p,q = extgcd(M,m[i])
        if (b[i]-r)%g != 0:
            return 0,-1
        tmp = (b[i]-r)//g*p%(m[i]//g)
        r += M*tmp
        M *= m[i]//g
    return r,M
n,m,d = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
r = [[int(x) for x in input().split()] for i in range(d)]
for d in range(d):
    mo = []
    b = []
    for i in range(m):
        if r[d][i] > -1:
            mo.append(a[i])
            b.append(r[d][i])
    x,M = chineserem(b,mo)
    if M < 0:
        print(-1)
        quit()
    i = (n-x)//M
    if i < 0:
        print(-1)
        quit()
    n = M*i+x
print(n)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

def gcd(m, n):
    while n: m, n = n, m % n
    return m

def lcm(m, n):
    return m // gcd(m, n) * n

class congruence(object):
    def __init__(self):
        self.sol = 0
        self.mod = 1
    def append(self, a, q):
        x = self.sol
        p = self.mod
        l = lcm(p, q)
        while x < l:
            if (x % q) == a:
                self.sol = x
                self.mod = l
                return
            x += p
        else:
            raise ValueError('nyan')
    def get(self):
        return (self.sol, self.mod)

def main():
    N, M, D = list(map(int, input().split()))
    A = list(map(int, input().split()))

    for i in range(D):
        R = list(map(int, input().split()))
        crt = congruence()
        for r, a in zip(R, A):
            if r == -1: continue
            crt.append(r, a)

        x, p = crt.get()
        if N < x:
            print(-1)
            return 0

        y = (N-x) // p * p + x
        if not 0 <= y <= N:
            print(-1)
            return 0

        N = y

    print(N)
    return 0

try:
    main()
except ValueError:
    print(-1)