import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val in = new Scanner(System.in)
    val N = in.nextInt()
    val X = in.nextInt()
    val Y = in.nextInt()
    val foods = (for (_ <- 0 until N) yield {
      val K = in.nextInt()
      (for (_ <- 0 until K) yield {
        val a = in.nextInt()
        val b = in.nextInt()
        val c = in.nextInt()
        (a, b, c)
      }).toArray
    }).toArray

    val dist = (for (_ <- 0 until N) yield (for (_ <- 0 until N) yield in.nextInt()).toArray).toArray
    for {
      k <- 0 until N
      i <- 0 until N
      j <- 0 until N
    } dist(i)(j) = math.min(dist(i)(j), dist(i)(k) + dist(k)(j))

    val cost = Array.fill(1 << (N + 1), N + 1)(Int.MaxValue / 2)
    cost(1)(0) = 0
    for {
      mask <- 0 until (1 << N)
      current <- 0 until N
      next <- 1 until (N + 1)
      if (mask & (1 << current)) != 0
      if (mask & (1 << next)) == 0
    } {
      val nextMask = mask | (1 << next)
      if (nextMask >= cost.length) {
        println(-1)
        return
      }

      cost(nextMask)(next) = math.min(cost(nextMask)(next), cost(mask)(current) + dist(current)(next % N))
    }

    val values = for {
      mask <- 0 until (1 << N)
    } yield {
      val travelCost = cost(mask | (1 << N))(N)
      val budget = math.min(X - travelCost, Y)
      if (budget > 0) {
        val dp = new Array[Int](budget + 1)

        for {
          i <- 0 until N
          if ((1 << i) & mask) != 0
          (price, value, remain) <- foods(i)
          current <- budget to 0 by -1
          num <- 1 to remain
          if current + price * num <= budget
        } {
          dp(current + price * num) = math.max(dp(current + price * num), dp(current) + value * num)
        }
        dp.max
      } else {
        0
      }
    }
    if (values.nonEmpty) println(values.max) else println(0)
  }
}