1349번 - 건축가의 나라

건축가만 사는 나라가 있다. 이 나라에는 N개의 도시가 있고 1부터 N까지 번호가 매겨져 있다. 일부 도시는 양방향 도로로 연결되어 있다. i번 도시에는 집이 B_i개 있다. 각 집에는 건축가 1명이 살고 있다.

이 나라는 두 단계의 건설 작업을 하려고 한다. 첫 번째 단계는 모든 도시의 쌍이 경로로 연결되어 있게 양방향 도로를 건설하는 것이다. 두 도시 사이에 도로를 건설할 때는 두 도시에 사는 모든 건축가가 참여해야 한며, 각 건축가에게 지불해야 하는 비용은 R이다.

두 번째 단계는 집을 집을 추가로 만드는 단계이다. 이 단계가 끝난 후 i번 도시에는 집이 A_i개 있어야 한다. 즉, B_i - A_i개의 집을 추가로 만들어야 한다. 도시 i에 집을 하나 지을 때는 도시 i에 있는 모든 건축가와 도시 i와 도로로 하나로 연결된 모든 도시에 있는 모든 건축가가 이 과정에 참여해야 한다. 이 때 각 건축가에게 지불해야 하는 비용은 C_i이다. 새로운 집이 완성되면 그 즉시 새로운 건축가 1명이 그 집에서 살게 된다. 집은 아무 순서로 만들어도 된다.

두 단계를 모두 마치는데 필요한 비용(각 건축가에게 지불해야 하는 비용의 합)의 최솟값을 구해보자.

첫째 줄에 도시의 개수 N이 주어진다. 둘째 줄에는 B_i, 셋째 줄에는 A_i, 넷째 줄에는 C_i가 가 공백으로 구분되어 주어진다.

넷째 줄부터 N개의 줄에는 도로의 정보가 주어진다. i번째 줄의 j번째 문자 G_i,j는 i번 도시와 j번 도시 사이의 도로를 의미하며, Y이면 도로가 있는 것, N은 도로가 없는 것이다.

마지막 줄에는 R이 주어진다.

두 단계를 모두 마치는데 필요한 비용의 최솟값을 출력한다.

• 1 ≤ N ≤ 50
• 1 ≤ B_i ≤ A_i ≤ 100,000
• 1 ≤ C_i ≤ 100,000
• G_i,i = Y (1 ≤ i ≤ N)
• G_i,j = G_j,i
• 1 ≤ R ≤ 100,000