/*
written by- Piyush Golani
language- c++
country- India
College- N.I.T Jamshedpur
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<cctype>
using namespace std;
#define pb push_back
#define all(s) s.begin(),s.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=b;i--)
#define PI 3.1415926535897932384626433832795
#define INF 2000000000
#define BIG_INF 7000000000000000000LL
#define mp make_pair
#define eps 1e-9
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007
#define mm 10000000

typedef long long LL;


string inttostring(int n)
{
    stringstream a;
    a<<n;
    return a.str();
}

int stringtoint(string A)
{
    istringstream a(A);
    int p;
    a>>p;
    return p;
}

//////////////////////////////////////////////////////


class MagicMoleculeEasy {
public:
    vector<int> mp;
    int a[1225],b[1225];
    int e;
    int n,best;
    bool used[1225];
    int rec(int p,int k)
    {
        if(p==e)
        {
            int res=0;
            vector<int> x;
            f(i,0,n)
            {
                if(used[i])
                {
                    res+=mp[i];
                }
                else
                {
                    x.pb(mp[i]);
                }
            }
            sort(all(x),greater<int>() );
            f(i,0,k) res+=x[i];
            best=max(best,res);
            return 0;
        }
        else
        {
            if(used[a[p]] || used[b[p]])
            {
                rec(p+1,k);
            }
            else if(k>0)
            {
                used[a[p]]=true;
                rec(p+1,k-1);
                used[a[p]]=false;
                used[b[p]]=true;
                rec(p+1,k-1);
                used[b[p]]=false;
            }
            return 0;
        }
    }
   int maxMagicPower( vector <int> magicPower, vector <string> magicBond, int k ) {
    this->mp=magicPower;
    n=magicPower.size();
    e=0;
    f(i,0,n)
    {
        f(j,0,n)
        {
            if(magicBond[i][j]=='Y')
            {
                a[e]=i;
                b[e++]=j;
            }
        }
    }
    fill(used,used+n,false);
    best=-1;
    rec(0,k);
    return best;
   }
};

// BEGIN CUT HERE
namespace moj_harness {
    int run_test_case(int);
	void run_test(int casenum = -1, bool quiet = false) {
		if (casenum != -1) {
			if (run_test_case(casenum) == -1 && !quiet) {
				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
			}
			return;
		}

		int correct = 0, total = 0;
		for (int i=0;; ++i) {
			int x = run_test_case(i);
			if (x == -1) {
				if (i >= 100) break;
				continue;
			}
			correct += x;
			++total;
		}

		if (total == 0) {
			cerr << "No test cases run." << endl;
		} else if (correct < total) {
			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
		} else {
			cerr << "All " << total << " tests passed!" << endl;
		}
	}

	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) {
		cerr << "Example " << casenum << "... ";

		string verdict;
		vector<string> info;
		char buf[100];

		if (elapsed > CLOCKS_PER_SEC / 200) {
			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
			info.push_back(buf);
		}

		if (expected == received) {
			verdict = "PASSED";
		} else {
			verdict = "FAILED";
		}

		cerr << verdict;
		if (!info.empty()) {
			cerr << " (";
			for (int i=0; i<(int)info.size(); ++i) {
				if (i > 0) cerr << ", ";
				cerr << info[i];
			}
			cerr << ")";
		}
		cerr << endl;

		if (verdict == "FAILED") {
			cerr << "    Expected: " << expected << endl;
			cerr << "    Received: " << received << endl;
		}

		return verdict == "PASSED";
	}

	int run_test_case(int casenum__) {
		switch (casenum__) {
		case 0: {
			int magicPower[]          = {1, 2};
			string magicBond[]        = {"NY",
 "YN"};
			int k                     = 1;
			int expected__            = 2;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 1: {
			int magicPower[]          = {100, 1, 100};
			string magicBond[]        = {"NYN",
 "YNY",
 "NYN"};
			int k                     = 1;
			int expected__            = 1;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 2: {
			int magicPower[]          = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

			string magicBond[]        = {"NYYYYYYYYYYYYYYYYYYYYNYYNYYYYYYYYYYYYYYYYY", "YNYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYY", "YYNYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYY", "YYYNYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYN", "YYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYNYYYYNYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYY", "YYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYNYYYYYYYYYYNYYYYYYYYYYYYNYYYYYYYYYY", "YYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYNYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYY", "YYYYYNYYYYNYYNYYYYYYYYYYYYYYYYYYYNYYYYYYYY", "YYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYNYYYNYYYYYYYYYYYYNYYNYYYYYYYYY", "YYYNYYYYYYNYYNYYYYYYYYYYYYYYYYYYYYYYYYYYNY", "YYYYYYYYYYYYYYNYYYYYYYYYYYYYYYNYYYYYYYYYYY", "YYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYNYYYNYYYYYYYYYNNYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYNYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYNYYYYYYYYNNYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYY", "NYYYYNYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYNYYYYYNY", "YYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYY", "NYNYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYNYYYYYYYYYNYYYYYYYYYYYYYYY", "YYYYYYYYYYYYYYYYNYYYYYYYYYYNYYYYYYYYYYYYYY", "YNYYYYYYYNYYYYYYYYYNYYYYYYYYNYYYYYYYYYYNYY", "YYYYYYYYYYYYNYYYYYYNYYYYYYYYYNYYYYNYYYYYYY", "YYYYYYYYYYYYYYNYYYYYYYYYYYYYYYNYYYYYYYYYYY", "YYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYY", "YYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYNYYYYYYYNY", "YYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYNYYYYYNYY", "YYYYYYYYYYYYYYYYYYYYYYNYYYYYYNYYYYNYYYNYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYNYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNNYYNYYY", "YYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYNYYYYYNNY", "YYYYYYYYYYYYYNYYYYYYYYNYYYYYYYYYNYYYYYYNNY", "YYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYN"};
			int k                     = 13;
			int expected__            = -1;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 3: {
			int magicPower[]          = {4, 7, 5, 8};
			string magicBond[]        = {"NYNY",
 "YNYN",
 "NYNY",
 "YNYN"};
			int k                     = 2;
			int expected__            = 15;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 4: {
			int magicPower[]          = {46474, 60848, 98282, 58073, 42670, 50373};
			string magicBond[]        = {"NYNNNY", "YNNYNY", "NNNYYY", "NYYNNN", "NNYNNN", "YYYNNN"};
			int k                     = 3;
			int expected__            = 209503;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 5: {
			int magicPower[]          = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
			string magicBond[]        = {"NNYYYNYYNYNNY", "NNYNYYYYYYYNY", "YYNYYNYYYYYYY", "YNYNYYNYYYYYY",
 "YYYYNNYYYYYNY", "NYNYNNYYYYYNN", "YYYNYYNYYYYYY", "YYYYYYYNYNYYY",
 "NYYYYYYYNYYYY", "YYYYYYYNYNNNN", "NYYYYYYYYNNYN", "NNYYNNYYYNYNN", "YYYYYNYYYNNNN"};
			int k                     = 9;
			int expected__            = -1;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 6: {
			int magicPower[]          = {1, 1};
			string magicBond[]        = {"NN", "NN"};
			int k                     = 1;
			int expected__            = 1;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}
		case 7: {
			int magicPower[]          = {1,1,2,5,2,4,2};
			string magicBond[]        = {"NNNNNNN","NNYNNNN","NYNNNYN","NNNNNNY","NNNNNNN","NNYNNNN","NNNYNNN"};
			int k                     = 3;
			int expected__            = 11;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}

		// custom cases

/*      case 8: {
			int magicPower[]          = ;
			string magicBond[]        = ;
			int k                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}*/
/*      case 9: {
			int magicPower[]          = ;
			string magicBond[]        = ;
			int k                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}*/
/*      case 10: {
			int magicPower[]          = ;
			string magicBond[]        = ;
			int k                     = ;
			int expected__            = ;

			clock_t start__           = clock();
			int received__            = MagicMoleculeEasy().maxMagicPower(vector <int>(magicPower, magicPower + (sizeof magicPower / sizeof magicPower[0])), vector <string>(magicBond, magicBond + (sizeof magicBond / sizeof magicBond[0])), k);
			return verify_case(casenum__, expected__, received__, clock()-start__);
		}*/
		default:
			return -1;
		}
	}
}


int main(int argc, char *argv[]) {
	if (argc == 1) {
		moj_harness::run_test();
	} else {
		for (int i=1; i<argc; ++i)
			moj_harness::run_test(atoi(argv[i]));
	}
}
// END CUT HERE