// @EXPECTED_RESULTS@: ACCEPTED, TIME_LIMIT_EXCEEDED // This is probably an O(n^3 lg n) solution. // It's over 10 times slower than the O(n^3) solution ragnar.cpp, and hence this should probably time out. #include using namespace std; using i64 = long long; const int N = 555; map dp[2][N][N]; int main() { int n, cross; cin >> n >> cross; vector> arrive(2); while (n--) { char c; cin >> c; int t; cin >> t; arrive[c == 'S'].push_back(t); } int gets = 0; int considers = 0; int erases=0; auto get_dp = [&](int dir, int a, int b, i64 t) -> i64 { ++gets; auto &M = dp[dir][a][b]; auto it = M.upper_bound(t); if (it == begin(M)) return i64(1e18); return prev(it)->second; }; set> pq; auto consider = [&](int dir, int a, int b, i64 t, i64 s) { ++considers; if (get_dp(dir, a, b, t) <= s) return; auto &M = dp[dir][a][b]; M[t] = s; auto it = next(M.find(t)); while (it != end(M) && it->second >= s) { ++erases; it = M.erase(it); } pq.emplace(t, s, dir, a, b); }; consider(0, 0, 0, 0, 0); consider(1, 0, 0, 0, 0); while (!pq.empty()) { auto [t,s,dir,a,b] = *begin(pq); pq.erase(begin(pq)); if (get_dp(dir, a, b, t) < s) continue; consider(1-dir, b, a, t+cross, s); if (a < ssize(arrive[dir])) { i64 arr = arrive[dir][a]; consider(dir, a+1, b, max(t,arr), s + max(t-arr, 0LL)); } } int na = size(arrive[0]), nb = size(arrive[1]); i64 resa = rbegin(dp[0][na][nb])->second; i64 resb = rbegin(dp[1][nb][na])->second; cout << min(resa, resb) << '\n'; cerr << gets/100000 << '\n' << considers/100000 << '\n' << erases/100000 << '\n'; }