Maximum Gold Coins Collection

You are given a mansion with n rooms. The mansion is represented as an undirected graph where the connections between rooms are given by an adjacency matrix. Each room has a certain number of gold coins. Two rooms are connected if there is a direct passage between them. A connected group of rooms (i.e., a connected component) allows you to collect coins from all the rooms in that group.

Your task is to determine the maximum total value of gold coins that can be collected from any connected group of rooms. In other words, you need to compute the maximum sum of gold coins from a connected component of the mansion.

Formally, if the mansion has n rooms, let the adjacency matrix be \(A\) with entries \[ A_{ij} = \begin{cases} 1, & \text{if there is a passage between room } i \text{ and } j,\\ 0, & \text{otherwise.} \end{cases} \] and let \(c_i\) denote the coins in room \(i\). You need to calculate: \[ \max_{C \subseteq \{0, 1, \ldots, n-1\} \text{ is connected}} \sum_{i \in C} c_i. \]

inputFormat

The first line contains an integer n — the number of rooms. The following n lines each contain n space-separated integers representing the adjacency matrix. The last line contains n space-separated integers representing the coins available in each room.

outputFormat

Output a single integer — the maximum total coins that can be collected from any connected group of rooms.## sample

4
0 1 0 0
1 0 1 0
0 1 0 0
0 0 0 0
10 20 30 40

60