Architects' Country

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.

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

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

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