EmployManager

Shiny wants to hire some managers for her company. There are N candidates, numbered 0 through N-1. She can employ any subset of these candidates, including possibly none or all of them.

For each of the candidates we know an amount in dollars Shiny must pay if she wants to hire that candidate. You are given a int[] value with N elements. For each i, value[i] is the amount in dollars Shiny has to pay if she wants to hire candidate i.

For each pair i < j of candidates we also know a value E(i,j) with the following meaning:

• If both i and j are employed, the company will earn E(i,j) dollars.
• However, if neither i nor j are employed, they will cooperate to harm the company, which will cost the company E(i,j) dollars.

If one of them is employed and the other isn't, nothing happens. All the values E(i,j) are between 0 and 9, inclusive.

For your convenience, we also define E(i,i)=0 and E(j,i)=E(i,j) for all i and j.

You are given the above values E(i,j) encoded as a String[] earning with N elements, each consisting of N characters. For each i and j, earning[i][j] is the character ('0'-'9') that represents the value E(i,j).

You are given the int[] value and the String[] earning. Compute and return the largest total profit (i.e., earnings minus costs) the company can obtain by hiring a suitable subset of candidates.