#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
template<typename V>
class Graph
{
map<V, int> v2id_;
vector<V> id2v_;
public:
vector< vector<int> > G;
int vert( const V& t )
{
if( !v2id_.count(t) ) { v2id_[t] = G.size(); id2v_.push_back(t); G.resize(G.size()+1); }
return v2id_[t];
}
void edge( const V& s_, const V& t_ )
{
int s=vert(s_), t=vert(t_);
G[s].push_back(t);
}
const V& orig( int v )
{
return id2v_[v];
}
};
class StronglyConnectedComponent
{
public:
StronglyConnectedComponent( const vector< vector<int> >& G )
: scc(), forest(), G(G), no(0), dfs_no(G.size()), dfs_lo(G.size()), scc_id(G.size())
{
for(int v=0; v<G.size(); ++v)
dfs(v);
}
vector< vector<int> > scc; // scc[i] : the list of verts in the i-th component
vector< vector<int> > forest; // the forest structure over sccs
private:
const vector< vector<int> >& G;
int no;
vector<int> dfs_no; // Special: 0 : not visited yet
vector<int> dfs_lo; // Special: INT_MAX : already classified into some scc !!!! not a good idea!
// rather use scc_id for that purpose (distinguishing assigned or not)
vector<int> scc_id;
vector<int> pending;
void dfs(int v)
{
if( dfs_no[v] )
return;
dfs_no[v] = dfs_lo[v] = ++no; // visit v
for(int i=0; i<G[v].size(); ++i) // visit children
{
int u = G[v][i];
dfs( u );
if( !is_already_classified_in_some_scc(u) )
dfs_lo[v] = min( dfs_lo[v], dfs_lo[G[v][i]] );
}
pending.push_back(v);
if( dfs_no[v] == dfs_lo[v] ) { // found the representative of a scc
// todo: pending -> dfs_lo:=INT_MAX
scc.push_back(pending), pending.clear();
// construct scc-forest (if needed)
scc_id[v] = scc.size()-1;
set<int> children;
for(int i=0; i<G[v].size(); ++i)
if( dfs_lo[G[v][i]] != v )
children.insert( scc_id[dfs_lo[G[v][i]]] );
forest.push_back( vector<int>(children.begin(), children.end()) );
}
}
};
class ImpossibleGame { public:
static LL C(LL n, LL k) {
LL v = 1;
for(int i=1; i<=k; ++i)
v = v * (n+1-i) / i;
return v;
}
static LL weight(LL a, LL b, LL c, LL d) {
return C(a+b+c+d,a) * C(b+c+d,b) * C(c+d,c);
}
long long getMinimum(int k, vector <string> before, vector <string> after)
{
vector< pair< vector<int>, vector<int> > > dif;
for(int i=0; i<after.size(); ++i)
{
vector<int> be(4), af(4);
for(int j=0; j<before[i].size(); ++j) be[before[i][j]-'A'] ++;
for(int j=0; j< after[i].size(); ++j) af[ after[i][j]-'A'] ++;
dif.push_back( make_pair(be,af) );
}
Graph< vector<int> > G;
vector<int> v(4);
for(v[0]=0; v[0]<=k; ++v[0])
for(v[1]=0; v[0]+v[1]<=k; ++v[1])
for(v[2]=0; v[0]+v[1]+v[2]<=k; ++v[2])
for(v[3]=0; v[0]+v[1]+v[2]+v[3]<=k; ++v[3])
{
G.vert(v);
for(int i=0; i<dif.size(); ++i)
{
bool dame = false;
vector<int> u = v;
for(int k=0; k<4; ++k)
{
if( (u[k]-=dif[i].first[k]) < 0 )
dame = true;
u[k] += dif[i].second[k];
}
if( !dame )
G.edge(v, u);
}
}
StronglyConnectedComponent scc(G.G);
return 0;
}
};
// 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> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, ImpossibleGame().getMinimum(k, before, after));}
int main(){
CASE(0)
int k = 1;
string before_[] = { "A" }
;
vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
string after_[] = { "B" }
;
vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
long long _ = 2LL;
END
CASE(1)
int k = 2;
string before_[] = { "A", "A", "D" }
;
vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
string after_[] = { "B", "C", "D" }
;
vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
long long _ = 5LL;
END
CASE(2)
int k = 2;
string before_[] = { "B", "C", "D" }
;
vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
string after_[] = { "C", "D", "B" }
;
vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
long long _ = 9LL;
END
CASE(3)
int k = 6;
string before_[] = { "AABBC", "AAAADA", "AAACA", "CABAA", "AAAAAA", "BAAAA" }
;
vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
string after_[] = { "AACCB", "DAAABC", "AAAAD", "ABCBA", "AABAAA", "AACAA" }
;
vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
long long _ = 499LL;
END
/*
CASE(4)
int k = ;
string before_[] = ;
vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
string after_[] = ;
vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
long long _ = LL;
END
CASE(5)
int k = ;
string before_[] = ;
vector <string> before(before_, before_+sizeof(before_)/sizeof(*before_));
string after_[] = ;
vector <string> after(after_, after_+sizeof(after_)/sizeof(*after_));
long long _ = LL;
END
*/
}
// END CUT HERE