题目描述

逛街、旅游、看电影，这三样都是周芬老师的最爱。电影院一旦上映新电影，周老师都会在忙完手头的事之后去看电影。她在前往电影院的路上有许多商铺，巧合的是，每当电影院上映新电影时，这些商铺也会随之上架新货物:衣服.零食、书籍等等。这就让周老师犯了难:她难以忍耐她想逛街的心，所经过的商铺她都会进去逛一下。虽然每次看电影她都会提前很久就出门，但她依然可能会因为逛街而错过电影开始。

$ACM$ 团队想要帮助周老师解决这个难题，于是开发了一个专门的程序。在商家上架新货物的时候，他们会在程序里同步显示上架了哪些东西。随后该程序能够通过上架的物品计算出周老师逛街时在每个商铺所花的时间。这样一来，周老师就能在出发前定好她要行走的路线，以便她尽可能地赶上电影开始。

$ACM$ 团队开发的程序还会自动将周老师居住的区域制作成一个$n \times n$的矩阵:周老师住在矩阵左上角 $A_{00}$，电影院在矩阵右下角 $A_{nn}$，表示周老师在在家和到电影院磨蹭的时间，矩阵其他的值 $A_{ij}$表示周老师在那个位置的商家所花费的时间，周老师可以往上、下、左、右四个方向移动。

现在，我们需要根据这个矩阵来找到周老师到达电影院需要花费时间最少的路径。$ACM$ 团队觉得这个算法写起来太简单了，而周芬老师刚好在学校给学生们上算法课，因此 $ACM$ 团队决定把这个算法交给你写，来考考你有没有认真听讲。

输入格式

第一行输入一个数 $n(3 \le n \le 100)$，接下来输入一个 $n$ 行 $n$ 列 的矩阵 $A$，里面的值分别是逛每个商铺所需的时间$A_{11}, A_{12},\dots,A_{nn}(0 \le A_{ij} \le 10^{12})$。

输出格式

一行，输出周芬老师从居住的地方到电影院需要花费的最短时间。