Description

To improve her IQ, ZJY starts to study linear algebra.

Her friend Boluo gives her the following problem: Given an $n \times n$ matrix $B$ and a $1 \times n$ matrix $C$. Find a $1 \times n$ 0-1 matrix $A$ such that $D = (A \times B - C) \times A^{\sf T}$ is maximized, where $A^{\sf T}$ is the transpose of $A$, and output $D$.

Input Format

The first line contains an integer $n$.
The next $n$ lines give matrix $B$: in the $i$-th line, the $j$-th number is $B_{i,j}$.
The next line contains $n$ integers, representing matrix $C$.
Every number in matrices $B$ and $C$ is a non-negative integer not exceeding $1000$.

Output Format

Output a single integer, the maximum value of $D$.

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

2

Hint

• For $30\%$ of the testdata, $n \leq 15$.
• For $100\%$ of the testdata, $1 \leq n \leq 500$.
• There are also two extra unscored hack testdata in subtask 2, with the same ranges as above.

Translated by ChatGPT 5