#include #include #include #include using namespace std; int main() { int n; long long L; cin >> n >> L; vector a, b; a.push_back(-1); b.push_back(-1); for(int i = 0; i < n; ++i) { char c; long long t; cin >> c >> t; (c == 'N' ? a : b).push_back(t); } auto A = a.size(), B = b.size(); auto INF = 1LL << 60; array>, 2> dp; for(auto& v : dp) { v.resize(A + 1); for(auto& w : v) { w.resize(B + 1, INF); } } dp[0][1][0] = 0; dp[1][0][1] = 0; std::function chain; chain = [&](int k, int i, int j, long long t, long long cost) { if(k == 0) { if(a[i] > t) { dp[k][i][j] = min(dp[k][i][j], cost); return; } cost += t - a[i]; // SLOW: This solution is slow because it does tail recursion for // every single train that can be send before time t, instead of // collecting them all in a while loop. if(i + 1 < A && a[i + 1] <= t) { chain(k, i + 1, j, t, cost); return; } dp[k][i + 1][j] = min(dp[k][i + 1][j], cost); if(j + 1 < B) { chain(1 - k, i, j + 1, t + L, cost); } } else { if(b[j] > t) { dp[k][i][j] = min(dp[k][i][j], cost); return; } cost += t - b[j]; if(j + 1 < B && b[j + 1] <= t) { chain(k, i, j + 1, t, cost); return; } dp[k][i][j + 1] = min(dp[k][i][j + 1], cost); if(i + 1 < A) { chain(1 - k, i + 1, j, t + L, cost); } } }; for(int i = 0; i < A; ++i) { for(int j = 0; j < B; ++j) { if(i > 0 && dp[0][i][j] < INF) { chain(0, i, j, a[i], dp[0][i][j]); } if(j > 0 && dp[1][i][j] < INF) { chain(1, i, j, b[j], dp[1][i][j]); } } } cout << min(dp[0][A][B - 1], dp[1][A - 1][B]) << endl; }