fun main(args:Array<String>?): Unit {
    val (n, _, d) = readLine()!!.trim().split(' ').map(String::toInt)
    val mod = readLine()!!.trim().split(' ').map(String::toLong)
    val suspects = List(d){
        val r = readLine()!!.trim().split(' ').map(String::toLong)
        mod.zip(r).fold(Pair(1L, 0L) as Pair<Long, Long>?) { pair, (a, r) ->
            if (r != -1L) {
                pair?.let { (product, prev) ->
                    newMod(product, prev, a, r)?.let {
                        newR ->
                        Pair(lcm(product, a), newR)
                    }
                }
            }else pair
        }
    }
    println(
            suspects.fold(n.toLong() as Long?){current, pair ->
                if (current != null && pair != null && current >= pair.second) {
                    (current - pair.second) / pair.first * pair.first + pair.second
                }
                else null
            } ?: -1
    )
}
fun lcm(a: Long, b: Long): Long {
    return a * b / gcd(a, b)
}
tailrec fun gcd(a: Long, b: Long): Long {
    return when(b){
        0L -> a
        else -> gcd(b, a % b)
    }
}
fun newMod(x: Long, mx: Long, y: Long, my: Long): Long? {
    tailrec fun sub(x: Long, y: Long, ax: Long, ay: Long, bx: Long, by: Long): Pair<Long, Long> {
        val a = ax * x + ay * y
        val b = bx * x + by * y
        return when (a % b) {
            0L -> if (bx > 0) Pair(bx, by) else Pair(bx + y, by - x)
            else -> {
                val r = a / b
                sub(x, y, bx, by,ax - r * bx, ay - r * by)
            }
        }
    }
    val g = gcd(x, y)
    return when{
        gcd(g, mx) == gcd(g, my) -> {
            val (ax, ay) = sub(x / g, y / g, 1, 0, 0, 1)
            val nx = ax * my % y
            val ny = ((ay % x + x) % x) * mx % x
            val ux = x / g
            val uy = y / g
            val r = ((nx * ux + ny * uy) % (x * y / g) + (x * y / g)) % (x * y / g)
            r
        }
        else -> null
    }
}
