题目描述

ABC来到了一个很大的动物园，他在左上角，这个动物园有许多稀有的动物，他希望看到所有的动物并回到出口（右下角），但ABC的现在很累，想知道看到所有种类动物的最短路径

输入格式

第一行n，n不大于20，表示地图的行列 第二行表示动物园的地图，0表示路，>0的数表示不同种类动物，注意：可能有重复的数字

输出格式

能看到所有种类的动物并且回到右下角的最短步数，如果不能看到所有动物输出-1（ABC站在的地方也算1步）

输入输出样例

输入

4

0 0 1 0

0 2 3 4

0 0 0 1

0 2 1 3

输出

7