Maximizing the Quadratic Form

You are given an \( n \times n \) matrix \( B \) and a \( 1 \times n \) matrix \( C \). Your task is to choose a \( 1 \times n \) binary (0-1) matrix \( A \) (i.e. each entry of \( A \) is either 0 or 1) in order to maximize the value of the expression

\( D = (A \times B - C) \times A^{\mathsf{T}} \)

Here, \( A^{\mathsf{T}} \) is the transpose of \( A \). In other words, if we denote \( X = A \times B \) (a \( 1 \times n \) matrix), then the expression can be written as \[ D = (X - C) \cdot A^{\mathsf{T}} = \sum_{j=1}^{n} (X_j - C_j)\,A_j. \]

Input: The first line contains an integer \( n \) representing the dimension. The next \( n \) lines each contain \( n \) space-separated integers representing the rows of the matrix \( B \). The last line contains \( n \) space-separated integers representing the matrix \( C \). All numbers are integers.

Output: Output a single integer, which is the maximum value of \( D \) achievable by any choice of the binary matrix \( A \).

inputFormat

The input starts with an integer \( n \) on a single line.

This is followed by \( n \) lines, each containing \( n \) space-separated integers representing the matrix \( B \) (each line is one row of \( B \)).

The final line consists of \( n \) space-separated integers representing the matrix \( C \).

outputFormat

Output a single integer which is the maximum value of \( D = (A \times B - C) \times A^{\mathsf{T}} \) that can be achieved.

sample

2
1 2
3 4
1 1

8