import scala.io.Source
import java.io.PrintWriter
import scala.collection.mutable.PriorityQueue
import util.control.Breaks._

/* The solution object. **/
object MatrixPath extends App  {
  // Read the input file
  val lines = Source.fromFile("in.txt").getLines

  val n = lines.next().toInt

  // a matrix of size NxN
  val matrix: Array[Array[Int]] = Array.ofDim[Int](n, n)

  for (x <- 0 until matrix.size) {
    val intArr = lines.next().split(" ")
    for (y <- 0 until intArr.size) {
      matrix(x)(y) = intArr(y).toInt
    }
  }

  class Node (val i: Int, val j: Int, val sum: Int) extends Ordered[Node] {
    def compare(that: Node): Int = that.sum.compare(this.sum)
  }

  val visited: Array[Array[Boolean]] = Array.ofDim(n, n)
  val queue = new PriorityQueue[Node]()

  def visit(i: Int, j: Int, sum: Int) {
    if (i < 0 || i >= n || j < 0 || j >= n || visited(i)(j)) {
      return
    }
    queue.enqueue(new Node( i, j, sum+matrix(i)(j) ))
    visited(i)(j) = true
  }

  def findMinPathSum(): Int = {
    var node: Node = new Node(0, 0, matrix(0)(0))

    queue.enqueue(node)

    breakable {
    while (!queue.isEmpty) {
      node = queue.head
        if (node.i == n - 1 && node.j == n - 1) { break }

        visit(node.i + 1, node.j, node.sum)
        visit(node.i - 1, node.j, node.sum)
        visit(node.i, node.j + 1, node.sum)
        visit(node.i, node.j - 1, node.sum)
        queue.dequeue()
      }
    }
    return node.sum
  }

  val answer = findMinPathSum()
  // Form and write the correct output
  val writer = new PrintWriter("out.txt", "UTF-8")
  try writer.print(answer.toString)
  finally writer.close
}

// EOF