#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <limits>
#include <memory.h>
#include <iterator>

using namespace std;

class MagicMolecule
{
public:
    int n;
    vector<int> p;
    vector<long long> neigh;

    int get(long long clique, long long cand, long long out, int size = 0, int cost = 0)
    {
        if (3 * (__builtin_popcount(cand & 0xFFFFFFFFU) + __builtin_popcount(cand >> 32) + size) < 2 * n) {
            return 0;
        }

        int result = 0;
        long long candintersect = (1LL << n) - 1;
        for (int i = 0; i < n; ++i) if (cand & (1LL << i)) candintersect &= neigh[i];
        if (out & candintersect) return result;

        for (int i = 0; i < n; ++i) if (cand & (1LL << i)) {
            long long mask = 1LL << i;
            long long ncand = cand & neigh[i], nout = out & neigh[i];
            if (ncand == 0 && nout == 0) {
                if (3 * (size + 1) >= 2 * n) result = max(result, cost + p[i]);
            } else {
                result = max(result, get(clique | mask, ncand, nout, size + 1, cost + p[i]));
            }
            cand = cand & ~mask;
            if (!cand) return result;
            out = out | mask;
        }
        return result;
    }

    int maxMagicPower(vector <int> magicPower, vector <string> magicBond)
    {
        n = (int) magicPower.size();
        int mindeg = (n * 2 - 1) / 3;
        p = magicPower;

        vector<int> deg(n);
        neigh.assign(n, 0); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (magicBond[i][j] == 'Y') neigh[i] += 1LL << j, ++deg[i];
        long long cand = 0;
        for (int i = 0; i < n; ++i) if (deg[i] >= mindeg) cand += 1LL << i;
        int result = get(0LL, cand, 0);
        return result ? result : -1;
    }
};