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;
const long long INF = (1LL << 60);
class Dijkstra {
 public:
  struct edge {
    long long v;
    pair<long long, long long> dist;
  };
  struct state {
    long long v;
    pair<long long, long long> cost;
    bool operator>(const state s) const { return cost > s.cost; }
  };
  long long N;
  vector<vector<edge>> E;
  Dijkstra(long long n) : N(n), E(n) {}
  void add_directed_edge(long long u, long long v,
                         pair<long long, long long> d) {
    E[u].push_back((edge){v, d});
  }
  vector<pair<long long, long long>> shortest_path(long long S) {
    vector<pair<long long, long long>> dp(E.size(),
                                          pair<long long, long long>(INF, INF));
    priority_queue<state, vector<state>, greater<state>> q;
    q.push((state){S, pair<long long, long long>(0, 0)});
    while (!q.empty()) {
      long long v = q.top().v;
      pair<long long, long long> cost = q.top().cost;
      q.pop();
      if (dp[v] <= cost) continue;
      dp[v] = cost;
      for (long long i = ((long long)0); i < ((long long)E[v].size()); i++) {
        long long nv = E[v][i].v;
        pair<long long, long long> ncost = pair<long long, long long>(
            cost.first + E[v][i].dist.first, cost.second + E[v][i].dist.second);
        if (dp[nv] > ncost) q.push((state){nv, ncost});
      }
    }
    return dp;
  }
};
int main(void) {
  long long N, Time;
  cin >> N >> Time;
  string A, B;
  cin >> A >> B;
  vector<vector<string>> S(N);
  vector<vector<long long>> T(N);
  for (long long i = ((long long)0); i < ((long long)N); i++) {
    long long a;
    cin >> a;
    for (long long j = ((long long)0); j < ((long long)a); j++) {
      string s;
      cin >> s;
      S[i].push_back(s);
    }
    for (long long j = ((long long)0); j < ((long long)a - 1); j++) {
      long long t;
      cin >> t;
      T[i].push_back(t);
    }
  }
  vector<string> vec;
  vec.push_back(A);
  vec.push_back(B);
  for (long long i = ((long long)0); i < ((long long)N); i++)
    for (long long j = ((long long)0); j < ((long long)S[i].size()); j++)
      vec.push_back(S[i][j]);
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  vector<pair<long long, string>> idx;
  for (long long i = ((long long)0); i < ((long long)N); i++)
    for (long long j = ((long long)0); j < ((long long)S[i].size()); j++)
      idx.push_back(pair<long long, string>(i, S[i][j]));
  for (long long i = ((long long)0); i < ((long long)vec.size()); i++)
    idx.push_back(pair<long long, string>(N, vec[i]));
  sort(idx.begin(), idx.end());
  Dijkstra dijk(idx.size());
  for (long long i = ((long long)0); i < ((long long)N); i++) {
    for (long long j = ((long long)0); j < ((long long)S[i].size() - 1); j++) {
      long long p = lower_bound(idx.begin(), idx.end(),
                                pair<long long, string>(i, S[i][j])) -
                    idx.begin();
      long long q = lower_bound(idx.begin(), idx.end(),
                                pair<long long, string>(i, S[i][j + 1])) -
                    idx.begin();
      dijk.add_directed_edge(p, q, pair<long long, long long>(T[i][j], 0));
      dijk.add_directed_edge(q, p, pair<long long, long long>(T[i][j], 0));
    }
  }
  for (long long i = ((long long)0); i < ((long long)N); i++) {
    for (long long j = ((long long)0); j < ((long long)S[i].size()); j++) {
      long long p = lower_bound(idx.begin(), idx.end(),
                                pair<long long, string>(i, S[i][j])) -
                    idx.begin();
      long long q = lower_bound(idx.begin(), idx.end(),
                                pair<long long, string>(N, S[i][j])) -
                    idx.begin();
      if (S[i][j] != B) {
        dijk.add_directed_edge(p, q, pair<long long, long long>(Time, 1));
        dijk.add_directed_edge(q, p, pair<long long, long long>(0, 0));
      } else {
        dijk.add_directed_edge(p, q, pair<long long, long long>(0, 0));
        dijk.add_directed_edge(q, p, pair<long long, long long>(0, 0));
      }
    }
  }
  long long s =
      lower_bound(idx.begin(), idx.end(), pair<long long, string>(N, A)) -
      idx.begin();
  long long g =
      lower_bound(idx.begin(), idx.end(), pair<long long, string>(N, B)) -
      idx.begin();
  pair<long long, long long> ans = dijk.shortest_path(s)[g];
  if (ans == pair<long long, long long>(INF, INF))
    cout << -1 << endl;
  else
    cout << ans.first << " " << ans.second << endl;
}
