#define maxn 55

 class Egalitarianism {

 public:

     int maxDifference(vector <string>, int);

 };

 int e[maxn][maxn],n,f[maxn][maxn];

 int Egalitarianism::maxDifference(vector <string> isFriend, int d) {

     n = isFriend.size();

     memset(e,-,sizeof(e));

     for (int i= ; i<n ; i++ ) {

         for (int j= ; j<n ; j++ ) if (isFriend[i][j]=='Y') {

             e[i][j] = d;

         }

     }

     int ans = -;

     for (int k= ; k<n ; k++ ) {

         for (int i= ; i<n ; i++ ) {

             for (int j= ; j<n ; j++ ) if (e[i][k] != - && e[k][j] != -) {

                 if (e[i][j]==- || e[i][j]>e[i][k] + e[k][j])

                     e[i][j] = e[i][k]+e[k][j];

             }

         }

     }

     for (int i= ; i<n ; i++ ) for (int j= ; j<n ; j++ )  if (i!=j){

         if (e[i][j] == -) return -;

         ans = max(ans,e[i][j]);

     }

     return ans;

 }

 using namespace std;

 #define maxn 60

 #define maxd 100010

 #include <cstring>

 const int INF = maxd-;

 typedef long long llong;

 class Excavations {

 public:

     long long count(vector <int>, vector <int>, vector <int>, int);

 };

 bool in[maxn];

 llong c[maxn][maxn] , b[maxn][maxn][maxn] ;//, s[maxn][maxn][maxn] , s2[maxn][maxn][maxn];

 int cnt[maxn],n,m,D;

 map<int,int> hk , hd;

 vector<int> bufk , bufd , t[maxn];

 struct node{

     int k,d;

 };node build[maxn];

 bool cmp (node a , node b) {

     if (a.k == b.k) return a.d<b.d;

     return a.k<b.k;

 }

 void pretreat(vector<int> kind,vector<int> depth,vector<int> found) {

     n = kind.size();

     m = found.size();

     bufd.push_back();

     bufd.push_back(INF);

     bufk.push_back();

     for (int i= ; i<n ; i++ ) bufk.push_back(kind[i]) , bufd.push_back(depth[i]);

     sort(bufd.begin(),bufd.end());

     sort(bufk.begin(),bufk.end());

     bufd.erase( unique(bufd.begin(),bufd.end()) , bufd.end() ) ;

     bufk.erase( unique(bufk.begin(),bufk.end()) , bufk.end() ) ;

     for (int i= ; i<(int)bufk.size() ; i++ ) hk[bufk[i]] = i;

     for (int i= ; i<(int)bufd.size()  ; i++ ) hd[bufd[i]] = i;

     for (int i= ; i<n ; i++ ) build[i] = (node){hk[kind[i]] , hd[depth[i]]};

     sort(build,build+n,cmp);

     for (int i= ; i<m ; i++ )    in[hk[found[i]]] = ;

     for (int i= ; i<= ; i++ ) {

         c[i][] = ;

         for (int j= ; j<=i ; j++ ) c[i][j] = c[i-][j-] + c[i-][j];

     }

     D = hd[maxd-];

     for (int i= ; i<=D ; i++ ) {

         for (int j= ; j<n ; j++ ) if (build[j].d>=i)

             cnt[i] ++;

     }

     for (int i= ; i<n ; i++ ) t[build[i].k].push_back(build[i].d);

     for (int i= ; i<= ; i++ ) sort(t[i].begin() , t[i].end());

 }

 long long Excavations::count(vector <int> kind, vector <int> depth, vector <int> found, int K) {

     pretreat(kind,depth,found);

     b[][][] = ;

     for (int i= ; i< ; i++ )

     for (int j= ; j<D ; j++ )

     for (int k= ; k<=K ; k++ ) if (b[i][j][k]) { //printf("b[%d][%d][%d]=%lld\n",i,j,k,b[i][j][k]);

         int debug = ;

         if (j==) debug = ;

         if (in[i+]) {// printf("t[%d].size()=%d\n",i+1,(int)t[i+1].size()); for (int x=0 ; x<(int)t[i+1].size() ; x++ ) printf("%d ",t[i+1][x]); printf("\n");

             for (int x= ; x<(int)t[i+].size() ; x++ )

             for (int y= ; y<=x ; y++ ) {

                 if (y++k>K) break;

                 int dep = max(j, t[i+][x]);

                 b[i+][dep][y++k] += b[i][j][k] * c[x][y];

                 if (debug) {

             //        printf("b[%d][%d][%d] add %lld * c[%d][%d](%lld) = %lld\n",i+1,dep,y+1+k,b[i][j][k],x,y,c[x][y],b[i][j][k]*c[x][y]);

                 }

             }

         } else {

             b[i+][j][k] += b[i][j][k];

         //    if (debug) printf("b[%d][%d][%d] add %lld\n",i+1,j,k,b[i][j][k]);

         }

     }

     llong ans = ;

     vector<int> illegal;

     int f[maxn];

     memset(f,,sizeof(f));

     for (int i= ; i<n ; i++ ) if (!in[build[i].k]) {

         illegal.push_back(build[i].d);

         f[build[i].d] ++ ;

     }

     sort(illegal.begin(),illegal.end());

     illegal.erase( unique(illegal.begin(),illegal.end()) , illegal.end() );

     for (int i= ; i<D ; i++ )

     for (int j=m ; j<=K ; j++ ) if (b[][i][j]) {

         if (j==K) {

             ans += b[][i][j];

             printf("add: b[%d][%d]=%lld\n",i,j,b[][i][j]);

         }

         else {

             llong fct = ;

             for (int x= ; x<(int)illegal.size() ; x++ ) if (illegal[x]>i) {

                 int d = illegal[x];

                 int need = K-j;

                 for (int y= ; y<=need && y<=f[d] ; y++ ) {

                     fct += c[f[d]][y] * c[cnt[d]-f[d]][need-y];

                     printf("fct add: c[%d][%d] * c[%d][%d] = %lld\n",f[d],y,cnt[d]-f[d],need-y,c[f[d]][y]*c[cnt[d]-f[d]][need-y]);

                 }

             }

             ans += b[][i][j] * fct;

         }

     }

     return ans;

 }

 string s = "";

     for (int i= ; i<(int)courseInfo.size() ; i++ ) s += courseInfo[i];

     stringstream ss(s);

     string t;

     while (ss>>t) {

         sscanf(t.c_str(),"%c%d->%c%d:%d",&a,&da,&b,&db,&cst);

         int pa , pb;

         pa = encode((int)(a-'A'),da);

         pb = encode((int)(b-'A'),db);

         addedge(pb,pa,cst);

     }