星际中有个空间站，任意两个空间站间可以相互跳跃，由空间站跳跃到空间站所需要的代价为,注意不保证，可以任意选择出发的空间站，并通过恰好次跳跃把所有空间站跳完，并且必须选择次跳跃，其中一次跳跃中进行重力加速，另一次跳跃中进行反重力加速，重力加速会导致当前跳跃代价变为，反重力加速会导致当前跳跃代价翻倍(乘)，问跳完所有空间站所需要最小代价

输入描述:

第一行一个数n(3≤n≤16)接下来n行每行n个数，第x行第y个数表示p[x][y](0≤p[x][y]≤100000)

输出描述:

一个数,表示最小代价