50061. Donation

I'm a slow walker, but I never walk backwards.

Task Description

Write a program to determine the maximum amount of donation you can raise from a set of people.

We are given N people who are willing to make a donation, and the amounts of money they will donate. However, each one of them may hate some of the others, so he/she will not attend if the persons he/she hates also appear. Now write a program to determine the maximum amount of donation you can raise.

Let us illustrate the task with an example. If we are given four people, Tim, Jason, Kate, Amy. The donations they will make are 900, 500, 1200, and 700 respectively. Tim hates Jason and Kate, and Amy hates Jason and Kate. If we select Tim and Amy, then we can raise 1600, and if we select Jason and Kate, we can raise 1700. Therefore, the maximum amount of donation is 1700.

Input Format

There is only one test case. The first line contains an integer $N$ indicating the number of people.
The following $N$ lines are the donations of those people, the $i_{th}$ line contains an integers $D$, indicating the donation of $i_{th}$ person.
Then, there is a $N$ by $N$ matrix $M$ representing the relationship of $i_{th}$ person and $j_{th}$ person. $M_{ij}$ is 1, if $i_{th}$ person hates $j_{th}$ person. It's 0, otherwise. It is guaranteed that this matrix will always be symmetric.

  • $ 0 \lt N \lt 64.$
  • $ 0 \lt D \lt 10000.$

Output Format

There is one line in the output. The line contains an integer indicating the maximum amount of donation.
0 < The maximum amount of donation < 2147483647.

Sample Input

4
900
500
1200
700
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

Sample Output

1700

Discussion