import scala.annotation.tailrec
import scala.collection.mutable

object Main extends App {
  import scala.io.StdIn._

  val n = readInt
  val swapCost = Array.fill(n){readLine.trim.split(' ').map(_.toInt)}
  val permutations = (1 to n).permutations.map{p ⇒ p.foldLeft(0){case (acc, i) ⇒ acc * 10 + i}}.toArray.sorted
  val memo = Array.fill((2 to n).product){Long.MaxValue}
  memo(0) = 0
  val queue = mutable.PriorityQueue((0, 0L))(Ordering.by[(Int, Long), Long](_._2).reverse)
  while (queue.nonEmpty) {
    val (c, cost) = queue.dequeue()
    if (memo(c) == cost) {
      val current = permutations(c)
      for (i ← 0 until n) for (j ← i until n) {
        val swapped = current.swap(i, j)
        val next = permutations.lowerBound(swapped)
        if (memo(next) > cost + swapCost(current(i) - 1)(current(j) - 1)) {
          memo(next) = cost + swapCost(current(i) - 1)(current(j) - 1)
          queue.enqueue((next, memo(next)))
        }
      }
    }
  }
  println(memo.max)
  object DigitsArray {
    val digits = Array.fill(8){1}
    for (i ← digits.indices.tail) digits(i) = 10 * digits(i - 1)
  }
  implicit class DigitsArray(val value: Int) extends AnyVal {
    def apply(digit: Int): Int = value / DigitsArray.digits(digit) % 10
    def swap(i: Int, j: Int): Int = value.replace(i, value(j)).replace(j, value(i))
    def replace(i: Int, d: Int): Int = value - value(i) * DigitsArray.digits(i) + d * DigitsArray.digits(i)
  }
  implicit class SortedArray[T: Ordering](val array: Array[T]) {
    def lowerBound(target: T): Int = {
      var left = 0
      var right = array.length
      while (left < right){
        val mid = (left + right) / 2
        if (implicitly[Ordering[T]].compare(array(mid), target) < 0) left = mid + 1
        else right = mid
      }
      right
    }
  }
}
