To improve her IQ, ZJY has started studying linear algebra. Her friend Pineapple gave her the following problem: Given an $n \times n$ matrix $B$ and a $1 \times n$ matrix $C$, find a $1 \times n$ binary matrix $A$ (consisting of 0s and 1s) such that $D = (A \times B - C) \times A^T$ is maximized, where $A^T$ is the transpose of $A$. Output $D$.

Input

The first line contains an integer $n$. The next $n$ lines contain the matrix $B$, where the $j$-th number in the $i$-th line represents $B_{ij}$. The following line contains $n$ integers representing the matrix $C$. Each number in matrix $B$ and matrix $C$ is a non-negative integer not exceeding $1000$.

Output

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

Constraints

• For 30% of the data, $1 \le n \le 15$.
• For 100% of the data, $1 \le n \le 500$.

Examples

Input 1

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

Output 1

2