종욱이가 살고있는 나라에는 도시가 N개 있고, 도시의 일부는 일방 통행 도로로 연결되어 있다. 종욱이가 살고있는 나라의 대통령 욱종이는 범죄와 싸우기 위해서 일부 도시에 경찰서를 세우려고 한다. 도시 i에 경찰서를 세우는 비용은 cost[i] 이다.</p>

도시 i에 세운 경찰서가 도시 j를 통제할 수 있으려면, i에서 j로 갔다가, 다시 돌아오는 경로가 존재해야 한다.

도로가 연결되어 있는 상태와 각 도시에 경찰서를 지을 때 필요한 비용이 주어졌을 때, 모든 도시를 통제하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 각 도시에 경찰서를 세우는데 드는 비용이 주어진다. 셋째 줄부터 도로가 연결되어 있는 상태가 한 줄에 한 줄에 하나씩 주어진다. i번째 줄의 j번째 문자가 0인 경우에는 도시 i에서 도시 j로 갈 수 없는 것이고, 1인 경우에는 갈 수 있는 것이다.</p>

경찰서를 세우는 비용은 1,000,000보다 작거나 같은 자연수이다.

출력 형식

첫째 줄에 모든 도시를 통제하는데 필요한 최소 비용을 출력한다.

예제 입력 1

5
1 2 3 4 5
00011
10000
00010
00100
01000

예제 출력 1

4

예제 입력 2

2
1000000 1000000
01
10

예제 출력 2

1000000

예제 입력 3

4
5 3 10 4
0100
0010
0001
1000

예제 출력 3

3