시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB63350.000%

문제

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

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

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

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

입력

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

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

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

출력

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

제한

  • 1 ≤ N ≤ 50
  • 1 ≤ Bi ≤ Ai ≤ 100,000
  • 1 ≤ Ci ≤ 100,000
  • Gi,i = Y (1 ≤ i ≤ N)
  • Gi,j = Gj,i
  • 1 ≤ R ≤ 100,000

예제 입력 1

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

예제 출력 1

13000

2번 도시와 모든 도시를 연결하는 도로를 만드는 비용은 (1+2)×1000 + (1+3)×1000 + (1+5)×1000 = 13000 이다. 추가로 만들 집은 없다.

예제 입력 2

4
1 1 1 1
1 3 1 2
8 5 3 2
NYNN
YNYN
NYNY
NNYN
100000

예제 출력 2

39

추가로 만들 도로는 없다.

2번 도시에 집을 하나 만들기 위해 건축가에게 지불해야 하는 총 비용은 5×(1+1+1)이다. 이후 2×(1+1)를 지불해서 4번 도시에 집을 하나 만들 수 있다. 마지막으로 2번 도시에 집을 하나 만들면 된다. 이때, 2번 도시에는 건축가가 총 2명 살고 있기 때문에, 지불해야 하는 총 비용은 5×(1+2+1)이다.

건축가에게 지불한 총 비용은 15+4+20 = 39이다.

예제 입력 3

2
9 11
10 11
5 1
NN
NN
15

예제 출력 3

400

도로 하나, 집 하나를 만들면 된다.

예제 입력 4

1
1
1000
2
N
888

예제 출력 4

999000

집 999개를 만들어야 한다. 총 비용은 (1 + 2 + ... + 999) × 2 = 999000 이다.

예제 입력 5

5
99 23 44 55 32
99 23 44 55 32
39 32 11 23 89
NYNNN
YNNNY
NNNYY
NNYNY
NYYYN
54

예제 출력 5

0

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013