시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4 2 2 50.000%

문제

머나먼 곳에 건축가들만 사는 나라가 있다. 그들은 이미 몇 개의 도시를 만들었다. 그리고 그 도시중 몇 개는 양방향 도로로 연결되 있다. 또 모든 도시는 몇 개의 집이 있다. 모든 집에는 한 명의 건축가만 살 수 있다.

이 나라는 두 개의 건설 작업을 하려고 한다.

첫 번째 작업은 새로운 양방향 도로를 짓는 것인데, 이 때 모든 도시는 다른 도시로 가는 경로가 모두 있어야 한다. 두 도시 사이에 도로를 지을 때는 두 도시에 사는 모든 건축가들이 참여한다. 그리고, 각각의 건축가는 R이란 돈을 내야 한다.

두 번째 작업은 새로운 집을 짓는 것이다. 이 때 이 작업이 끝난 후에 각 도시에 있어야 하는 집의 개수가 주어진다. 이때는 그 도시의 건축가와 이웃한 도시의 모든 건축가가 참여한다. 그리고, 모든 건축가는 H[i] (i번도시에 집을 짓는데 드는 비용)을 내야 한다. 두 도시가 도로로 직접 연결되어 있을 때 이웃이라고 한다. 집을 짓게되면 그 즉시 새로운 건축가가 살게 된다.

두 작업을 마치는데 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N이 주어진다. 둘째 줄에는 현재 각 도시에 있는 집의 개수가 1번 도시부터 차례대로 주어진다. 셋째 줄에는 두 번째 작업이 끝난 후 각 도시에 있어야 하는 집의 개수가 1번 도시부터 차례대로 주어진다. 넷째 줄에는 각 도시에 집을 짓는데 드는 비용이 1번 도시부터 주어진다. 넷째 줄부터 N개의 줄에는 도로가 주어진다. 도로는 인접행렬과 같은 형태로 주어지고, Y는 도로가 있는 것, N은 도로가 없는 것이다. 마지막 줄에는 도로를 짓는데 드는 비용 R이 주어진다. N은 50보다 작거나 같은 자연수이고, 그 이외의 모든 숫자는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 두 작업을 마치는데 드는 비용의 최솟값을 출력한다.

예제 입력

4
2 1 3 5
2 1 3 5
4 5 3 2
NNNN
NNNN
NNNN
NNNN
1000

예제 출력

13000

힌트

출처