Migrated from Lutece 2773 我彻底理解了V圈！-2

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

V 圈小团体中的裟鸾（中国神话中一种凤凰，这里借代精神境界超脱的鸿儒）防盒意识特别强，每个裟鸾最多会和其他三个裟鸾直接联系，但是裟鸾们又想要能够互相传递消息，因此他们可以通过一些裟鸾的帮助来和其他裟鸾进行联系。裟鸾们很懒，因此对于两个裟鸾之间的消息，其余的每个裟鸾最多只愿意帮助一次。裟鸾们不喜欢重复，因此任意两个裟鸾联系的方式只有一种。现在小团体选出了一位最高话事人，话事人的防盒意识更加强大，最多只和其他两个裟鸾直接联系。与最高话事人直接联系的裟鸾为次高话事人，与次高话事人直接联系的非最高话事人为次次高话事人，与次次高话事人直接联系的非次高话事人为次次次高话事人，以此类推。小团体中的每个裟鸾都有一个编号，为了防止混乱，每个话事人都希望自己的一个次话事人以及这个次话事人不通过自己联系到的所有裟鸾的编号都比自己小，另个次话事人以及这个次话事人不通过自己联系到的所有裟鸾的编号都比自己大（两个次话事人的任意一个都可以不存在）。任意两个裟鸾之间联系所花费的米是 (他们联系需要经过的裟鸾的人数+1) * 两人之间的恩怨值。现在作为工具人的你希望帮助裟鸾之间建立联系，使得任意两人取得联系所花费的米的和最小。

注意，裟鸾 $a$ 与裟鸾 $b$ 联系和裟鸾 $b$ 与裟鸾 $a$ 联系视为一种联系，只用花费一次米。

Input

工具人对裟鸾的记录如下 第一行一个整数 $n$，表示小团体中裟鸾的数量 接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 个数记为 $c_{ij}$ 表示编号为 $i$ 的裟鸾与编号为 $j$ 的裟鸾之间的恩怨值

Output

一个整数，表示任意两人取得联系所花费的米的和最小值。

Samples

4
0 566 1 0
566 0 239 30
1 239 0 1
0 30 1 0

839

Constraints

$1\leq n \leq 200$ $0 \leq c_{ij}\leq10^9$ $c_{ii}=0$ $c_{ij}=c_{ji}$

Resources

2022 UESTC ICPC Training for Dynamic Programming