题目描述

为了提高智商，ZJY 开始学习线性代数。

她的小伙伴菠萝给她出了这样一个问题：给定一个 $n \times n$ 的矩阵 $B$ 和一个 $1 \times n$ 的矩阵 $C$。求出一个 $1×n$ 的 01 矩阵 $A$，使得 $D=(A×B-C)×A^{\sf T}$ 最大，其中$A^{\sf T}$为$A$的转置，输出$D$。

输入格式

第一行输入一个整数 $n$。接下来 $n$ 行输入 $B$ 矩阵，第 $i$ 行第 $j$ 个数代表 $B$ 接下来一行输入 $n$ 个整数，代表矩阵 $C$。矩阵 $B$ 和矩阵 $C$ 中每个数字都是不过 $1000$ 的非负整数。

输出格式

输出一个整数，表示最大的 $D$。

3
1 2 1
3 1 0
1 2 3
2 3 7

2

提示

• 对于 $30\%$ 的数据，$n \leq 15$；
• 对于 $100\%$ 的数据，$1 \leq n \leq 500$；
• 另外还有两组不计分的 hack 数据，放在 subtask 2 中，数据范围与上面一致。