#include<iostream>
#include<vector>
using namespace std;
int G[55][55];
int n,m,yM[55],chk[55];
int dfs(int u){
    for(int v=0; v<m;v++) if(G[u][v] && !chk[v]){
        chk[v] = 1;
        if(yM[v]==-1 || dfs(yM[v])){
            yM[v] = u; return 1;
        }
    }
    return 0;
}
bool judge(int th,int tr, int bh, int br){
    return br > tr && br*th >tr*bh;
}
class PointyWizardHats{
    public : int getNumHats(vector <int> th, vector <int> tr, vector <int> bh, vector <int> br){
        n = th.size(), m = bh.size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(judge(th[i],tr[i],bh[j],br[j]))
                    G[i][j] =1;
        int ans=0;
        for(int i=0;i<m;i++) yM[i] = -1;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) chk[j] = 0;
            ans += dfs(i);
        }
        return ans;
    }
};

#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 13;
pair<int,int> pos[N];
bool can[1600000],row[N],col[N];
int count(int mask){
    int a = 0;
    while(mask) a += mask & 1, mask >>= 1;
    return a;
}
int dp[1600000],base[20],cont[1<<N],n,cns;
int cal(int a,int b){
    int ans=0;
    for(int i=0;i<n;i++){
        ans += base[i] * ((a&1) + (b&1));
        a>>=1, b>>=1;
    }
    return ans;
}
const int inf = 100;
void OP(int msk){for(int i=0;i<n;i++,msk>>=1)cout<<(msk&1);cout<<" ";}
int dfs(int msk1,int msk2,int m){
    
    if(m==0) return 0;
    int &ans = dp[cal(msk1,msk2)];
    if(ans!=-1) return ans;
    for(int i=0;i<n;i++)if((1<<i) & msk1);else{
        int nmask = msk1 ^ (1<<i),l=inf,r=inf;
        if(can[cal(nmask,msk2)]) l = dfs(nmask,msk2,m-1);
        if(can[cal(nmask,msk2 ^ (1<<i))]) r = dfs(nmask,msk2 ^ (1<<i),m-1)+1;
        if(l > r) l = r;
        if(l>=inf) continue;
        if(ans < l) ans = l;
    }
    return ans;
}
class MagicalHats{
    public : 
    int findMaximumReward(vector <string> G, vector <int> coins, int m){
        n = 0;
        int flag,k, ans = 0;cns = coins.size();
        memset(dp,-1,sizeof(dp));
    //    memset(hash,-1,sizeof(hash));
        for(int i=0;i<G.size();i++)
            for(int j=0;j<G[0].size();j++)
                if(G[i][j] == 'H'){
                    pos[n++] = make_pair(i,j);
                }
        base[0] = 1;
        for(int i=1;i<n;i++) base[i] = 3*base[i-1];
        int l1=G.size(),l2=G[0].size();
        for(int i=0;i<(1<<n);i++) cont[i] = count(i);
        for(int msk1 = 0; msk1 < (1<<n); msk1 ++){
            for(int msk2 = 0; msk2 < (1<<n); msk2 ++){
                if(cont[msk2] != cns) continue;
                if(can[k=cal(msk1,msk2 & msk1)]) continue;
                for(int i=0;i<l1;i++) row[i] = 0;
                for(int i=0;i<l2;i++) col[i] =0;
                for(int i=0;i<n;i++) if((1<<i) & msk2);else row[pos[i].first]^=1, col[pos[i].second] ^=1;
                flag = 0;
                for(int i=0;i<G.size();i++) flag |= row[i];
                for(int i=0;i<G[0].size();i++) flag |= col[i];
                if(flag) continue;
                can[k] = 1;
            }
            if(msk1 && !can[0]) return -1;
        }
    //    cout<<"."<<endl;
        if(!can[0]) return -1;
        k = dfs(0,0,m);
        sort(coins.begin(), coins.end());
        for(int i=0;i < k; i++) ans += coins[i];
        return ans;
    }
};