import scala.collection.mutable
import scala.io.StdIn._
object Main extends App {
  val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
  val distance = Array.tabulate(n){_ ⇒ readLine.trim.split(' ').map(_.toLong)}
  var left = 1L
  var right = distance.map{_.max}.max
  while(left < right) {
    val mid = (left + right) / 2
    if (pushFlow(makeGraph(distance, mid)) == m) right = mid
    else left = mid + 1
  }
  println(if (m % n == 0) 0 else 1)
  println(right)
  def makeGraph(distance: Array[Array[Long]], maxDistance: Long): Array[List[Edge]] = {
    val smaller = m / n
    val rest = m % n
    val sourceForSmaller = n * 2 + m
    val sourceForRest = sourceForSmaller + 1
    val source = sourceForRest + 1
    val sink = source + 1
    val result = Array.fill(sink + 1){Nil: List[Edge]}
    def setEdge(from: Int, to: Int, flow: Int): Unit = {
      result(from) ::= Edge(to, flow)
      result(to) ::= Edge(from, 0)
      result(from).head.pair = result(to).head
      result(to).head.pair = result(from).head
    }
    for (i ← 0 until n) {
      setEdge(sourceForSmaller, i, smaller)
      setEdge(sourceForRest, i + n, 1)
      for (j ← 0 until m if distance(i)(j) <= maxDistance){
        setEdge(i, 2 * n + j, 1)
        setEdge(i + n, 2 * n + j, 1)
      }
    }
    for (j ← 0 until m) {
      setEdge(2 * n + j, sink, 1)
    }
    setEdge(source, sourceForSmaller, smaller * n)
    setEdge(source, sourceForRest, rest)
    result
  }
  def pushFlow(nodes: Array[List[Edge]]): Int = {
    val source = nodes.length - 2
    val sink = nodes.length - 1
    val depth = Array.fill(nodes.length){-1}
    val searching = Array.tabulate(nodes.length)(nodes)
    def bfs() = {
      depth.indices.foreach(i ⇒ depth(i) = -1)
      searching.indices.foreach(i ⇒ searching(i) = nodes(i))
      val queue = mutable.Queue[Int](source)
      depth(source) = 0
      while(queue.nonEmpty) {
        val current = queue.dequeue()
        if (current != sink) for (Edge(to, flow) ← nodes(current) if flow > 0 && depth(to) == -1) {
          depth(to) = depth(current) + 1
          queue.enqueue(to)
        }
      }
    }
    def dfs(current: Int): Boolean = {
      if (current == sink) true
      else {
        var result = false
        while (!result && searching(current).nonEmpty) {
          searching(current) match {
            case (e@Edge(to, flow))::rest if flow > 0 && depth(to) > depth(current) ⇒
              result = dfs(to)
              if (result) {
                e.flow -= 1
                e.pair.flow += 1
              }else searching(current) = rest
            case _::rest ⇒
              searching(current) = rest
            case _ ⇒
          }
        }
        result
      }
    }
    var count = 0
    var hasFlow = true
    while(hasFlow) {
      hasFlow = false
      bfs()
      while(dfs(source)) {
        count += 1
        hasFlow = true
      }
    }
    count
  }
}
case class Edge(to: Int, var flow: Int) {
  private var mPair = this
  def pair: Edge = mPair
  def pair_=(edge: Edge) = mPair = edge
}
