该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

过年回家最悲伤的事情一定是要洗碗吧。

Description

为了让洗碗不那么悲伤，lyh仔细研究了每个碗，他发现洗碗的顺序对悲伤程度有影响。第i号碗如果是第j个被洗的，那么洗这个碗将获得ai,j的悲伤值。现在给出所有ai,j，求洗完所有的碗，lyh可以获得的最低悲伤值。

Format

Input

第一行一个正整数n，表示碗的数量。 1<=n<=16
接下来n行，每行n个数。第1+i行的第j个数表示ai,j。0<ai,j<=1000

Output

一个整数，表示lyh洗完所有的碗可以获得的最低悲伤值。

Sample 1

Input

3
1 2 3
2 3 1
2 1 3

Output

3

Limitation

1s, 1024KiB for each test case.

Hint

样例解释：第1个洗1号碗，获得1的悲伤值；第2个洗3号碗，获得1的悲伤值；第3个洗2号碗，获得1的悲伤值。
对于60%的测试数据，1<=n<=10。

Source

hpy