import java.util.Scanner

object Main extends App {
  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)
    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)


}