Police Stations

Interview

Time limit2sMemory limit128 MB

Summary

Given a directed graph and per-city build costs, find strongly connected components and sum the minimum cost city in each component.

Level: Medium4 of 10
Topics: Graph, DFS, Greedy
Solved: No attempts yet

Problem

There are N cities. Some ordered pairs of cities are connected by one-way roads. President Ukjong wants to build police stations in some cities. Building a police station in city i costs cost[i].

A police station built in city i can control city j only when there is a path from i to j and also a path from j back to i.

Given the road connectivity and the construction cost for each city, compute the minimum total cost needed to control every city.

Input

The first line contains N (1 <= N <= 100). The second line contains cost[1], ..., cost[N], the police-station construction cost for each city. The next N lines describe the road connectivity. In the i-th of these lines, the j-th character is 0 if there is no direct road from city i to city j, and 1 if there is one.

Each cost is an integer between 1 and 1,000,000, inclusive.

Output

Print the minimum total cost required to control every city.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
2
1000000 1000000
01
10
```
Expected output
```
1000000
```
Example 3
Input
```
4
5 3 10 4
0100
0010
0001
1000
```
Expected output
```
3
```