[TJOI2015]线性代数

题目描述

为了提高智商,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$。

输入输出样例

输入样例 #1

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

输出样例 #1

2

说明

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