건축가의 나라
시간 제한2초메모리 제한128 MB
떨어진 도시들을 도로로 연결하고 필요한 집을 짓는 순서를 정해, 참여하는 건축가에게 지급하는 총 비용을 최소화하는 문제입니다.
문제
건축가들만 사는 나라가 있다. 이 나라에는 (1)번부터 (N)번까지 번호가 붙은 도시 (N)개가 있고, 일부 도시 쌍은 양방향 도로로 직접 연결되어 있다. 처음에 (i)번 도시에는 집이 (B_i)개 있으며, 각 집에는 건축가 한 명이 산다.
이 나라는 두 단계의 건설을 진행하려고 한다.
첫 번째 단계에서는 어느 두 도시를 골라도 도로들을 따라 서로 오갈 수 있도록 양방향 도로를 추가로 건설한다. 두 도시 사이에 도로 하나를 새로 지을 때는 그 두 도시에 사는 모든 건축가가 참여해야 하며, 참여한 건축가 한 명에게 비용 (R)을 지불한다.
두 번째 단계에서는 집을 추가로 짓는다. 이 단계가 끝난 뒤 (i)번 도시에는 집이 정확히 (A_i)개 있어야 하므로, (i)번 도시에는 집을 (A_i-B_i)개 더 지어야 한다. (i)번 도시에 집 하나를 지을 때는 (i)번 도시에 있는 모든 건축가와, (i)번 도시와 도로 하나로 직접 연결된 모든 도시에 있는 모든 건축가가 참여한다. 이때 참여한 건축가 한 명에게 비용 (C_i)를 지불한다. 새 집이 완성되면 즉시 새로운 건축가 한 명이 그 집에 살기 시작한다. 집들은 어떤 순서로 지어도 된다.
두 단계를 모두 마치는 데 필요한 총비용의 최솟값을 구하라.
입력
첫째 줄에 도시의 수 (N)이 주어진다.
둘째 줄에 (B_1,B_2,\dots,B_N)이 공백으로 구분되어 주어진다.
셋째 줄에 (A_1,A_2,\dots,A_N)이 공백으로 구분되어 주어진다.
넷째 줄에 (C_1,C_2,\dots,C_N)이 공백으로 구분되어 주어진다.
다음 (N)개의 줄에는 기존 도로 정보가 주어진다. 그중 (i)번째 줄의 (j)번째 문자 (G_{i,j})는 (i)번 도시와 (j)번 도시 사이의 기존 도로를 나타낸다. 문자가 Y이면 도로가 있고, N이면 도로가 없다. 대각 원소 (G_{i,i})는 비용 계산에 사용하지 않는다.
마지막 줄에 (R)이 주어진다.
출력
두 단계를 모두 마치는 데 필요한 총비용의 최솟값을 출력한다.
제한
- (1 \le N \le 50)
- (1 \le B_i \le A_i \le 100{,}000)
- (1 \le C_i \le 100{,}000)
- (G_{i,j}=G_{j,i})
- (1 \le R \le 100{,}000)