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>
using namespace std;
constexpr int MAX_V = 100000;
constexpr int MAX_N = 10000;
typedef pair<int, int> state;
typedef pair<pair<int, int>, state> P;
typedef pair<int, int> edge;
vector<int> p[MAX_N];
vector<int> t[MAX_N];
set<pair<int, int>> S[MAX_V];
unordered_map<string, int> converter;
inline int input_station() {
  string station_name;
  cin >> station_name;
  if (!converter.count(station_name)) {
    converter.insert({station_name, converter.size()});
  }
  return converter[station_name];
}
string dijkstra(int s, int g, int T) {
  map<state, pair<int, int>> dist;
  priority_queue<P, vector<P>, greater<P>> que;
  for (const auto &e : S[s]) {
    const state st(e.first, e.second);
    dist[st] = {0, 0};
    que.push({{0, 0}, st});
  }
  while (!que.empty()) {
    const pair<int, int> d = que.top().first;
    const int r = que.top().second.first;
    const int q = que.top().second.second;
    que.pop();
    if (dist[state(r, q)] < d) continue;
    const int v = p[r][q];
    if (v == g) return to_string(d.first) + " " + to_string(d.second);
    for (const auto &e : S[v]) {
      const state next_state(e.first, e.second);
      const pair<int, int> next_dist(d.first + T, d.second + 1);
      if (!dist.count(next_state) || dist[next_state] > next_dist) {
        dist[next_state] = next_dist;
        que.push({next_dist, next_state});
      }
    }
    if (0 < q) {
      const state next_state(r, q - 1);
      const pair<int, int> next_dist(d.first + t[r][q - 1], d.second);
      if (!dist.count(next_state) || dist[next_state] > next_dist) {
        dist[next_state] = next_dist;
        que.push({next_dist, next_state});
      }
    }
    if (q < static_cast<int>(p[r].size() - 1)) {
      const state next_state(r, q + 1);
      const pair<int, int> next_dist(d.first + t[r][q], d.second);
      if (!dist.count(next_state) || dist[next_state] > next_dist) {
        dist[next_state] = next_dist;
        que.push({next_dist, next_state});
      }
    }
  }
  return "-1";
}
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, T;
  cin >> N >> T;
  const int A = input_station();
  const int B = input_station();
  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    p[i].resize(a);
    t[i].resize(a - 1);
    for (int j = 0; j < a; ++j) {
      p[i][j] = input_station();
      S[p[i][j]].insert({i, j});
    }
    for (auto &e : t[i]) cin >> e;
  }
  cout << dijkstra(A, B, T) << endl;
}
