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>
#pragma warning(disable : 4996)
using namespace std;
using ld = long double;
template <class T>
using Table = vector<vector<T>>;
const ld eps = 1e-9;
struct Line {
  int from;
  int to;
  int type;
  int id;
  long long int cost;
};
struct aa {
  Line l;
  pair<long long int, int> time;
};
class Compare {
 public:
  bool operator()(const aa& l, const aa& r) { return l.time > r.time; }
};
map<string, int> mp;
vector<pair<long long int, int>> memo;
int main() {
  int N;
  long long int T;
  cin >> N >> T;
  memo = vector<pair<long long int, int>>(100000, make_pair(1e18, 0));
  vector<vector<Line>> ls(100000);
  string Start, Goal;
  cin >> Start >> Goal;
  mp[Start] = 0;
  mp[Goal] = 1;
  int num = 2;
  int id = 0;
  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    vector<int> stas;
    for (int j = 0; j < a; ++j) {
      string st;
      cin >> st;
      if (mp.find(st) == mp.end()) {
        mp[st] = num;
        num++;
      }
      stas.push_back(mp[st]);
    }
    for (int j = 0; j < a - 1; ++j) {
      int a;
      cin >> a;
      ls[stas[j]].push_back(Line{stas[j], stas[j + 1], i, id, a});
      ls[stas[j + 1]].push_back(Line{stas[j + 1], stas[j], i, id, a});
      id++;
    }
  }
  priority_queue<aa, vector<aa>, Compare> que;
  que.push(aa{Line{-1, 0, -1, -1, 0}, make_pair(-T, -1)});
  long long int ans = -1;
  int change = -1;
  while (!que.empty()) {
    aa atop(que.top());
    que.pop();
    const int nowtype = atop.l.type;
    const int nowtime = atop.time.first;
    const int nowchange = atop.time.second;
    const int now = atop.l.to;
    if (now == 1) {
      ans = nowtime;
      change = nowchange;
      break;
    }
    for (auto l : ls[now]) {
      const bool sametype = l.type == nowtype;
      ;
      const long long int nexttime =
          sametype ? nowtime + l.cost : nowtime + l.cost + T;
      const int nextchange = sametype ? nowchange : nowchange + 1;
      const auto nextp = make_pair(nexttime, nextchange);
      if (nextp < memo[l.id]) {
        memo[l.id] = nextp;
        que.push(aa{l, nextp});
      }
    }
  }
  if (ans == -1) {
    cout << -1 << endl;
  } else {
    cout << ans << " " << change << endl;
  }
  return 0;
}
