Architects' Country

Time limit2sMemory limit128 MB

Summary

Connect disjoint cities with new roads and pick an order to build required houses so total payments to participating architects are minimized.

Level: Medium7 of 10
Topics: Minimum spanning tree, Greedy, Graph, Math
Solved: No attempts yet

Problem

There is a country inhabited only by architects. The country has (N) cities numbered from (1) to (N), and some pairs of cities are directly connected by bidirectional roads. Initially, city (i) has (B_i) houses, and each house has one architect living in it.

The country will carry out construction in two stages.

In the first stage, it adds bidirectional roads so that every pair of cities is connected by some path. When one road is built between two cities, every architect living in those two cities must participate, and each participating architect is paid (R).

In the second stage, more houses are built. After this stage, city (i) must have exactly (A_i) houses, so (A_i-B_i) houses must be added in city (i). When one house is built in city (i), every architect in city (i), and every architect in every city directly connected to city (i) by one road, must participate. Each participating architect is paid (C_i). As soon as the new house is completed, one new architect starts living in it. The houses may be built in any order.

Find the minimum possible total cost needed to finish both stages.

Input

The first line contains the number of cities (N).

The second line contains (B_1,B_2,\dots,B_N), separated by spaces.

The third line contains (A_1,A_2,\dots,A_N), separated by spaces.

The fourth line contains (C_1,C_2,\dots,C_N), separated by spaces.

The next (N) lines contain the existing road information. In the (i)-th of these lines, the (j)-th character (G_{i,j}) describes the existing road between city (i) and city (j). Y means that the road exists, and N means that it does not. The diagonal value (G_{i,i}) is not used in the cost calculation.

The last line contains (R).

Output

Print the minimum possible total cost needed to finish both stages.

Constraints

(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)

Examples5

Example 1

Input

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

Expected output

Example 2

Input

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

Expected output

Example 3
Input
```
2
9 11
10 11
5 1
NN
NN
15
```
Expected output
```
400
```
Example 4
Input
```
1
1
1000
2
N
888
```
Expected output
```
999000
```

Example 5

Input

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

Expected output