Example

Input

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


Output

380 1
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <string>
#include <deque>
#include <functional>
#include <tuple>

template <class Weight>
struct edge {
  using value_type = Weight;
  size_t src, dst;
  value_type cost;

  edge(size_t src, size_t dst, value_type cost=1):
    src(src), dst(dst), cost(cost)
  {}

  bool operator <(const edge<value_type> &rhs) const {
    if (cost != rhs.cost) return cost < rhs.cost;
    if (src != rhs.src) return src < rhs.src;
    return dst < rhs.dst;
  }
};

template <class Weight>
struct graph: public std::vector<std::vector<edge<Weight>>> {
  using value_type = Weight;
  graph(size_t n): std::vector<std::vector<edge<value_type>>>(n) {}

  void connect_with(size_t src, size_t dst, value_type cost=1) {
    (*this)[src].emplace_back(src, dst, cost);
    (*this)[dst].emplace_back(dst, src, cost);
  }

  void connect_to(size_t src, size_t dst, value_type cost=1) {
    (*this)[src].emplace_back(src, dst, cost);
  }
};

template <class Tp, class Compare>
using priority_queue = std::priority_queue<Tp, std::deque<Tp>, Compare>;

template <class T1, class T2>
std::pair<T1, T2> operator +(const std::pair<T1, T2>& p, const std::pair<T1, T2>& q) {
  return {p.first+q.first, p.second+q.second};
}

template <class Tp>
constexpr Tp inf() {
  return static_cast<Tp>(1) << (8*sizeof(Tp)-3);
};

template <>
constexpr std::pair<intmax_t, size_t> inf() {
  return std::make_pair(inf<intmax_t>(), inf<size_t>());
}

template <class Weight>
std::vector<Weight> shortest(const graph<Weight> &g, size_t s) {
  // based on Dijkstra algorithm
  std::vector<Weight> res(g.size(), inf<Weight>());
  priority_queue<std::pair<Weight, size_t>, std::greater<>> q;
  res[s] = Weight();
  q.emplace(Weight(), s);
  while (!q.empty()) {
    Weight w;
    size_t v;
    std::tie(w, v) = q.top();
    q.pop();
    if (w > res[v]) continue;

    for (const auto& e: g[v]) {
      if (res[e.dst] > w + e.cost) {
        res[e.dst] = w + e.cost;
        q.emplace(res[e.dst], e.dst);
      }
    }
  }
  return res;
}

int main() {
  size_t N;
  intmax_t T;
  scanf("%zu %jd", &N, &T);

  char buf[16];
  scanf("%s", buf);
  std::string A = buf;
  scanf("%s", buf);
  std::string B = buf;

  std::vector<std::vector<std::string>> s(N);
  std::vector<std::vector<intmax_t>> t(N);
  std::map<std::pair<std::string, size_t>, size_t> enc;
  enc[std::make_pair(A, -1)] = 0;
  enc[std::make_pair(B, -1)] = 0;

  for (size_t i = 0; i < N; ++i) {
    size_t a;
    scanf("%zu", &a);
    s[i].resize(a);
    for (size_t j = 0; j < a; ++j) {
      scanf("%s", buf);
      s[i][j] = buf;
      enc[std::make_pair(s[i][j], i)] = 0;
      enc[std::make_pair(s[i][j], -1)] = 0;
    }

    t[i].resize(a-1);
    for (size_t j = 0; j < a-1; ++j)
      scanf("%jd", &t[i][j]);
  }

  {
    size_t i = 0;
    for (auto& p: enc)
      p.second = i++;
  }

  size_t n = enc.size();
  graph<std::pair<intmax_t, size_t>> g(n);
  for (size_t i = 0; i < N; ++i) {
    for (size_t j = 1; j < s[i].size(); ++j) {
      size_t u = enc[std::make_pair(s[i][j-1], i)];
      size_t v = enc[std::make_pair(s[i][j], i)];
      g.connect_with(u, v, std::make_pair(t[i][j-1], 0));
    }
    for (size_t j = 0; j < s[i].size(); ++j) {
      size_t u = enc[std::make_pair(s[i][j], i)];
      size_t v = enc[std::make_pair(s[i][j], -1)];
      g.connect_to(u, v, std::make_pair(0, 0));
      g.connect_to(v, u, std::make_pair(T, 1));
    }
  }

  size_t u0 = enc[std::make_pair(A, -1)];
  size_t v0 = enc[std::make_pair(B, -1)];
  auto cost = shortest(g, u0)[v0];
  if (cost.second == inf<size_t>()) return puts("-1"), 0;
  printf("%jd %zu\n", cost.first-T, cost.second-1);
}

