Description

As a business-savvy tycoon, Xiao $L$ decides to hire some of the best managers in his country to run his company. There is a collaboration contribution index among these managers (we use $E_{i,j}$ to denote how well manager $i$ knows manager $j$). That is, when manager $i$ and manager $j$ are both hired, manager $i$ contributes to manager $j$, increasing the profit by $E_{i,j}$.

Of course, hiring each manager costs some money $A_i$. For some managers, their contribution may not be worth the cost, so, being smart, Xiao $L$ will not hire them. However, those who are not hired will be hired by competitors. In that case, they will affect the work of the managers you hire, decreasing the profit by $E_{i,j}$ (note: this $E_{i,j}$ is the same as above).

Being efficiency-first, Xiao $L$ wants to hire some people to maximize the net profit. Can you help Xiao $L$ solve this problem?

Input Format

• The first line contains an integer $N$, the number of managers.
• The second line contains $N$ integers $A_i$, the cost to hire each manager.
• The next $N$ lines each contain $N$ numbers, giving $E_{i,j}$, i.e., how well manager $i$ knows manager $j$. It holds that $E_{i,j} = E_{j,i}$.

Output Format

The first line contains one integer, the maximum value.

3
3 5 100
0 6 1
6 0 2
1 2 0

1

Hint

• For 20% of the testdata, $N \le 10$.
• For 50% of the testdata, $N \le 100$.
• For 100% of the testdata, $N \le 1000$, $E_{i,j} < 2^{31}$, $A_i < 2^{31}$.

From Lin Yankai.

Translated by ChatGPT 5