
object Main extends App {

  import scala.io.StdIn._
  import scala.math._


  val Array(n, s) = readLine.trim.split(' ').map(_.toInt)
  val planets = Array.tabulate(n){i ⇒
    val Array(l, r) = readLine.trim.split(' ').map(_.toInt)
    Time(l, r)
  }
  val distance = Array.tabulate(n){_ ⇒ readLine.trim.split(' ').map(_.toLong)}
  for (k ← distance.indices){
    for {i ← distance.indices
         j ← distance.indices if i != j} {
      if (distance(i)(j) > distance(i)(k) + distance(k)(j))
        distance(i)(j) = distance(i)(k) + distance(k)(j)
    }
  }
  for (i ← planets.indices){
    if (planets(i).from < distance(s - 1)(i))
      planets(i) = planets(i).copy(from = distance(s - 1)(i))
  }
  val maxTime = Array.tabulate(n){_ ⇒ 0L}

  for ((p, i) ← planets.zipWithIndex.sortBy(_._1.to)){
    if (p.to >= p.to) {
      if (maxTime(i) < p.to - p.from)
        maxTime(i) = p.to - p.from
      for ((q, j) ← planets.zipWithIndex if i != j) {
        if (q.to + distance(j)(i) <= p.from) {
          if (maxTime(i) < maxTime(j) + p.to - p.from) maxTime(i) = maxTime(j) + p.to - p.from
        } else if (q.to + distance(j)(i) <= p.to) {
          if (maxTime(i) < maxTime(j) + p.to - q.to - distance(j)(i)) maxTime(i) = maxTime(j) + p.to - q.to - distance(j)(i)
        }
      }
    }
  }
  println(
    maxTime.max
  )

  case class Planet(id: Int, time: Time)
  case class Time(from: Long, to: Long)
  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}
