Example

Input

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


Output

380 1
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <tuple>
#include <queue>
#include <utility>
using namespace std;
 
typedef tuple<int,int,int> T3; //to,dist,transfer
vector<T3> E[200050];
map<tuple<int,int,string>,int> M;
 
int id(int line, int pos, string sta){
    auto t = make_tuple(line,pos,sta);
    if(M.find(t)==M.end()){
        int id = M.size();
        M[t]=id;
    }
    return M[t];
}
 
int main(){
    int N,T;
    cin>>N>>T;
    string A,B;
    cin>>A>>B;
    int start = id(0,0,A), goal = id(0,0,B);
    for(int n=1;n<=N;n++){
        int a;
        cin>>a;
        vector<string> S(a);
        vector<int> TT(a-1);
        for(auto &s:S){
            cin>>s;
        }
        for(auto &t:TT){
            cin>>t;
        }
        //graph build
        for(int i=0;i<a;i++){
            int ground = id(0,0,S[i]);
            int inside = id(n,i,S[i]);
            E[ground].emplace_back(inside,T,1);
            E[inside].emplace_back(ground,0,0);
        }
        for(int i=0;i<a-1;i++){
            int cs = id(n,i,S[i]);
            int ns = id(n,i+1,S[i+1]);
            E[cs].emplace_back(ns,TT[i],0);
            E[ns].emplace_back(cs,TT[i],0);
        }
    }
 
    priority_queue<T3,vector<T3>,greater<T3>> que; // T:=<time,transfer,id>
    que.emplace(0,0,start);
    typedef pair<int,int> P; // time, trasfer
    vector<P> memo(200000,P(1100000000,0));
    while(!que.empty()){
        int time, transfer, cs;
        tie(time,transfer,cs) = que.top(); que.pop();
        if(cs==goal){
            cout<<time-T<<' '<<transfer-1<<endl;
            return 0;
        }
        for(auto e:E[cs]){
            int to, dist, trans;
            tie(to,dist,trans) = e;
            if(P(dist+time,transfer+trans)<memo[to]){
                memo[to]=P(dist+time,transfer+trans);
                que.emplace(dist+time,transfer+trans,to);
            }
        }
    }
    cout<<-1<<endl;
 
    return 0;
}