A169717.星愿配对

$Sherry$ 收集了 $n$ 块星愿石，编号为 $1\sim n$，其中 $n$ 是偶数。

她需要把所有星愿石两两配成若干对。第 $i$ 块星愿石和第 $j$ 块星愿石配成一对时，可以得到 $c_{i,j}$ 点星愿值。

每块星愿石必须且只能出现在一对中。请你求出所有配对方案中，能够得到的最大总星愿值。

第一行输入一个偶数 $n$，表示星愿石数量。

接下来 $n$ 行，每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示 $c_{i,j}$。

保证 $c_{i,i}=0$，且 $c_{i,j}=c_{j,i}$。

输出一个整数，表示最大总星愿值。

样例解释

最优方案是将 $1$ 和 $4$ 配成一对，得到 $4$ 点星愿值；将 $2$ 和 $3$ 配成一对，得到 $6$ 点星愿值。总星愿值为 $10$。

数据范围

$2\le n\le 20$

$0\le c_{i,j}\le 10^9$

保证 $n$ 为偶数。

答案可能较大，请使用 long long。