Maximizing Net Profit by Selecting Managers

As a sharp businessman, Mr. L wishes to hire a subset of the best managers in his country in order to maximize his net profit. There are n managers available. Each manager i has a hiring cost A_i. Also, between any two managers i and j there is a contribution factor E_i,j defined as follows:

• If both manager i and manager j are hired, then manager i contributes E_i,j to the profit.
• If manager i is hired while manager j is not (and is employed by a rival), then manager i suffers a penalty of E_i,j.

Thus, if we let H be the set of managers hired, the net profit is computed as follows:

Your task is to choose a subset H (possibly empty) that maximizes the net profit. Note that it might be optimal to hire no managers at all, yielding a profit of 0.

inputFormat

The input begins with an integer n (the number of managers).

The second line contains n integers: A₁, A₂, \dots, A_n (the hiring cost for each manager).

Then follow n lines, each containing n integers. The j^th number in the i^th line is E_i,j, which represents the contribution factor from manager i to manager j.

outputFormat

Output a single integer which is the maximum net profit achievable by hiring an optimal set of managers.

sample

2
3 2
1 2
3 4

5