#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
struct union_find {
vector<int> p, s;
union_find(int N) : p(N, -1), s(N, 1) {}
int repr(int u) {
while( p[u]>=0 ) u=p[u];
return u;
}
bool conn(int u, int v) {
u = repr(u);
v = repr(v);
if( u==v ) return false;
if( s[u] < s[v] ) { p[u]=v; s[v]+=s[u]; }
else { p[v]=u; s[u]+=s[v]; }
return true;
}
};
class BuildersCountry {
public:
long long minCost(vector <int> before, vector <int> after, vector <int> houseCost, vector <string> g, int roadCost)
{
int N = before.size();
LL baseCost = 0;
vector< vector<LL> > cost(N, vector<LL>(N));
for(int i=0; i!=N; ++i)
for(int j=i+1; j!=N; ++j)
{ LL cc = LL(roadCost)*(before[i]+before[j]);
int mi = houseCost[i]<houseCost[j] ? i : j;
int mj = houseCost[i]<houseCost[j] ? j : i;
LL cc2 = LL(houseCost[mj])*(after[mj]-before[mj])*before[mi]
+ LL(houseCost[mi])*(after[mi]-before[mi])*after[mj];
cost[i][j] = cost[j][i] = cc+cc2;
if( g[i][j] == 'Y' )
baseCost += cc2;
}
for(int i=0; i!=N; ++i)
baseCost += LL(houseCost[i]) * LL(before[i]+after[i]-1) * LL(after[i] - before[i]) / 2;
return baseCost + mst(cost, g, N);
}
LL mst(vector<vector<LL> >& c, vector<string>& g, int N)
{
union_find uf(N);
for(int i=0; i!=N; ++i)
for(int j=i+1; j!=N; ++j)
if( g[i][j]=='Y' )
uf.conn(i,j);
typedef pair<LL,pair<int,int> > cedge;
vector<cedge> es;
for(int i=0; i!=N; ++i)
for(int j=i+1; j!=N; ++j)
es.push_back( make_pair( c[i][j], make_pair(i,j) ) );
sort(es.begin(), es.end());
LL cc = 0;
for(int i=0; i!=es.size(); ++i)
{
int u = es[i].second.first;
int v = es[i].second.second;
LL c = es[i].first;
if( uf.conn(u,v) )
cc += c;
}
return cc;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const long long &Expected, const long long &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}
template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
int before_[] = {2, 1, 3, 5};
vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
int after_[] = {2, 1, 3, 5};
vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
int houseCost_[] = {4, 5, 3, 2};
vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
string g_[] = {"NNNN", "NNNN", "NNNN", "NNNN"};
vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
int roadCost = 1000;
long long RetVal = 13000LL;
return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
int Test_(Case_<1>) {
int before_[] = {1, 1, 1, 1};
vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
int after_[] = {1, 3, 1, 2};
vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
int houseCost_[] = {8, 5, 3, 2};
vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
string g_[] = {"NYNN", "YNYN", "NYNY", "NNYN"};
vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
int roadCost = 100000;
long long RetVal = 39LL;
return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
int Test_(Case_<2>) {
int before_[] = {9, 11};
vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
int after_[] = {10, 11};
vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
int houseCost_[] = {5, 1};
vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
string g_[] = {"NN", "NN"};
vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
int roadCost = 15;
long long RetVal = 400LL;
return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
int Test_(Case_<3>) {
int before_[] = {1};
vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
int after_[] = {1000};
vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
int houseCost_[] = {2};
vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
string g_[] = {"N"};
vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
int roadCost = 888;
long long RetVal = 999000LL;
return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
int Test_(Case_<4>) {
int before_[] = {99, 23, 44, 55, 32};
vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
int after_[] = {99, 23, 44, 55, 32};
vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
int houseCost_[] = {39, 32, 11, 23, 89};
vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
string g_[] = {"NYNNN", "YNNNY", "NNNYY", "NNYNY", "NYYYN"};
vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
int roadCost = 54;
long long RetVal = 0LL;
return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<> void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE