Example

Input

2 10
Warsaw Petersburg
3
Kiev Moscow Petersburg
150 120
3
Moscow Minsk Warsaw
100 150


Output

380 1
#include<bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define MAX 300001
#define inf 1<<28
using namespace std;

typedef pair<int,int> pii;

class edge{
public:
  int to,cost;
  bool b;
  edge(int to,int cost,bool b):to(to),cost(cost),b(b){}
};

class State{
public:
  int n,cost,sum;
  State(int n,int cost,int sum):n(n),cost(cost),sum(sum){}
  bool operator<(State s)const{
    if(cost!=s.cost)return s.cost<cost;
    return s.sum<sum;
  } 
};

vector<edge> v[MAX];
int n,t,c[MAX];
map<string,vector<int> > m;
string a,b,s[MAX];
set<int> st;
vector<int> start,end;
pii dis[MAX];

void add(int now,string s){
  vector<int> vi=m[s];
  for(int i=0;i<vi.size();i++){
    v[vi[i]].push_back(edge(now,t,true));
    v[now].push_back(edge(vi[i],t,true));
  }
  vi.push_back(now);
  m[s]=vi;
}

pii dijkstra(){
  for(int i=0;i<MAX;i++){
    dis[i].f=inf;
    dis[i].s=inf;
  }
 
  start=m[a];
  end=m[b];
  for(int i=0;i<end.size();i++)st.insert(end[i]);
  priority_queue<State> pq;
  for(int i=0;i<start.size();i++){
    pq.push(State(start[i],0,0));
    dis[start[i]]=mp(0,0);
  }    

  while(!pq.empty()){
    State u=pq.top();
    pq.pop();

    if(st.find(u.n)!=st.end())return mp(u.cost,u.sum);

    if(dis[u.n]<mp(u.cost,u.sum))continue;

    for(int i=0;i<v[u.n].size();i++){
      int next=v[u.n][i].to,cost=v[u.n][i].cost;
      bool f=v[u.n][i].b;
      if(mp(dis[u.n].f+cost,dis[u.n].s+f)<dis[next]){
	dis[next]=mp(dis[u.n].f+cost,dis[u.n].s+f);
	pq.push(State(next,dis[next].f,dis[next].s));
      }
    }
  }
  return mp(-1,-1);
}

int main()
{
  int k,count=0;

  cin>>n>>t;
  cin>>a>>b;

  for(int i=0;i<n;i++){
    cin>>k;
    for(int j=0;j<k;j++)cin>>s[j];
    for(int j=0;j<k-1;j++)cin>>c[j];
    for(int j=0;j<k-1;j++){
      add(count,s[j]);
      v[count].push_back(edge(count+1,c[j],false));
      v[count+1].push_back(edge(count,c[j],false));
      count++;
    }
    add(count,s[k-1]);
    count++;
  }
  pii p=dijkstra();
  if(p==mp(-1,-1))cout<<-1<<endl;
  else cout<<p.f<<" "<<p.s<<endl;

  return 0;
}